Om gegevens zo snel mogelijk over het Internet te verzenden, worden ze door een webserver eerst zo compact mogelijk voorgesteld (compressie) voordat ze over het netwerk verstuurd worden. Een browser die de gecomprimeerde gegevens ontvangt, moet ze daardoor eerst uitpakken (decompressie) voordat ze kunnen gebruikt worden. Om te begrijpen hoe men tot een dergelijke datacompressie kan komen, moet je eerst weten dat alle gegevens (tekst, afbeeldingen, geluid, video, …) binnen een computer worden voorgesteld als bitstrings — strings van opeenvolgende nullen en enen. Bijvoorbeeld, voor tekstuele data wordt elk symbool (karakter) traditioneel voorgesteld door een bitstring met een vast aantal bits. Als we op die manier elk van de 8 symbolen van het woord internet voorstellen door één enkele byte (8 bits), dan gebruikt de computervoorstelling van dit woord in totaal 64 bits.

Tijdens zijn doctoraat aan MIT ontwikkelde David A. Huffman¹ een algoritme dat elk symbool voorstelt door een unieke bitstring, waarbij het aantal bits kan verschillen van symbool tot symbool. De details van dit algoritme zijn voor deze opgave niet belangrijk, maar de winst bij compressie zit hem in het feit dat symbolen die vaker voorkomen, worden voorgesteld door kortere bitstrings dan symbolen die minder vaak voorkomen. Hieronder zie je bijvoorbeeld een tabel die aangeeft hoe symbolen kunnen omgezet worden naar hun corresponderende bitstringvoorstelling. Daaruit kan je afleiden dat de letter i wordt voorgesteld door de bitstring 1000, de letter e door de bitstring 000, de letter x door de bitstring 10010 en een spatie door de bitstring 111. Een volledige tekst wordt gecomprimeerd door de bitstrings van de opeenvolgende symbolen achter elkaar te zetten. Het woord internet wordt volgens de codering uit onderstaande tabel dus voorgesteld door de bitstring 1000001001100001100000100000110 (31 bits).

Voor het decomprimeren van gecomprimeerde gegevens moeten we rekenen op een ingenieuze eigenschap van de bitstrings die door het algoritme van Huffman worden vastgelegd. Het is namelijk zo dat van alle mogelijke symbolen in het codeerschema, er altijd juist één symbool is waarvan de corresponderende bitstring een prefix (string aan het begin van een andere string) is van het resterende deel van de gecomprimeerde gegevens.

Stel bijvoorbeeld dat we de gecomprimeerde bitstring 1000001001100001100000100000110 willen decomprimeren. Dan stellen we vast dat het symbool i het enige is uit bovenstaande tabel waarvan de corresponderende bitstring (1000) een prefix vormt van de gecomprimeerde bitstring. Daarmee kennen we dus het eerste symbool, en kunnen we de gecomprimeerde bitstring herleiden tot 001001100001100000100000110 door de corresponderende prefix te verwijderen. Opnieuw kunnen we vaststellen dat het symbool n het enige symbool is waarvan de corresponderende bitstring (0010) een prefix vormt van de resterende gecomprimeerde bitstring, waardoor we het tweede symbool gevonden hebben. Door op deze manier prefixen te zoeken en de gecomprimeerde bitstring te reduceren, kunnen we uiteindelijk de volledige bitstring decomprimeren.

Opgave

We vragen je om strings te comprimeren naar bitstrings, en gecomprimeerde bitstrings te decomprimeren naar de oorspronkelijke string volgens het principe van de Huffmancodering. Hierbij worden bitstrings voorgesteld als strings die enkel bestaan uit de karakters 0 en 1. We geven je de bitstrings die gebruikt worden om de verschillende symbolen te comprimeren onder de vorm van een tekstbestand, waarvan elke regel bestaat uit een symbool (één enkel karakter), gevolgd door een tab en de bitstring die gebruikt wordt om dit symbool voor te stellen. Hieronder zie je bijvoorbeeld de inhoud van het tekstbestand met de bitstrings die corresponderen met de symbolen uit bovenstaande tabel. Merk hierbij op dat het symbool op de eerste regel in dit voorbeeld een spatie is.

 	111
a	010
e	000
f	1101
h	1010
i	1000
m	0111
n	0010
s	1011
t	0110
l	11001
o	00110
p	10011
r	11000
u	00111
x	10010

Definieer een klasse ZIP die kan gebruikt worden om strings te comprimeren als bitstrings, en gecomprimeerde bitstrings te decomprimeren naar de oorspronkelijke strings volgens het principe van de Huffmancodering. Bij initialisatie van een object van deze klasse moet de locatie (str) van een tekstbestand doorgegeven worden. Dit bestand moet de codering van de verschillende symbolen bevatten, in het formaat zoals hierboven omschreven. Voorts moeten de objecten van de klasse ZIP minstens de volgende methoden ondersteunen:

• Een methode symbool2bitstring waaraan een symbool (str; één enkel karakter) moet doorgegeven worden. De methode moet de gecomprimeerde bitstring (str) teruggeven die correspondeert met het gegeven symbool. Als het gegeven symbool niet voorkomt in het bestand dat bij initialisatie werd opgegeven, dan moet de methode een AssertionError opwerpen met de boodschap onbekend symbool "x", waarbij x moet ingevuld worden met het gegeven symbool.

• Een methode bitstring2symbool waaraan een bitstring (str) moet doorgegeven worden. De methode moet het symbool (str) teruggeven dat correspondeert met de gegeven bitstring. Als de gegeven bitstring niet voorkomt in het bestand dat bij initialisatie werd opgegeven, dan moet de methode een AssertionError opwerpen met de boodschap ongeldige bitstring.

• Een methode comprimeer waaraan een string (str) moet doorgegeven worden. De methode moet de gecomprimeerde bitstring (str) teruggeven die correspondeert met de gegeven string. Als de gegeven string karakters bevat waarvan de bitstringcodering niet vervat zit in het bestand dat bij initialisatie werd opgegeven, dan moet de methode een AssertionError opwerpen met de boodschap onbekend symbool "x", waarbij x moet ingevuld worden met het eerste (meest linkse) karakter dat niet voorkomt in het bestand.

• Een methode decomprimeer waaraan een gecomprimeerde bitstring (str) moet doorgegeven worden. De methode moet de oorspronkelijke string (str) teruggeven die correspondeert met de gegeven string volgens het schema van de Huffmancodering. Als de gegeven bitstring geen geldige stringvoorstelling heeft volgens het schema van de Huffmancodering, dan moet de methode een AssertionError opwerpen met de boodschap ongeldige bitstring.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand codes.txt² zich in de huidige directory bevindt.

>>> zip = ZIP('codes.txt3')

>>> zip.symbool2bitstring('i')
'1000'
>>> zip.symbool2bitstring('e')
'000'
>>> zip.symbool2bitstring('T')
Traceback (most recent call last):
AssertionError: onbekend symbool "T"

>>> zip.bitstring2symbool('1000')
'i'
>>> zip.bitstring2symbool('000')
'e'
>>> zip.bitstring2symbool('01')
Traceback (most recent call last):
AssertionError: ongeldige bitstring
    
>>> zip.comprimeer('internet')
'1000001001100001100000100000110'
>>> len(zip.comprimeer('internet'))
31
>>> zip.comprimeer('internet explorer')
'1000001001100001100000100000110111000100101001111001001101100000011000'
>>> zip.comprimeer('mozilla firefox')
Traceback (most recent call last):
AssertionError: onbekend symbool "z"

>>> zip.decomprimeer('1000001001100001100000100000110')
'internet'
>>> zip.decomprimeer('1000001001100001100000100000110111000100101001111001001101100000011000')
'internet explorer'
>>> zip.decomprimeer('10000010011000011000001000001101')
Traceback (most recent call last):
AssertionError: ongeldige bitstring
>>> zip.decomprimeer('10000010011000011000000000110')
Traceback (most recent call last):
AssertionError: ongeldige bitstring

Epiloog

Toen David Huffman in 1999 stierf, verloor de wereld één van zijn meest getalenteerde informatici — Huffman was het best gekend voor zijn ontdekking van de Huffmancodering, een techniek die gebruikt wordt in datacompressie. Maar het verloor ook een pionier op het vlak van wiskundige origami, een uitbreiding van de traditionele kunst van het papiervouwen als toepassing van computationele meetkunde, getaltheorie, codeertheorie en lineaire algebra. Dit onderzoeksdomein vindt vandaag de dag steeds meer toepassingen en helpt onderzoekers bij het opvouwen van allerlei zaken zoals eiwitten, airbags voor auto's en ruimtetelescopen.

Huffman werd sterk aangetrokken tot dit werk door zijn onderzoek naar de wiskundige eigenschappen van oppervlakken zonder kromming, waarbij hij bestudeerde hoe papier zich gedraagt in de buurt van plooien en toppen van kegels. Tijdens de laatste twee decennia van zijn leven maakte hij honderden prachtig ingewikkelde papiermodellen waarvan de plooien gebogen waren in plaats van recht.

Maar hij hield zijn onderzoek over papiervouwen grotendeels voor zichzelf. Hij publiceerde slechts één artikel over dit onderwerp⁴, en veel van zijn ontdekkingen gingen verloren bij zijn dood. In 2004 zei laserfysicus Robert Lang hier het volgende over aan de New York Times⁵:

Hij voorzag heel wat zaken die andere mensen pas later ontdekt hebben of nu pas ontdekken. Minstens de helft van wat hij gedaan heeft wijkt af van alles wat ik tot nu toe reeds gezien heb.

Computerwetenschapper Erik Demaine van MIT werkt momenteel met Huffman's familie om zijn ontdekkingen bijeen te sprokkelen en te documenteren⁶.

Tijdens een publieke voordracht in 1979 zei Huffman:

Ik beweer niet dat ik een kunstenaar ben. Ik weet zelfs niet zeker hoe ik kunst zou moeten definiëren, maar ik vind het logisch dat de elegante wiskundige stellingen in verband met papieren oppervlakken ook moeten leiden tot visuele elegantie.