Een encyclopedie op een schijfje – met dank aan de wiskunde

Maak jij ook geregeld dankbaar gebruik van Wikipedia? De gratis internetencyclopedie, geschreven door vrijwillige auteurs, zag het levenslicht in 2001. Het project betekende de doodsteek voor de toenmalige grootste commerciële digitale encyclopedie Encarta van Microsoft. Die werd in 1993 uitgebracht op cd-rom en was razend populair omwille van zijn zoekfunctie, hyperlinks tussen artikels en beschikbare multimedia, van audio tot video’s. Voordelen waar Wikipedia dankbaar op voortbouwde.

Wist je dat Encarta zijn succes dankte aan een wiskundig resultaat van exact honderd jaar oud? De Britse wiskundige Michael Barnsley ontdekte dertig jaar geleden hoe hij het theoretische resultaat van Stefan Banach uit 1922 in de praktijk kon toepassen om, naast ongeveer vijftigduizend artikels, zesduizend kleurenfoto’s te wringen op één cd-rom of ongeveer 650 megabyte. Hij zette een foto van ongeveer 1,4 megabyte om in een bestand van slechts 25 kilobyte.

Banach had bewezen dat het herhaald toepassen van een functie die afstanden verkleint steeds hetzelfde resultaat geeft in de limiet, ongeacht het startobject waarop we de functie beginnen te itereren. Het limietobject verandert niet meer wanneer we er de functie op toepassen. De stelling gaat dan ook door het leven als de Banach-fixpuntstelling.

Laten we dit illustreren met een functie die van ieder object drie kleinere kopieën maakt, door de lengte en breedte te halveren en ze vervolgens te verschuiven zodat de top van de eerste kopie samenvalt met de oorspronkelijke hoogte van de beginvorm, de tweede zodat het linkse uiterste samenvalt met dat van het origineel. Hetzelfde voor de derde kopie, maar dan met het rechtse uiterste. Wanneer we dit herhaaldelijk toepassen op volgende driehoeken, verkrijgen we hetzelfde resultaat dat uiteindelijk niet meer verandert.

Het herhaald toepassen van dezelfde procedure van verkleinen en kopiëren op een verschillend startobject geeft hetzelfde eindresultaat.

Dat komt omdat het limietobject opgebouwd is uit kleinere kopieën van zichzelf. Elk object dat zo’n zelfgelijkenis heeft, kan dan ook op die manier gemaakt worden. Figuren die zo’n perfecte gelijkenis met zichzelf vertonen, noemen we fractalen, afgeleid van het Latijnse woord fractus of gebroken. Deze naam werd in 1975 gemunt door de Franse wiskundige en IBM’er Benoit Mandelbrot. Hij merkte op dat heel wat patronen in de natuur een onregelmatige, maar toch herhalende structuur vertonen, zoals de varen, de romanesco, ijskristallen, kustlijnen en zelfs onze longen. Mandelbrot zocht een middel om de lengte of oppervlakte van zo’n structuur te meten en ontdekte dat hij er altijd een breuk mee kon associëren. Vandaar de naam.

Barnsley bewees vervolgens dat je geen volledige zelfgelijkenis in een foto nodig hebt om het idee achter fractalen bouwen met herhaling te kunnen toepassen. Op elke foto zal je namelijk stukken vinden die als kleinere kopieën elders terugkomen, waarbij je misschien alleen de kleur wat moet aanpassen. Denk maar aan de vorm van je schouder die we verkleind terugvinden in de ronding van je kin.

Barnsleys resultaat kreeg al snel de naam kopieer­machine-stelling, omdat je de zelfgelijkenis snel kon vinden door met een kopieermachine kleinere kopieën te maken, daar stukken uit te knippen en op de goeie plaats te kleven. Mensen kunnen die terugkerende vormen op een foto vrij makkelijk ontdekken. Barnsley slaagde erin dit aan een computer over te laten, wat niet evident is. Zijn algoritme berekende welke vormen verkleind, gedraaid en verschoven overeenkomen met een ander stuk van de foto. Een proces dat heel lang kan duren. Hij sloeg dan enkel die gevonden transformaties op in een bestand en niet de hele foto. De stukjes die je moet kopiëren, had hij niet nodig. Als je dan het bestand opende, werden die transformaties gewoon een aantal keer herhaald toegepast op een willekeurige beginvorm om de foto te laten groeien op je scherm. Niet lang na zijn ontdekking werd Barnsley ondernemer en stichtte hij het succesvolle bedrijf Iterated Systems Incorporated, waarmee hij zijn technologie inzette voor Microsofts encyclopedie.

Samen met Encarta moest ook hij zijn uitvinding uiteindelijk opbergen. Hoe beter digitale camera’s en scanners werden, hoe langer zijn bestandsverkleinend algoritme moest draaien, waardoor hij uiteindelijk de duimen moest leggen tegen erg snelle JPEG-compressie (zie ook ‘DeepFakes’, Eos nr. 6, 2018). Dat algoritme verslaat hem in tijd, maar hij blijft de winnaar wanneer het op bestandsgrootte aankomt. En dat dankzij die fantastische fractalen waarover je dan weer alles kunt lezen op … Wikipedia.