Kod som ett träd
En prefixfri kod mappar till ett binärt träd: roten representerar början på avkodning, vänstra grenar representerar bit 0, högra grenar representerar bit 1, och löv representerar kompletta kodord.
Den geometriska begränsningen: varje löv avslutar en väg från rot till löv. Inget löv kan ha en efterkommare (om det gjorde det skulle dess kodord vara ett prefix för efterkommandes kodord, vilket bryter mot egenskapen prefixfritt).
Detta ger Krafts olikhet en geometrisk tolkning:
Varje löv på djupet d 'upptar' en bråkdel 2^(−d) av trädet totala kapacitet. En komplett binärt träd på djupet D har kapaciteten 1. En prefixfri kod använder löv på olika djup; Kraft-summan mäter total ockupering.
Kraft-summa = 1: komplett kod (varje väg slutar på ett löv — perfekt packning).
Kraft-summa < 1: ofullständig kod (viss trädkapacitet är oanvänd — fler symboler kunde läggas till).
Kraft-summa > 1: omöjligt för prefixfria koder (vissa vägar måste dela ett löv).
Djupare löv = längre koder = mindre kapacitet
Ett löv på djupet 1 använder hälften av trädet kapacitet (2^(−1) = 0,5).
Ett löv på djupet 3 använder en åttondel (2^(−3) = 0,125).
Att placera ett kort kodord högt upp i trädet blockerar alla dess efterkommande från att användas — du byter ett kort kodord mot många potentiella längre koder.
Att bygga ett prefixfritt träd
Överväg 5 symboler med längder l = {1, 2, 3, 3, 3}. Kraft-summa = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Detta överstiger 1: dessa längder är inkompatibla med en prefixfri kod. Minst en längd måste öka.
Åtgärd: ändra l_1 från 1 till 2. Nya längder {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Giltigt, men ofullständigt.
Åtgärd: ändra l_1 från 2 till 2, lägg till l_2 = 3 för att använda återstående kapacitet. Kraft = 0,875; återstående = 0,125 = 2^(−3): plats för ett löv till på djupet 3.
Varför entropi begränsar kodlängd
Krafts olikhet begränsar kodstruktur (längder måste passa i trädet). Shannons entropi begränsar kodeffektivitet (genomsnittlig längd kan inte slå en teoretisk gräns).
Optimala kodlängder. För en symbol med sannolikhet p_i är den ideala kodlängden log₂(1/p_i). Sällsynta symboler förtjänar långa koder; frekventa symboler förtjänar korta. Detta speglar Kraft-likheten: 2^(−l_i) = p_i när l_i = log₂(1/p_i).
Men log₂(1/p_i) är sällan ett heltal. Att avrunda upp till ⌈log₂(1/p_i)⌉ ger Huffman-längden, som uppfyller H ≤ L < H + 1.
Geometrisk läsning. Plotta varje symbol som en punkt på det binära trädet på djupet l_i. Kraft-summan mäter total lövtäckning. Entropi mäter det viktade genomsnittliga djupet, viktad efter sannolikhet. Shannons teorem: sannolikhetsviktat genomsnittligt djup ≥ sannolikhetsviktad informationsinnehål.
Verifikation av entropiföreningsgräns
Det utarbetade exemplet: p = [1/2, 1/4, 1/8, 1/8] för symboler {A, B, C, D}.
Optimala längder: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Dessa är alla heltal — en perfekt matchning. Huffman-kod: A=0, B=10, C=110, D=111.
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 0,5 + 0,5 + 0,375 + 0,375 = 1,75.
H = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75. L = H exakt: optimal kod.
Ett fullständigt utarbetat exempel
Fullständig pipeline: givet sannolikheter, beräkna entropi, verifiera att en kod uppfyller gränsen.
Källa: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bitar (beräknat ovan).
En naiv blockkod: 4 symboler → 2 bitar vardera → L = 2,0. Overhead över entropi: 2,0 − 1,75 = 0,25 bitar/symbol = 12,5% slöseri.
Koden med variabel längd sparar 12,5% jämfört med fast längd. För stora meddelanden är detta väsentligt.
Entropitakt för engelska. Shannon uppskattade entropien för skriven engelska till cirka 1,0 till 1,3 bitar per tecken, trots att 5-bitars ASCII-koder används. Det 4:1-förhållandet återspeglar den massiva redundansen i naturligt språk — vanliga bokstäver klumpas, ord upprepas, grammatik begränsar sekvenser.
Kompression kan inte slå entropi
Kompressionsförhållande: H / (blockkodlängd). För vårt exempel: 1,75/2,0 = 0,875 — 87,5% effektivitet.
Kan du komprimera vidare? Endast genom att använda kontext: om du kodar par eller treor av symboler tillsammans, kan den gemensamma entropien H(X,Y) vara mindre än 2·H(X) på grund av statistiska beroenden. Detta är utökningen av den bullerfria kodningsteoremet till n-gram.