Huffman-kodning forklaret

Computere gemmer som regel hvert bogstav i det samme antal bit, otte i almindelig ASCII. Det er enkelt, men ødselt, fordi nogle bogstaver er langt mere almindelige end andre. I 1951 fandt en studerende den bedste måde at give hvert symbol en kode med sin egen længde på, hyppige symboler korte og sjældne lange, med en konstruktion så enkel, at den kan skrives på få linjer. Huffman-kodning findes nu i næsten hver komprimeret fil, hvert billede og hver lyd, du åbner.

Et Huffman-træ med bogstaverne i ABRACADABRA som blade, kanter markeret med 0 og 1 og den korte kode for A fremhævet
Et Huffman-træ med bogstaverne i ABRACADABRA som blade, kanter markeret med 0 og 1 og den korte kode for A fremhævet

Korte koder til almindelige symboler

Morsekoden brugte allerede idéen i 1830'erne: E, det mest almindelige bogstav på engelsk, er en enkelt prik, mens Q er streg streg prik streg. En sådan kode sparer tid og plads, når nogle symboler forekommer oftere end andre. Men variable længder rejser et problem, som morsekoden løste med pauser: hvordan ved man, hvor én kode slutter, og den næste begynder? Og hvilke længder skal hvert symbol have, for at totalen bliver så lille som muligt?

Præfikskoder

Det første problem forsvinder, hvis ingen kode er begyndelsen af en anden. Med koderne A = 0, B = 10, C = 110 og D = 111 kan bittene 0101100 kun læses som A B C A: så snart de hidtil læste bit danner en kode, er den kode færdig. Sådanne præfikskoder svarer præcis til binære træer med symbolerne i bladene, hvor hver venstre gren står for 0 og hver højre gren for 1. At vælge en kode er at vælge et træ.

Huffmans konstruktion

Start med ét blad pr. symbol, vægtet med hvor ofte det forekommer. Tag de to letteste træer, forbind dem under en ny knude, hvis vægt er deres sum, og gentag, indtil der er ét træ tilbage. Det er hele algoritmen. Sjældne symboler forbindes først og ender dybt i træet med lange koder; almindelige forbindes sidst og bliver tæt på toppen med korte koder. Med en prioritetskø tager det tid proportional med n log n for n symboler.

Hvorfor den er optimal

I et bedst muligt træ kan de to sjældneste symboler altid placeres som søskende på det dybeste niveau: at bytte dem med det, der står der, kan kun gøre totalen kortere. Slå dem sammen til ét symbol med deres samlede vægt, og resten er det samme problem med ét symbol færre, så det grådige trin lukker aldrig af for det bedste svar. Det samlede antal brugte bit er lig med summen af vægtene af alle de indre knuder, og sammenføjningen holder den så lille som muligt.

En semesteropgave i stedet for en eksamen

I 1951 fulgte David Huffman, ph.d.-studerende ved MIT, Robert Fanos kursus i informationsteori. Fano gav sine studerende et valg: gå til den afsluttende eksamen eller skrive en semesteropgave om at finde den mest effektive binære kode. Huffman var tæt på at opgive opgaven, men indså så, at det altid giver det bedste resultat at bygge træet nedefra og op i stedet for at dele oppefra og ned som i Shannon–Fano-metoden. Han offentliggjorde det i 1952; den studerendes metode slog den, hans professor havde udarbejdet sammen med Claude Shannon.

David Huffman, fotograferet som professor ved UC Santa Cruz. Som kandidatstuderende ved MIT fandt han i 1951 sin optimale kode i en semesteropgave til Robert Fanos kursus.
David Huffman, fotograferet som professor ved UC Santa Cruz. Som kandidatstuderende ved MIT fandt han i 1951 sin optimale kode i en semesteropgave til Robert Fanos kursus.
Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.
Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.

Tæt på entropien

Claude Shannon viste, at ingen kode i gennemsnit kan bruge færre bit pr. symbol end kildens entropi. En Huffman-kode når entropien præcis, når hver sandsynlighed er en potens af en halv, og ligger aldrig en hel bit pr. symbol over den. Hullet betyder noget, når ét symbol er meget almindeligt: et symbol med en andel på 99 % kræver stadig mindst én hel bit, selvom det kun bærer omkring 0,015 bit information. Aritmetisk kodning og de asymmetriske talsystemer (ANS) i nyere komprimeringsprogrammer undgår den grænse.

Huffman-koder overalt

Huffman-kodning bruges sjældent alene, men udgør det sidste trin i mange formater. Deflate, i ZIP, gzip og PNG, erstatter først gentagelser med henvisninger og skriver derefter resultatet med Huffman-koder. JPEG bruger dem til de tal, der er tilbage efter transformationen af billedet, MP3 til lyddata og faxmaskiner til længderne af sorte og hvide serier. Formater sender som regel en kanonisk Huffman-kode, hvor kun kodelængderne skal gemmes, fordi selve koderne kan genskabes ud fra dem.

Udforsk det

Åbn Huffman-kodebyggeren for at bygge træet for ABRACADABRA, MISSISSIPPI RIVER, en sætning, du selv skriver, eller en hvilken som helst anden tekst, ét trin ad gangen. Se de to letteste træer blive forbundet ved hvert trin, klik på et blad for at se dets kode, følg et symbol gennem de kodede bit, og sammenlign totalen med en kode med fast længde, UTF-8 og entropien.

Ofte stillede spørgsmål

Hvad er forskellen på Huffman- og Shannon–Fano-kodning?

Shannon–Fano-kodning bygger træet oppefra ved igen og igen at dele symbolerne i to grupper med næsten lige stor vægt. Den er ofte god, men ikke altid optimal. Huffman bygger træet nedefra ved at forbinde de to letteste træer og giver altid den kortest mulige præfikskode.

Har dekoderen brug for træet?

Ja, den skal have den samme kode. Komprimerede filer gemmer den derfor, som regel som en liste over kodelængder for en kanonisk kode, hvilket kun fylder et par dusin byte. For korte tekster kan det ekstra overhead overstige besparelsen; kodebyggeren tæller kun de kodede bit.

Kan Huffman-kodning gøre en fil større?

De kodede symboler fylder aldrig flere bit end en kode med fast længde for de samme symboler. Men kodetabellen skal også gemmes, så for meget korte eller næsten tilfældige data kan resultatet blive lidt større end originalen.

Hvad siger Krafts ulighed?

At der findes en præfikskode med kodelængderne l₁, l₂, …, præcis når summen af 2 opløftet til −l over alle symboler højst er 1. For et fuldstændigt træ, som ethvert Huffman-træ med mindst to symboler, er summen præcis 1.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn Huffman-kodebyggeren