Slanke bestanden; Eindhovense nieuwe methode voor datacompressie bekroond

Om een digitale opname van het North Sea Jazz Festival voordelig op te slaan of snel te verzenden, wordt datacompressie toegepast. Maar hoeveel overtollige bits kunnen uit het bestand worden verwijderd?

F.M.J. Willems, Y.M. Shtarkov and Tj.J. Tjalkens, 'The Context-Tree Weighting Method: Basic Properties'. IEEE Transactions on Information Theory, Vol. IT-41, pp. 653-664, 1995.

JE HEBT METEEN in de gaten dat het iets moois is', zegt Frans Willems. Hij doelt ermee op het vertrouwen dat hij en zijn collega's Yuri Shtarkov en Tjalling Tjalkens hadden in hun nieuwe methode voor datacompressie.

Willems en Tjalkens maken deel uit van de groep Informatie en Communicatietheorie van de Technische Universiteit Eindhoven, Shtarkov is verbonden aan een onderzoeksinstituut in Moskou en regelmatig te gast in Eindhoven. Uit de grote belangstelling voor hun werk bleek dat internationalevakgenoten dat vertrouwen deelden. Onlangs werd hun artikel 'The Context-Tree Weighting Method: Basic Properties' door het Institute for Electronical and Electrical Engineers bekroond met de IEEE Information Theory Paper Award.

De informatietheorie is de wiskundige theorie van de telecommunicatie.

Filosofisch getinte vragen over de essentie van communicatie gaat men te lijf met gedegen wiskundig gereedschap. Het is die combinatie van wiskundig rekenwerk en fundamentele vragen die Tjalkens aanspreekt: “Je kunt rekenen aan iets waar je ook een verhaal bij kunt houden.” Om de inhoud van de Dikke Van Dale, een digitale opname van het North Sea Jazz Festival of een ander groot databestand voordeling op te slaan of snel te verzenden, wordt datacompressie toegepast. Het bestand wordt omgezet in een compactere versie, waaruit zoveel mogelijk overtollige bits verwijderd zijn. Daarbij mag natuurlijk geen informatie verloren gaan. Dat wil zeggen, uit de gecomprimeerdeversie moet het originele bestand weer te reconstrueren zijn.

Hoever kun je een bestand laten inkrimpen? Dat is nu precies zo'n fundamentele vraag die thuishoort bij de informatietheorie. C.E. Shannon, de pionier van de informatietheorie, gaf in 1948 op deze vraag een typisch informatietheoretisch antwoord: een wiskundige formule om het best mogelijke compressieniveau te berekenen. Met Shannons formule is berekend dat voor het opslaan van Engelse tekst gemiddeld ongeveer 1,2 bit per letter nodig is. Als dat voor het Nederlands net zoiets is, betekent het dat dit artikel vertaald zou kunnen worden in een rij van ongeveer 1.800 nullen en enen. Normaal gesproken wordt in de computer iedere letter omgezet in een (ASCII)code van 8 bits, ongeveer zes keer zoveel als theoretisch nodig is.

BETERE RESULTATEN

De oorzaak van deze verspilling is dat de statistische eigenschappen van het bestand niet gebruikt worden. In dit artikel komen de vier-letter combinaties 'EEEE' en 'ofni' niet voor, de combinatie 'IEEE' komt af en toe voor, en 'info' komt vaak voor. Toch gebruikt een normale digitale representatie van tekst (met ASCII-codes) voor ieder van deze combinaties hetzelfde aantal bits. Een compressiemethode die vaak voorkomende combinaties vertaalt in een klein aantal bits en omgekeerd, geeft veel betere resultaten. Er bestaat zelfs een methode gebaseerd op dit principe waarmee het optimale niveau van Shannons formule bereikt kan worden.

Voor optimale compressie moeten echter de statistische eigenschappen van het bestand volledig bekend zijn. Dat betekent dat je voor een tekstbestand bij voorbeeld precies moet weten hoe vaak iedere lettercombinatie voorkomt. Maar zulke eigenschappen zijn voor elke tekst anders, ze hangen onder andere af van de taal waarin en het onderwerp waarover de tekst geschreven is. Het is echter onpraktisch voor ieder bestand de compressiemethode aan de inhoud te moeten aanpassen. Die inhoud is meestal niet eens bekend: een faxmodem weet niet of het pornografische plaatjes of medische dossiers aan het verzenden is. Daarom is veel onderzoek gedaan naar universele compressiemethodes. Een universele methode werkt goed voor alle databestanden, of daarin nu Nederlandse gedichten,Amerikaanse advertenties of de beursberichten opgeslagenzijn. De nieuwe methode van Willems, Shtarkov en Tjalkens is universeel. Het enige dat zij veronderstellen is dat het bestand statistisch gezien een boomstructuur heeft.

Een bestand heeft een boomstructuur als je ieder symbool kunt voorspellen aan de hand van een aantal voorafgaande symbolen. Hierbij wordt ervan uitgegaan dat een bestand bit voor bit wordt ingelezen. Bij een bestand met een boomstructuur is de kans dat er een nul volgt afhankelijk van het rijtje bits dat net tevoren ingelezen is. Hoever je iedere keer moet terugkijken, wordt bepaald door de vorm van de boomstructuur, het zogenoemde model (zie kader).

Niet bekend

Schatten levert echter een ingewikkelde theorie op, waar de specialisten steeds minder gelukkig mee waren. Willems, Shtarkov en Tjalkens hadden een beter idee. “Gooi de boel maar bij elkaar en weeg maar”, aldus Willems. Met andere woorden: in plaats van te kiezen voor een specifiek boomstructuur-model werkt hun CTW-methode (Context-Tree Weighting) met een soort gewogen gemiddelde van alle mogelijke modellen. Dit heeft het voordeel dat de onzekerheid in de gegevens in het resultaat tot uitdrukking komt, waardoor er minder informatie verloren gaat. Denk bijvoorbeeld aan het weerbericht. Het KNMI zou kunnen zeggen 'het gaat regenen', als op basis van zijn gegevens regen waarschijnlijker is dan zonneschijn. Maar door te zeggen dat er een 'grote kans op regen', of zelfs, zoals in de Verenigde Staten, dat er 'tachtig procent kans op regen' is, wordt de onzekerheid in de gegevens in de uitspraak verwerkt.

EI VAN COLUMBUS

Met dit idee waren de Eindhovense onderzoekers anderen net voor. In 1993 maakten zij hun werk openbaar op een internationale conferentie in Texas. Het leek of ze het ei van Columbus hadden gevonden, want na afloop van de voordracht door Frans Willems werd deze door de aanwezigen letterlijk bestormd met vragen of verzoeken om een geschreven versie. Enkele onderzoekers uit Israel staken hun teleurstelling niet onder stoelen of banken. Zij werkten aan hetzelfde probleem en waren net tevoren op het idee gekomen dat wegen misschien beter was dan schatten. Overigens was het een lid van deze Israëlische groep, Meir Feder, die het artikel van Willems, Shtarkov en Tjalkens voor de IEEE-prijs nomineerde.

Het idee om te wegen in plaats van te schatten is een eerste stap, maar daarmee is het probleem nog niet opgelost. Net zo belangrijk is de vraag hoe te wegen. Het antwoord vonden de onderzoekers in een korte formule, die zij spoedig na het weeg-idee ontdekten. Die formule zegt grofweg dat je voor elke tak in de boomstructuur het gemiddelde neemt van de twee mogelijkheden dat de tak doodloopt, of dat deze zich nog eens gaat splitsen. In mei 1992 kwam de Russische wetenschapper Yuri Shtarkov voor een werkbezoek naar Eindhoven.

Shtarkov en Tjalkens hadden het idee voor samenwerking eerder opgevat, toen zij samen te gast waren bij een onderzoeksinstituut in Zweden. In Eindhoven sloot Willems zich bij hen aan. Uit een lijst met mogelijke onderzoeksvraagstukken verkozen de drie te werken aan universele datacompressie van bestanden met een boomstructuur. In een week was het idee om te wegen geboren, en stond de formule op papier die de kiem was van deCTW-methode. Shtarkov herinnert zich hoe hij daarna door de stromende regen naar zijn kamertje ging, waar hij er zich na wat rekenwerk van overtuigde dat alles precies klopte. “Een prachtig moment.”

ENTHOUSIASTER

Na de ontdekking van de formule volgden weken van rekenwerk om de methode te ontwikkelen en te analyseren. De onderzoekers werden daarbij steeds enthousiaster. Ten eerste bleek dat je kunt bewijzen dat de CTW-methodeoptimaal is. Met een universele compressiemethode kun je een bestand nooit gegarandeerd op zijn kleinst samenpersen. Er moet een prijs betaald worden voor het feit dat de methode werkt voor allerlei bestanden, niet slechts voor één bestand dat je door en door kent. Maar ook die prijs valt te berekenen en de CTW-methode heeft niet méér nodig.

Ten tweede is de CTW-methode gemakkelijk te analyseren. Dat wil zeggen dat vrij eenvoudig te berekenen is wlke compressieresultaten met deze methode maximaal en minimaal te behalen zijn. De oude methodes (die gebaseerd zijn op schatten) kun je alleen analyseren als je ervan uitgaat dat de bestanden diegecomprimeerd worden oneindig lang zijn. De CTW-methode heeft die beperking niet en is bovendien, in de woorden van Sergio Verdu van de Amerikaanse Princeton Universiteit, “ingenieus en toch eenvoudig”.

In theorie werkt de CTW-methode dus prachtig. Door haar elegantie eneenvoud vergroot ze het inzicht in de fundamenten van de datacompressie, en is dus zeker een onderscheiding waard. Of een theorie zich laat vertalen in praktische resultaten is de vraag, want, zoals Tjalkens het uitdrukt: “Niet altijd past de werkelijkheid zich aan jouw resultaten aan”. De CTW-methode gedraagt zich ook wat dat betreft voorbeeldig. Uitgewerkt door AIO Paul Volf en toegepast op een internationaal bekende verzameling testbestanden, het zogeheten Calgary corpus, verbeterde de Eindhovense methode met een compressie van 1,8 bit per letter het wereldrecord.

Met dergelijke resultaten is de weg gebaand voor commerciële toepassingen.

Het is heel goed mogelijk dat het CTW-algoritme over een paar jaar de huidige methode zal vervangen. Zelf zullen de onderzoekers daar niet rijk van worden. Exploitatie van een dergelijk idee vereist nou eenmaal het soortinvesteringen en commercieel overwicht dat alleen een groot bedrijf kan bieden. Daarom is een werkverband aangegaan met KPN Research, dat al heeft geleid tot twee patentaanvragen.

De CTW-methode kan wellicht zelfs voor andere doeleinden dan datacompressie worden gebruikt. Specialisten op het gebied van data mining tonen veel belangstelling. Bij data mining gaat het erom in een enorme hoeveelheid gegevens structuur te ontdekken. De gewogen boomstructuur die het resultaat is van toepassing van het CTW-algoritme zou daartoe desleutel kunnen zijn. Al met al is duidelijk dat het prijswinnende artikel slechts het begin is van veel vruchtbaar vervolgonderzoek. De onderzoekers zijn dan ook niet van plan op hun lauweren te gaan rusten, maar juist om er dubbel zo hard tegenaan te gaan. Shtarkov: “When you are happy, you cannot work.”

Boomstructuur

Het idee van een boomstructuur valt te illustreren aan de hand van een quiz. Er zijn twee grabbeltonnen met vragen, één met moeilijke en één met minder moeilijke vragen. Door met een dobbelsteen te gooien bepaalt de speler zelf of de volgende vraag uit de ton met gemakkelijke of de ton met moeilijke vragen getrokken wordt.

Gooit de speler 1, 2 of 3, dan betekent dat een moeilijke vraag, 4, 5 of 6 levert een gemakkelijke vraag op. Er is nu dus fifty-fifty kans op een moeilijke vraag. Dit blijft zo als de vorige vraag die de speler beantwoord heeft uit de ton met moeilijke vragen kwam.

Maar om het de speler niet al te gemakkelijk te maken, veranderen de regels als de vorige vraag gemakkelijk was. De kans op een moeilijke vraag wordt nu verhoogd, en hangt bovendien af van de op één na laatste vraag.

Was die ook gemakkelijk, dan levert alleen een gedobbelde 6 weer een gemakkelijke vraag op. Was de op één na laatste vraag moeilijk, dan betekent het gooien van 5 of 6 een gemakkelijke vraag.

Het verloop van moeilijke en gemakkelijke vragen in deze quiz heeft een boomstructuur (Bij het begrip boomstructuur is het overigens beter om aan stambomen dan aan kastanjebomen te denken). De stamboom van de quiz heeft twee grote takken, 'moeilijk' en 'gemakkelijk'. 'Moeilijk' vertakt zich verder niet meer. Als de vorige vraag moeilijk was, dan staan de regels van het dobbelspel vast en is het niet nodig verder terug te kijken. 'Gemakkelijk' vertakt zich wel, in twee takken: 'gemakkelijk gemakkelijk' en 'gemakkelijk moeilijk'. Dus als de vorige vraag gemakkelijk was, moet je naar de vraag ervoor kijken om te weten welke kant van de vertakking te nemen.

De kans op een moeilijke vraag wordt dus bepaald door het model van de boom (in dit voorbeeld een boom met twee grote takken, waarvan er één zich weer in tweeën splitst) en door de dobbelregels (de parameters) die bij elke tak horen. Als het model bekend is, kun je de statistische eigenschappen van het bestand schatten door naar dat gedeelte van het bestand te kijken dat al ingelezen is. In het voorbeeld zou je de regels van het dobbelspel na een moeilijke vraag kunnen raden door te tellen hoe vaak er in het verleden op een moeilijke vraag een gemakkelijke vraag volgde, en hoe vaak een moeilijke. Als beide mogelijkheden even vaak voorkwamen, is het redelijk aan de nemen dat na een moeilijke vraag met vijftig procent kans opnieuw een moeilijke vraag volgt.