Code als Baum
Ein präfixfreier Code wird auf einen Binärbaum abgebildet: die Wurzel repräsentiert den Anfang der Decodierung, linke Äste repräsentieren Bit 0, rechte Äste repräsentieren Bit 1, und Blätter repräsentieren vollständige Codewörter.
Die geometrische Beschränkung: jedes Blatt beendet einen Pfad von der Wurzel zum Blatt. Kein Blatt kann einen Nachkommen haben (wenn es das täte, wäre sein Codewort ein Präfix des Codewortes des Nachkommen und würde die Präfixfreiheit verletzen).
Dies gibt der Kraftschen Ungleichung eine geometrische Interpretation:
Jedes Blatt in der Tiefe d 'belegt' einen Bruchteil 2^(−d) der gesamten Baumkapazität. Die Gesamtkapazität eines vollständigen Binärbaums der Tiefe D ist 1. Ein präfixfreier Code verwendet Blätter in verschiedenen Tiefen; die Kraftsumme misst die gesamte Belegung.
Kraftsumme = 1: vollständiger Code (jeder Pfad endet in einem Blatt — perfekte Packung).
Kraftsumme < 1: unvollständiger Code (einige Baumkapazität ungenutzt — weitere Symbole könnten hinzugefügt werden).
Kraftsumme > 1: unmöglich für präfixfreie Codes (einige Pfade würden sich ein Blatt teilen müssen).
Tiefere Blätter = Längere Codes = Weniger Kapazität
Ein Blatt in der Tiefe 1 nutzt die Hälfte der Baumkapazität (2^(−1) = 0,5).
Ein Blatt in der Tiefe 3 nutzt ein Achtel (2^(−3) = 0,125).
Das Platzieren eines kurzen Codewortes hoch im Baum blockiert alle seine Nachkommen — Sie tauschen einen kurzen Code gegen viele potenzielle längere Codes.
Aufbau eines präfixfreien Baums
Betrachten Sie 5 Symbole mit Längen l = {1, 2, 3, 3, 3}. Kraftsumme = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Dies überschreitet 1: diese Längen sind mit einem präfixfreien Code nicht kompatibel. Mindestens eine Länge muss erhöht werden.
Behebung: ändern Sie l_1 von 1 auf 2. Neue Längen {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Gültig, aber unvollständig.
Behebung: ändern Sie l_1 von 2 zu 2, fügen Sie l_2 = 3 hinzu, um die verbleibende Kapazität zu nutzen. Kraft = 0,875; verbleibend = 0,125 = 2^(−3): Platz für ein weiteres Blatt der Tiefe 3.
Warum Entropie die Codelänge begrenzt
Krafts Ungleichung beschränkt die Codestruktur (Längen müssen in den Baum passen). Shannons Entropie beschränkt die Codeeffizienz (durchschnittliche Länge kann eine theoretische Untergrenze nicht unterschreiten).
Optimale Codelängen. Für ein Symbol mit Wahrscheinlichkeit p_i ist die ideale Codelänge log₂(1/p_i). Seltene Symbole verdienen lange Codes; häufige Symbole verdienen kurze. Dies spiegelt die Kraftgleichung wider: 2^(−l_i) = p_i wenn l_i = log₂(1/p_i).
Aber log₂(1/p_i) ist selten eine ganze Zahl. Das Aufrunden auf ⌈log₂(1/p_i)⌉ ergibt die Huffman-Länge, die H ≤ L < H + 1 erfüllt.
Geometrische Lesart. Zeichnen Sie jedes Symbol als einen Punkt im Binärbaum in der Tiefe l_i. Die Kraftsumme misst die gesamte Blattabdeckung. Entropie misst die gewichtete durchschnittliche Tiefe, gewichtet nach Wahrscheinlichkeit. Shannons Theorem: wahrscheinlichkeitsgewichtete durchschnittliche Tiefe ≥ wahrscheinlichkeitsgewichteter Informationsgehalt.
Verifikation der Entropiegrenze
Das ausgearbeitete Beispiel: p = [1/2, 1/4, 1/8, 1/8] für Symbole {A, B, C, D}.
Optimale Längen: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Dies sind alle ganze Zahlen — eine perfekte Übereinstimmung. Huffman-Code: 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 genau: optimaler Code.
Ein vollständiges ausgearbeitetes Beispiel
Komplette Pipeline: Angesichts von Wahrscheinlichkeiten, berechnen Sie Entropie, überprüfen Sie, dass ein Code die Grenze erfüllt.
Quelle: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 Bits (berechnet oben).
Ein naiver Blockcode: 4 Symbole → 2 Bits pro Stück → L = 2,0. Overhead über Entropie: 2,0 − 1,75 = 0,25 Bits/Symbol = 12,5% Verschwendung.
Der Code mit variabler Länge spart 12,5% im Vergleich zu fester Länge. Bei großen Nachrichten ist dies erheblich.
Entropierate des Englischen. Shannon schätzte die Entropie des geschriebenen Englischen auf etwa 1,0 bis 1,3 Bits pro Zeichen, trotz Verwendung von 5-Bit-ASCII-Codes. Dieses 4:1-Verhältnis spiegelt die enorme Redundanz in natürlicher Sprache wider — häufige Buchstaben häufen sich, Wörter wiederholen sich, Grammatik begrenzt Sequenzen.
Kompression kann Entropie nicht besiegen
Kompressionsverhältnis: H / (Blockcodelänge). Für unser Beispiel: 1,75/2,0 = 0,875 — 87,5% Effizienz.
Können Sie weiter komprimieren? Nur durch Kontextnutzung: Wenn Sie Paare oder Tripel von Symbolen zusammen codieren, kann die gemeinsame Entropie H(X,Y) aufgrund statistischer Abhängigkeiten weniger als 2·H(X) sein. Dies ist die Erweiterung des fehlerfreien Codierungssatzes auf n-Gramme.