Huffmankod
Kod med fast längd
Sparat
Entropi

Symbol Antal Kod Bitar Bitar totalt

Mer information om Huffmankodning

Huffmankodbyggare

Varför ska en vanlig bokstav som e ta lika många bitar som en ovanlig som q? Huffmankodning ger vanliga symboler korta koder och ovanliga långa koder, och gör det på bästa möjliga sätt. Skriv en text eller välj ett exempel och bygg dess Huffmanträd ett steg i taget: de två lättaste träden slås ihop under en ny nod, om och om igen, tills bara ett träd är kvar. Sedan bildar varje väg från toppen en kod, och du kan följa varje symbol genom de kodade bitarna. Skriv en text eller välj ett exempel. Varje symbol börjar som ett löv med sitt antal. Stega dig igenom bygget: varje steg slår ihop de två lättaste träden under en ny nod med deras summa, tills bara ett träd är kvar. Sedan ger vägen från toppen till ett löv dess kod, 0 för vänster och 1 för höger. Klicka på ett löv, en rad eller en del av bitföljden för att följa en symbol, och jämför totalen med en kod med fast längd och med entropin.

Hur det fungerar

  1. Skriv eller klistra in en text, eller välj ett exempel som ABRACADABRA eller MISSISSIPPI RIVER.
  2. Stega dig igenom bygget med Nästa steg, eller tryck på Spela: varje steg slår ihop de två lättaste träden under en nod med deras summa.
  3. När trädet är klart klickar du på ett löv, en rad i tabellen eller en del av bitföljden för att följa en symbol, och jämför totalerna i rutorna.

Så byggs trädet

Räkna hur ofta varje symbol förekommer och gör var och en till ett träd med ett enda löv, viktat med sitt antal. Upprepa sedan ett enkelt steg: ta de två träden med minst vikt och häng dem under en ny nod vars vikt är deras summa. Varje steg ger ett träd mindre, så efter n − 1 steg för n symboler återstår ett enda träd. De ovanliga symbolerna slogs ihop först och sitter långt ner; de vanliga slogs ihop sent och sitter nära toppen.

Att läsa av koderna

Gå nedåt från toppen: ett steg åt vänster lägger till en 0:a, ett steg åt höger en 1:a. Vägen till ett löv är den symbolens kod. Eftersom symbolerna bara sitter i löven är ingen kod början på en annan, så en följd av bitar kan avkodas utan avgränsare: följ bitarna ner genom trädet, och varje gång du når ett löv skriver du dess symbol och börjar om vid toppen. För ABRACADABRA behöver Huffman 23 bitar, mot 33 för en fast kod med 3 bitar per bokstav.

Ofta ställda frågor

Varför är Huffmankoden den bästa möjliga?

Av alla koder som ger varje symbol en egen följd av hela bitar har ingen en kortare total för de givna antalen. Beviset följer konstruktionen: i en optimal kod kan de två ovanligaste symbolerna alltid göras till syskon på den djupaste nivån, och att slå ihop dem lämnar ett mindre problem av samma slag. Det totala antalet bitar är lika med summan av vikterna för alla inre noder i trädet.

Vad är en prefixkod?

En kod där inget kodord är början på ett annat, till exempel 0, 10, 110 och 111. Den egenskapen gör att en avkodare kan läsa en ström av bitar utan avgränsare, eftersom den alltid vet var ett kodord slutar. Varje Huffmankod är en prefixkod: symbolerna sitter bara i trädets löv.

Är Huffmanträdet entydigt?

Inte riktigt: när två träd har samma vikt kan vilket som helst av dem tas först, och vänster och höger kan byta plats. Olika val ger olika koder, men alltid samma totala antal bitar. Byggaren avgör lika vikter alltid på samma sätt, så en text ger alltid samma träd.

Hur nära entropin kommer Huffman?

Den genomsnittliga kodlängden är minst lika stor som entropin och mindre än en bit över den. Den är lika med entropin när varje sannolikhet är en potens av en halv, som i exemplet med halverade antal. Aritmetisk kodning och moderna intervallkodare undviker gränsen med hela bitar och kommer ännu närmare.

Skickas min text någonstans?

Nej. Trädet och koderna beräknas i din webbläsare, och din text sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor