Indikken!

Wat doe je bij gebrek aan opbergruimte? Dan koop je een kast. Is ook die kast vol, dan koop je er nog een, en nog één. Aan de zaterdagse file voor Ikea is te zien dat er in Nederland veel gebrek aan opbergruimte is.

Maar er komt een dag dat alle kasten vol spullen zitten, en het huis vol kasten. Dan wil je verhuizen naar een kast van een huis, maar daar heb je geen geld voor. En dus pak je het slimmer aan. Je ruimt alle kasten heel secuur en methodisch opnieuw in, waardoor er wel twee keer zoveel in blijkt te passen als eerst. Met een computer is het net zo. Opslagruimte was van het begin af schaars en duur, terwijl de bytes zich onverstoorbaar aaneen bleven rijgen. Vandaar dat er in de loop der jaren heel wat is nagedacht over slimme manieren zoveel mogelijk gegevens in zo weinig mogelijk bytes te proppen. Dat deden bijvoorbeeld de heren Lempel en Ziv. Samen ontwikkelden zij een inmiddels beroemde methode om de lucht uit gegevens te persen, die in 1980 door een derde slimmerik, Terry Welch, bijgeschaafd en vervolmaakt werd: het Lempel-Ziv-Welch-protocol, kortweg LZW. Dat protocol onder meer gebruikt bij het maken van GIF-plaatjes, met een winst van soms wel 90 procent!

Zoals de meeste werkelijk slim bedachte dingen, is het LZW-protocol in essentie zo simpel, dat je nauwelijks kunt geloven dat het werkt. Het lijkt een beetje op de oplossing van dat oude raadsel, hoe je vier olifanten in een Volkswagen krijgt: olie eruit laten lopen, fant opvouwen. Nu zit er in digitale gegevens geen olie, maar wel herhaling. In de vorige zin komt bijvoorbeeld drie keer de reeks ge voor, en en, er, al, in, it en li elk twee keer.

Lempel, Ziv en Welch laten de herhalingen er eerst uitlopen, en vouwen het residu in superkorte codes op. Maar het miraculeuze is dat later, bij het weer decoderen van de gegevens, de uitgeperste 'olie' er toch zo maar weer blijkt te zijn. Het basisidee achter veel compressiemethodes is dit: je maakt eerst een genummerde lijst van alle verschillende tekenreeksen die in het te comprimeren bestand voorkomen. Die lijst zet je in een nieuw bestandje, met daarachter een rij nummers, die elk voor een van de eerder opgesomde reeksen staan. Als die reeksen langer zijn dan één teken, is die lijst altijd korter dan de oorspronkelijke gegevens. Wil je de zaak weer decoderen, dan hoef je de nummers maar te vervangen door de bijbehorende tekenreeksen aan het begin van het gecodeerde bestand, en klaar is Kees. Nu bedachten Lempel, Ziv en Welch dat je daar op zichzelf niet veel mee opschiet, omdat de kans groot is dat de opsomming van alle tekenreeksen aan het begin van het gecodeerde bestand al bijna net zo lang is als het oorspronkelijke bestand zelf. Bovendien is het een heel karwei om uit een flink bestand alle verschillende tekenreeksen te halen, zodat coderen wel eens erg lang kon gaan duren. Dus bedachten ze een slimme truc: aan het begin van het gecodeerde bestand zetten ze niet alle verschillende tekenreeksen, maar alleen alle verschillende tekens die in het oorspronkelijke bestand voorkomen. Aan het zinnetje van daarstraks is te zien dat dat een slok op een borrel scheelt: er zitten, inclusief de leestekens en de spatie, maar 21 verschillende tekens in, maar wel 73 verschillende reeksen, waarvan er dus 52 ook nog langer zijn dan één teken. Het coderen gaat als volgt in zijn werk. Eerst wordt er een tijdelijke genummerde tabel gemaakt van alle verschillende tekens in het bestand, dat zijn er maximaal 256. Die begintabel vormt ook het begin van het gecodeerde bestand. Daarna bekijk je telkens een stukje van het bestand in twee delen: een staart, die bestaat uit tekens die al bekeken zijn, en een kop: het eerstvolgende teken dat nog niet eerder bekeken is. Aan het begin is de staart natuurlijk leeg, er is immers nog niets bekeken, en is de kop het allereerste teken van het oorspronkelijke bestand. Staat de reeks die staart en kop samen vormen in de tijdelijke tabel, dan voeg je staart en kop samen tot een nieuwe staart, en wordt het eerstvolgende teken in het oorspronkelijk bestand de nieuwe kop. Verder gebeurt er niets. Maar staat die reeks niet in de tijdelijke tabel, dan wordt hij er met een eigen nummer aan toegevoegd. De staart staat in zo'n geval altijd al wel in de tabel, en het nummer daarvan wordt bijgeschreven in het gecodeerde bestand. Tot slot wordt dan de kop tot staart gebombardeerd, en lezen we een nieuw kop uit het oorspronkelijke bestand. Zo schuiven de heren van begin tot eind door het bestand heen, en aan het eind wordt de tijdelijke tabel, meestal een flinke jongen, domweg weggegooid. Als we de spatie het nummer 0 geven, en verder volgende tekens en reeksen volgens de ASCII-tabel nummeren, blijven er zo van de 60 tekens van het olie-zinnetje 51 codetekens zonder een spoor van herhaling over, een winst van bijna twintig procent: 3A0D9@06>09<0597I4: 6076ZB6<?Y60=:9610; 44MC6:08L8VO72.

Bij het decoderen gebeurt vervolgens een wonder. Om de oorspronkelijke gegevens te kunnen herstellen is de tijdelijke tabel weer nodig. Immers, anders weten we niet waar de codenummers op slaan. Maar van die tabel zit alleen het allereerste stukje, dat op de losse tekens betrekking heeft, in het gecodeerde bestand. Lempel, Ziv en Welch hebben gezorgd dat die tabel zich gelijk de Baron van Münchhausen aan zijn eigen haren uit het moeras omhoogtrekt. Eerst maken ze van het kleine tabelletje aan het begin van het gecodeerde bestand weer een tijdelijke tabel in het geheugen. Dan lopen ze één voor één de codenummers af. Het teken (of, later: de reeks), die in de tijdelijke tabel bij dat codenummer hoort wordt toegevoegd aan het nieuwe, weer leesbare bestand. Dan wordt het volgende nummer gelezen, en de bijbehorende tekenreeks naar het nieuwe bestand geschreven. En nu komt de grote truc: De vórige uitgeschreven reeks plus het eerste teken van de reeks die zojuist is uitgeschreven worden nu samen toegevoegd aan de tijdelijke tabel. Het lijkt toverij, maar op die manier ontstaat in principe vanzelf weer precies de oorspronkelijke tijdelijke tabel, en kan het hele bestand perfect worden gereconstrueerd.