Huffman och LZ

Här är ett exempel på Huffman kodning i C#: http://pastebin.com/8QZW2xZ3

Jag tycker informationen på Wikipedia är väldigt bra, men den är ganska formellt skriven så det är inte det enklast att ta till sig om man inte har kommit i kontakt med området förut.

Men en sak som kan nämnas är att för ett meddelande (en ström av symboler) så finns ett begrepp som kallas informationentropi, http://en.wikipedia.org/wiki/Entropy_(information_theory), som ungefär motsvarar "informationsinnehåll". Huffmankodning är optimal i den meningen att den ger en kodning som är så nära entropin som möjligt.

Formeln för att beräkna informationsentropin finns i Wikipedia-artikeln ovan, http://en.wikipedia.org/wiki/Entropy_(information_theory)#Def.... p(xi) är sannolikheten för att en viss symbol ska komma, alltså motsvarande det som du kallar frekvensen fast normaliserad. Om man använder 2-logaritmen så får man svaret i antalet bitar.

Det är enklast att förklara med ett exempel:
Ett meddelande har tre symboler, A, B och C. Sannolikheten för att de ska dyka upp i meddelandet är p(A) = 1/2, p(B) = 1/3, p(C) = 1/6, så att den totala sannolikheten p(A) + p(B) + p(C) = 1. Entropin i meddelandet är då:
H(X) = -((1/2) * log2(1/2) + (1/3) * log2(1/3) + (1/6) * log2(1/6)) ≈ 1,459 bitar per symbol.

Om man använder Huffman algoritmen så tilldelas symbolerna koderna:
A: 0
B: 10
C: 11
Och om man räknar ut hur många bitar i snitt som kommer användas i meddelandet så blir det:
(1/2) * 1 + (1/3) * 2 + (1/6) * 2 = 1,5 bitar per symbol.

Om man istället använder en kodning som har fast längd (så att alla symboler har koder med lika många bitar) så behövs 2 bitar per symbol i det här fallet.

Det är också värt att säga att detta gäller för förlustfri komprimering; kan man ta bort data så har man extra kunskap kring meddelandet som inte har tagits med i den här modellen, som gör att man kan göra en kortare kodning.