Huffmankodning förklarad
Datorer lagrar oftast varje bokstav med samma antal bitar, åtta i vanlig ASCII. Det är enkelt men slösaktigt, eftersom vissa bokstäver är mycket vanligare än andra. År 1951 hittade en student det bästa sättet att ge varje symbol en kod med egen längd, kort för vanliga symboler och lång för ovanliga, med en konstruktion så enkel att den får plats på några rader. Huffmankodning finns i dag i nästan varje komprimerad fil, bild och ljudfil du öppnar.
Korta koder för vanliga symboler
Morsekoden använde redan idén på 1830-talet: E, den vanligaste bokstaven i engelska, är en enda prick, medan Q är streck streck prick streck. En sådan kod sparar tid och utrymme så snart vissa symboler förekommer oftare än andra. Men varierande längder skapar ett problem som Morse löste med pauser: hur vet man var en kod slutar och nästa börjar? Och vilka längder ska varje symbol få för att totalen ska bli så liten som möjligt?
Prefixkoder
Det första problemet försvinner om ingen kod är början på en annan. Med koderna A = 0, B = 10, C = 110 och D = 111 kan bitarna 0101100 bara läsas som A B C A: så snart de bitar som lästs hittills bildar en kod är den koden fullständig. Sådana prefixkoder motsvarar precis binära träd med symbolerna i löven, där varje gren åt vänster står för 0 och varje gren åt höger för 1. Att välja en kod är att välja ett träd.
Huffmans konstruktion
Börja med ett löv per symbol, viktat med hur ofta den förekommer. Ta de två lättaste träden och slå ihop dem under en ny nod vars vikt är deras summa, och upprepa tills ett enda träd är kvar. Det är hela algoritmen. Ovanliga symboler slås ihop först och hamnar djupt ner i trädet, med långa koder; vanliga slås ihop sist och stannar nära toppen, med korta koder. Med en prioritetskö tar det tid proportionell mot n log n för n symboler.
Varför den är optimal
I ett bästa möjliga träd kan de två ovanligaste symbolerna alltid placeras som syskon på den djupaste nivån: att byta plats med det som finns där kan bara korta totalen. Slå ihop dem till en symbol med deras sammanlagda vikt, så är resten samma problem med en symbol mindre, och därför stänger det giriga steget aldrig vägen till det bästa svaret. Det totala antalet bitar är lika med summan av vikterna för alla inre noder, och sammanslagningarna håller den så liten som möjligt.
En uppsats i stället för en tenta
År 1951 läste David Huffman, doktorand vid MIT, Robert Fanos kurs i informationsteori. Fano lät studenterna välja: skriva sluttentan eller skriva en uppsats om hur man hittar den mest effektiva binära koden. Huffman höll på att ge upp uppsatsen, men såg sedan att om man bygger trädet nerifrån och upp, i stället för att dela upp det uppifrån och ner som i Shannon–Fano-metoden, blir resultatet alltid bäst. Han publicerade den 1952; studentens metod slog den som hans professor hade tagit fram tillsammans med Claude Shannon.
Nära entropin
Claude Shannon visade att ingen kod i genomsnitt kan använda färre bitar per symbol än källans entropi. En Huffmankod når entropin exakt när varje sannolikhet är en potens av en halv, och ligger aldrig en hel bit per symbol över den. Gapet spelar roll när en symbol är mycket vanlig: en symbol med en andel på 99 % behöver ändå minst en hel bit, fast den bara bär ungefär 0,015 bitar information. Aritmetisk kodning och de asymmetriska talsystemen i nyare komprimerare undviker den gränsen.
Huffmankoder överallt
Huffmankodning används sällan ensam men utgör sista steget i många format. Deflate, som finns i ZIP, gzip och PNG, ersätter först upprepningar med referenser och skriver sedan resultatet med Huffmankoder. JPEG använder dem för talen som blir kvar efter bildens transform, MP3 för sina ljuddata och faxmaskiner för längderna på svarta och vita skurar. Format skickar oftast en kanonisk Huffmankod, där bara kodlängderna behöver lagras, eftersom själva koderna kan byggas upp igen utifrån dem.
Utforska
Öppna Huffmankodbyggaren för att bygga trädet för ABRACADABRA, MISSISSIPPI RIVER, en egen mening eller vilken annan text som helst, ett steg i taget. Se de två lättaste träden slås ihop i varje steg, klicka på ett löv för att se dess kod, följ en symbol genom de kodade bitarna och jämför totalen med en kod med fast längd, UTF-8 och entropin.
Ofta ställda frågor
Vad är skillnaden mellan Huffmankodning och Shannon–Fano-kodning?
Shannon–Fano-kodning bygger trädet uppifrån genom att om och om igen dela symbolerna i två grupper med nästan lika stor vikt. Den är ofta bra men inte alltid optimal. Huffman bygger trädet nerifrån genom att slå ihop de två lättaste träden, och ger alltid den kortaste möjliga prefixkoden.
Behöver avkodaren trädet?
Ja, den behöver samma kod. Komprimerade filer lagrar den därför, oftast som en lista med kodlängder för en kanonisk kod, vilket bara tar några dussin byte. För korta texter kan det tillägget väga tyngre än vinsten; byggaren räknar bara de kodade bitarna.
Kan Huffmankodning göra en fil större?
De kodade symbolerna tar aldrig fler bitar än en kod med fast längd för samma symboler. Men kodtabellen måste också lagras, så för mycket korta eller nästan slumpmässiga data kan resultatet bli något större än originalet.
Vad säger Krafts olikhet?
Att en prefixkod med kodlängderna l₁, l₂, … finns precis när summan av 2 upphöjt till −l över alla symboler är högst 1. För ett fullständigt träd, som varje Huffmanträd med minst två symboler, är summan exakt 1.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna Huffmankodbyggaren