Met meer dan 9 miljard gigabyte aan informatie die elke dag over het internet reist, zijn onderzoekers voortdurend op zoek naar nieuwe manieren om gegevens in kleinere pakketten te comprimeren. Geavanceerde technieken richten zich op lossy-benaderingen, die compressie bereiken door opzettelijk informatie van een transmissie te "verliezen". Zo heeft Google onlangs een lossy-strategie onthuld waarbij de verzendende computer details uit een afbeelding laat vallen en de ontvangende computer kunstmatige intelligentie gebruikt om de ontbrekende delen te raden. Zelfs Netflix gebruikt een lossy-benadering, waarbij de videokwaliteit wordt verlaagd wanneer het bedrijf detecteert dat een gebruiker kijkt op een apparaat met een lage resolutie.

Er wordt momenteel echter zeer weinig onderzoek gedaan naar verliesloze strategieën, waarbij transmissies kleiner worden gemaakt, maar er geen substantie wordt opgeofferd. De reden? Lossless benaderingen zijn al opmerkelijk efficiënt. Ze voeden alles, van de JPEG-beeldstandaard tot het alomtegenwoordige softwarehulpprogramma PKZip. En het komt allemaal door een afgestudeerde student die gewoon op zoek was naar een uitweg uit een zwaar eindexamen.

Zeventig jaar geleden bood Robert Fano, een professor aan het Massachusetts Institute of Technology, de studenten in zijn informatietheorieklas de keuze: een traditioneel eindexamen afleggen of een toonaangevend algoritme voor datacompressie verbeteren. Fano heeft zijn studenten misschien wel of niet verteld dat hij de auteur was van dat bestaande algoritme, of dat hij al jaren op zoek was naar een verbetering. Wat we wel weten is dat Fano zijn leerlingen de volgende uitdaging aanbood.

Denk aan een bericht dat bestaat uit letters, cijfers en leestekens. Een eenvoudige manier om zo'n bericht te coderen, is door elk teken een uniek binair getal toe te wijzen. Een computer kan bijvoorbeeld de letter A weergeven als 01000001 en een uitroepteken als 00100001. Dit resulteert in codes die gemakkelijk te ontleden zijn - elke acht cijfers of bits komen overeen met één uniek teken - maar vreselijk inefficiënt, omdat hetzelfde nummer van binaire cijfers wordt gebruikt voor zowel gewone als ongebruikelijke invoer. Een betere benadering zou zoiets zijn als morsecode, waarbij de frequente letter E wordt weergegeven door slechts een enkele punt, terwijl de minder gebruikelijke Q het langere en meer arbeidsintensieve streepje-streepje-punt-streepje vereist.

Maar morsecode is ook inefficiënt. Zeker, sommige codes zijn kort en andere zijn lang. Maar omdat de lengte van codes varieert, kunnen berichten in morsecode alleen worden begrepen als er korte perioden van stilte zijn tussen elke overdracht van tekens. Inderdaad, zonder die kostbare pauzes zouden ontvangers het morsebericht dash dot-dash-dot dot-dot dash dot (“trite”) niet kunnen onderscheiden van dash dot-dash-dot dot-dot-dash dot (“true” ).

Fano had dit deel van het probleem opgelost. Hij realiseerde zich dat hij codes van verschillende lengtes kon gebruiken zonder dure spaties nodig te hebben, zolang hij maar nooit hetzelfde cijferpatroon gebruikte als zowel een volledige code als het begin van een andere code. Als de letter S bijvoorbeeld zo gewoon was in een bepaald bericht dat Fano er de extreem korte code 01 aan toekende, dan zou geen enkele andere letter in dat bericht gecodeerd zijn met iets dat met 01 begon; codes als 010, 011 of 0101 zouden allemaal verboden zijn. Hierdoor kon het gecodeerde bericht zonder enige dubbelzinnigheid van links naar rechts worden gelezen. Bijvoorbeeld, met de letter S toegewezen aan 01, de letter A toegewezen aan 000, de letter M toegewezen aan 001 en de letter L toegewezen aan 1, plotseling kan het bericht 0100100011 onmiddellijk worden vertaald in het woord "klein", ook al wordt L weergegeven door één cijfer, S met twee cijfers en de andere letters met elk drie.

Om de codes daadwerkelijk te bepalen, bouwde Fano binaire bomen, waarbij elke noodzakelijke letter aan het einde van een visuele tak werd geplaatst. De code van elke letter werd vervolgens gedefinieerd door het pad van boven naar beneden. Als het pad naar links aftakte, voegde Fano een 0 toe; rechtertakken kregen een 1. De boomstructuur maakte het voor Fano gemakkelijk om die ongewenste overlappingen te vermijden: zodra Fano een letter in de boom plaatste, zou die tak eindigen, wat betekent dat geen enkele toekomstige code op dezelfde manier kan beginnen.

Om te beslissen welke letters waar zouden komen, had Fano elk mogelijk patroon uitputtend kunnen testen voor maximale efficiëntie, maar dat zou onpraktisch zijn geweest. Dus in plaats daarvan ontwikkelde hij een benadering: voor elk bericht zou hij de relevante letters op frequentie ordenen en vervolgens letters toewijzen aan vertakkingen, zodat de letters aan de linkerkant in een bepaald vertakkingspaar ongeveer evenveel keer in het bericht werden gebruikt als de brieven aan de rechterkant. Op deze manier zouden veelgebruikte tekens op kortere, minder dichte takken terechtkomen. Een klein aantal hoogfrequente letters zou altijd een groter aantal lagerfrequente letters compenseren.

Het resultaat was een opmerkelijk effectieve compressie. Maar het was slechts een benadering; er moest een betere compressiestrategie bestaan. Dus daagde Fano zijn studenten uit om het te vinden.

Fano had zijn bomen van boven naar beneden gebouwd, waarbij hij zoveel mogelijk symmetrie tussen de gepaarde takken handhaafde. Zijn student David Huffman zette het proces op zijn kop en bouwde dezelfde soorten bomen, maar dan van onderaf. Huffmans inzicht was dat, wat er verder ook gebeurt, in een efficiënte code de twee minst voorkomende karakters de twee langste codes zouden moeten hebben. Dus Huffman identificeerde de twee minst voorkomende karakters, groepeerde ze samen als een vertakkend paar en herhaalde het proces, dit keer op zoek naar de twee minst voorkomende ingangen tussen de resterende karakters en het paar dat hij zojuist had gebouwd.

Overweeg een bericht waar de Fano-aanpak hapert. In "klaslokaal" verschijnt O vier keer en S/C/H/L/R/M elk één keer. Fano's evenwichtsbenadering begint met het toewijzen van de O en een andere letter aan de linkertak, waarbij het vijf totale gebruik van die letters de vijf verschijningsvormen van de resterende letters in evenwicht houdt. Het resulterende bericht vereist 27 bits.

Huffman daarentegen begint met twee van de ongebruikelijke letters - zeg R en M - en groepeert ze bij elkaar, waarbij hij het paar behandelt als een enkele letter.

Zijn bijgewerkte frequentiekaart biedt hem vervolgens vier keuzes: de O die vier keer verschijnt, de nieuwe gecombineerde RM-node die twee keer functioneel wordt gebruikt, en de enkele letters S, C, H en L. Huffman kiest opnieuw de twee minst voorkomende opties, overeenkomend met (zeg maar) H met L.

De kaart wordt weer bijgewerkt: O heeft nog steeds een gewicht van 4, RM en HL hebben nu elk een gewicht van 2, en de letters S en C staan ​​op zichzelf. Huffman gaat vanaf daar verder, waarbij hij in elke stap de twee minst frequente opties groepeert en vervolgens zowel de boomstructuur als de frequentiegrafiek bijwerkt.

Uiteindelijk wordt 'schoollokaal' 11101111110000110110000101, waarmee de Fano-benadering van bovenaf een beetje wordt geschrapt.

Een bit klinkt misschien niet veel, maar zelfs kleine besparingen groeien enorm wanneer ze worden opgeschaald met miljarden gigabytes.

De aanpak van Huffman is inderdaad zo krachtig gebleken dat tegenwoordig bijna elke lossless compressiestrategie het inzicht van Huffman geheel of gedeeltelijk gebruikt. PKZip nodig om een ​​Word-document te comprimeren? De eerste stap omvat nog een andere slimme strategie om herhaling te identificeren en daardoor de berichtgrootte te comprimeren, maar de tweede stap is om het resulterende gecomprimeerde bericht te nemen en door het Huffman-proces te leiden. Een afbeelding opslaan als JPEG? Uw computer vertaalt de afbeelding eerst in een op tekst gebaseerde weergave en gebruikt vervolgens opnieuw Huffman-codering om die tekst te comprimeren.

Niet slecht voor een project dat oorspronkelijk werd ingegeven door de wens van een afgestudeerde student om een ​​eindexamen over te slaan.