| Symbol | Antal | Kode | Bit | Bit i alt |
|---|
Huffman-kodebygger
Hvorfor skal et almindeligt bogstav som e fylde lige så mange bit som et sjældent som q? Huffman-kodning giver hyppige symboler korte koder og sjældne lange koder, og gør det på den bedst mulige måde. Skriv en tekst, eller vælg et eksempel, og byg dens Huffman-træ ét trin ad gangen: de to letteste træer forbindes under en ny knude, igen og igen, indtil der er ét træ tilbage. Så staver hver sti fra toppen en kode, og du kan følge hvert symbol gennem de kodede bit. Skriv en tekst, eller vælg et eksempel. Hvert symbol starter som et blad med sit antal. Gå trin for trin gennem opbygningen: hvert trin forbinder de to letteste træer under en ny knude med deres sum, indtil der er ét træ tilbage. Derefter giver stien fra toppen til et blad dets kode, 0 for venstre og 1 for højre. Klik på et blad, en række eller et stykke af bittene for at følge ét symbol, og sammenlign totalen med en kode med fast længde og med entropien.
Sådan virker det
- Skriv eller indsæt en tekst, eller vælg et eksempel som ABRACADABRA eller MISSISSIPPI RIVER.
- Gå gennem opbygningen med »Næste trin«, eller tryk på »Afspil«: hvert trin forbinder de to letteste træer under en knude med deres sum.
- Når træet er færdigt, kan du klikke på et blad, en række i tabellen eller et stykke af bittene for at følge ét symbol og sammenligne totalerne i felterne.
Sådan bygges træet
Tæl, hvor ofte hvert symbol forekommer, og gør hvert af dem til et træ med et enkelt blad, vægtet med sit antal. Gentag så ét enkelt trin: tag de to træer med de mindste vægte, og hæng dem under en ny knude, hvis vægt er deres sum. Hvert trin efterlader ét træ færre, så efter n − 1 trin for n symboler er der ét træ tilbage. De sjældne symboler blev forbundet først og sidder dybt nede; de almindelige blev forbundet sent og sidder tæt på toppen.
Aflæsning af koderne
Gå ned fra toppen: et skridt til venstre tilføjer et 0, et skridt til højre et 1. Stien til et blad er det symbols kode. Fordi symboler kun sidder i bladene, er ingen kode begyndelsen af en anden, så en række bit kan afkodes uden skilletegn: følg bittene ned gennem træet, og hver gang du når et blad, skriver du dets symbol og begynder forfra ved toppen. For ABRACADABRA skal Huffman bruge 23 bit mod 33 for en fast kode på 3 bit pr. bogstav.
Ofte stillede spørgsmål
Hvorfor er Huffman-koden den bedst mulige?
Blandt alle koder, der giver hvert symbol sin egen streng af hele bit, har ingen en kortere total for de givne antal. Beviset følger konstruktionen: i en optimal kode kan de to sjældneste symboler altid gøres til søskende på det dybeste niveau, og når de forbindes, står man tilbage med et mindre problem af samme slags. Det samlede antal bit er lig med summen af vægtene af alle træets indre knuder.
Hvad er en præfikskode?
En kode, hvor intet kodeord er begyndelsen af et andet, som 0, 10, 110 og 111. Den egenskab lader en dekoder læse en strøm af bit uden skilletegn, fordi den altid ved, hvor et kodeord slutter. Enhver Huffman-kode er en præfikskode: symbolerne sidder kun i træets blade.
Er Huffman-træet entydigt?
Ikke helt: når to træer har samme vægt, kan hvert af dem tages først, og venstre og højre kan byttes om. Forskellige valg giver forskellige koder, men altid det samme samlede antal bit. Kodebyggeren vælger altid på samme måde ved lige vægt, så en tekst altid giver det samme træ.
Hvor tæt kommer Huffman på entropien?
Den gennemsnitlige kodelængde er mindst entropien og mindre end én bit over den. Den er lig med entropien, når hver sandsynlighed er en potens af en halv, som i eksemplet med halverede antal. Aritmetisk kodning og moderne range coders undgår grænsen med hele bit og kommer endnu tættere på.
Bliver min tekst sendt nogen steder hen?
Nej. Træet og koderne beregnes i din browser, og din tekst bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor