Dr. ir. Frans Willems en dr. ir. Tjallling Tjalkens van de Technische Universiteit Eindhoven zijn onlangs onderscheiden met de ‘1996 IEEE Information Theory Society Paper Award’.
Zij kregen de prijs, samen met de Moskouse wetenschapper dr. Yuri Shtarkov, voor het baanbrekende artikel ‘The Context-Tree Weighting method: Basic Properties’. Hierin wordt een nieuw algoritme voorgelegd, waarmee digitale data compacter kunnen worden beschreven. Nog niet eerder werd de prestigieuze onderscheiding toegekend voor onderzoek dat aan een Nederlandse universiteit of in een industrieel onderzoeksinstituut is uitgevoerd.
Groot nadeel
De hoeveelheid wereldwijd verstuurde en opgeslagen digitale informatie neemt nog steeds met sprongen toe en daarmee ook de behoefte aan betere datacompressie methodieken. Gecomprimeerde data vragen nu eenmaal minder opslagcapaciteit en geven een hogere benutting aan een bestaande infrastructuur. Tot nu toe wordt voor datacompressie gebruik gemaakt van computerprogramma’s met het zogeheten Lempel-Ziv algoritme als basis. Dit algoritme is in 1977 geïntroduceerd en in de jaren tachtig als computerprogramma geïmplementeerd. Deze computerprogramma’s zijn snel, vragen relatief weinig geheugen, maar kennen als groot nadeel dat ze data niet altijd goed comprimeren.
Het nieuwe algoritme van Willems en Tjalkens comprimeert aanmerkelijk beter en efficiënter dan het Lempel-Ziv algoritme. Het is in staat om tijdens het comprimeren alternatieven voor de comprimatie te bekijken. Die worden door het algoritme gewogen en vervolgens al dan niet toegepast.
Voorheen was het onderzoekers nog niet gelukt een algoritme te ontwikkeling die rekening kon houden met de diverse uit de theorie bekende alternatieven voor het comprimeren van files of bestanden. "Veel onderzoekers, vooral uit de hoek van de informatie- en computertechniek, hebben recent geprobeerd om een compressietechniek te bedenken die de competitie aankan met het bekende Lempel-Ziv algoritme. Dit artikel, dat voortkomt uit een fundamenteel begrip van de ‘stochastische complexiteit’ en de ‘algoritmische complexiteit’ en andere informatietheoretische ideeën is waarschijnlijk het eerste echte alternatief voor Lempel-Ziv methodieken, omdat het zowel algoritmisch (dat wil zeggen in rekencapaciteit) als in compressieprestaties daarmee kan wedijver", aldus het nominatie-rapport in haar motivatie voor de toekenning van de prijs.
Perfect
Het algoritme dat door de onderzoekers is ontwikkeld, draagt de toepasselijke naam ‘context-tree weighting algoritme’, is universeel en kan voor alle databronnen worden gebruikt. Het is – dat is inmiddels theoretisch bewezen – het best denkbare algoritme voor compressie van data van bronnen waarvan de statistische eigenschappen niet bekend zijn.
Met het algoritme is compressieverlies tijdens transmissie minimaal en gelijk aan het door onderzoeker Rissanen in 1984 aangetoonde absolute minimale verlies dat bij een universele code bereikt kan worden. Minder verlies tijdens een transmissie kan niet en dus is het algoritme niet te verbeteren. Anders gezegd, met het nieuwe algoritme kan de gecomprimeerde bites zo kort mogelijk worden gehouden.
Het behoeft dan ook geen verbazing te wekken dat het algoritme tijdens de in maart van dit jaar gehouden Data Compression Conference in Snowbird, Utah als beste uit de bus kwam. Tijdens de jaarlijkse conferentie worden door onderzoekers uit de gehele wereld nieuwe algoritmen op het gebied van datacompressie met elkaar vergeleken aan de hand van een standaardpakket files en computerbestanden. In deze ‘wedstrijd’ maakten vele van deze onderzoekers overigens ook gebruik van het ‘context-tree weighting algoritme’.
Traag
Een en ander betekent echter nog niet dat het algoritme op korte termijn in de vorm van computerprogramma’s op de markt verkrijgbaar zal zijn. Een aantal problemen rondom het omzetten van het algoritme in een werkend computerprogramma moet nog worden opgelost. Vooral de snelheid vormt vooralsnog een groot probleem. Het door de onderzoekers geschreven programma haalt het met de huidige computerapparatuur qua snelheid niet bij de programma’s die op basis van het Lempel-Ziv algoritme zijn geschreven.
Het Eindhovense programma zorgt wel voor een twee maal betere datacompressie. Is bij Lempel-Ziv een datacompressie van 3 tot 3.5 bit per karakter bij tekstbestanden mogelijk, in het programma van Willems en Tjalkens wordt dit gereduceerd tot ongeveer 1.9 bit per karakter. Vervolgonderzoek moet dit nog verder omlaag brengen.
Om de prestaties van dit eerste computerprogramma te verbeteren is een samenwerkingsverband aangegaan met KPN Research in Leidschendam. Daardoor is de snelheid ten opzichte van dit zelf geschreven programma met een factor 5 verbeterd, maar het is daarmee altijd nog 50 maal trager dan de bestaande datacompressieprogramma’s op basis van Lempel-Ziv. KPN Research heeft desalniettemin op basis van dit onderzoek twee patenten aangevraagd.
De traagheid heeft veel te maken met de geheugenruimte die het programma vraagt. Het eerste programma dat in Eindhoven is gemaakt had maar liefst 200 Mb aan geheugen nodig. Door de samenwerking is dit inmiddels met een factor 6 verbeterd.
Vijf jaar
De TU Eindhoven is overigens niet de enige plaats waar pogingen worden gedaan het algoritme om te zetten in een goed en snel werkend computerprogramma. Ook in Japan, Australië, Zweden en Israël zijn onderzoekers hiermee bezig, maar ook die hebben nog geen bruikbare programma’s kunnen produceren. Volgens onderzoeker Tjalkens moet het nieuwe algoritme dan ook worden gezien als een tweede generatie datacompressietechniek, die waarschijnlijk pas over ongeveer vijf jaar zal doorbreken.
Het algoritme heeft krachtige computers nodig. In het vervolgonderzoek zal worden bekeken of voor het comprimeren parallelle computers het meest geschikt zijn.
De onderzoekers denken dat over vijf jaar de in de tussentijd op basis van het context-tree weighting algoritme ontwikkelde datacompressieprogramma’s gebruikt zullen gaan worden op plaatsen waar sprake is van zware datastromen: Internet bijvoorbeeld. Of in interbancair verkeer. Een ander toepassingsgebied lijkt datamining te worden. Onderzoekers menen dat het algoritme ook kan worden gebruikt om data in datawarehouses beter te structureren, omdat het in data waarvan de statistiek vooraf niet bekend is uit zichzelf zoekt naar structuur in de data. Dit kan in de praktijk betere analyses, trends en diagnoses opleveren.
