Code als Baum
Ein präfixfreier Code entspricht einem binären Baum: Der Wurzelknoten repräsentiert den Anfang der Dekodierung, linke Zweige stehen für den Bit 0, rechte Zweige für den Bit 1 und Blätter für vollständige Codewörter.
Die geometrische Einschränkung: Jedes Blatt endet eine Wurzelblatt-Pfad. Kein Blatt kann einen Abkömmling haben (wenn es einen hätte, wäre sein Codewort ein Präfix des Abkömmlings-Codeworts, was dem Präfixfreieigenschaft widerspricht).
Dies gibt der Krafthäufigkeit eine geometrische Interpretation:
Jedes Blatt in einer Tiefe d 'belegt' einen Bruchteil 2^(−d) des gesamten Baumkapazitäten. Die gesamte Kapazität eines vollständigen binären Baums in einer Tiefe D beträgt 1. Ein Präfixfreecode verwendet Blätter an verschiedenen Tiefen; die Krafthäufigkeit misst die Gesamtnutzung.
Krafthäufigkeit = 1: vollständiger Code (jeder Weg endet an einem Blatt - perfekte Verpackung).
Krafthäufigkeit < 1: unvollständiger Code (einige Baumkapazitäten werden nicht genutzt - können mehr Symbole hinzufügen).
Krafthäufigkeit > 1: unmöglich für Präfixfreecodes (müssen sich einige Pfade teilen).
Tiefere Blätter = Längere Codes = Weniger Kapazität
Ein Blatt in einer Tiefe 1 verwendet die Hälfte der Baumkapazität (2^(−1) = 0,5).
Ein Blatt in einer Tiefe 3 verwendet einen Achtfarthel (2^(−3) = 0,125).
Ein kurzes Codewort hoch in den Baum legen, blockiert alle seine Abkömmlinge von der Verwendung - Sie tauschen ein kurzes Code gegen viele potenzielle längere Codes aus.
Erstellen eines Präfixfreien Baums
Überlegen Sie 5 Symbole mit Längen l = {1, 2, 3, 3, 3}. Krafthäufigkeit = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Dies übersteigt 1: Diese Längen sind mit einem Präfixfreecode nicht kompatibel. Mindestens eine Länge muss erhöht werden.
Korrektur: Ändern Sie l_1 von 1 auf 2. Neue Längen {2, 2, 3, 3, 3}: Krafthäufigkeit = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Gültig, aber unvollständig.
Korrektur: Ändern Sie l_1 von 2 auf 2, fügen Sie l_2 = 3 hinzu, um die verbleibende Kapazität zu nutzen. Krafthäufigkeit = 0,875; verbleibend = 0,125 = 2^(−3): Platz für ein weiteres Blatt in einer Tiefe-3.
Warum bindet Entropie die Codierlänge
Die Ungleichheit von Kraft beschränkt die Codierstruktur (Längen müssen im Baum passen). Die Entropie von Shannon beschränkt die Codiereffizienz (durchschnittliche Länge kann ein theoretisches Dach nicht überschreiten).
Optimale Codierlängen. Für ein Symbol mit Wahrscheinlichkeit p_i ist die ideale Codierlänge log₂(1/p_i). Seltene Symbole verdienen lange Codes; häufige Symbole verdienen kurze. Dies spiegelt die Kraft-Gleichheit wider: 2^(−l_i) = p_i, wenn l_i = log₂(1/p_i).
Aber log₂(1/p_i) ist selten ein ganzzahlig. Aufwärtsrunden auf ⌈log₂(1/p_i)⌉ geben die Huffman-Länge, die H ≤ L < H + 1 erfüllt.
Geometrische Lesart. Ploten Sie jedes Symbol als Punkt im binären Baum auf der Tiefe l_i. Die Kraft-Summe misst die Gesamthöhe der Blätter. Die Entropie misst die gewichtete durchschnittliche Tiefe, gewichtet mit der Wahrscheinlichkeit. Shannons Theorem: Wahrscheinlichkeitsgewichtete durchschnittliche Tiefe ≥ Wahrscheinlichkeitsgewichtete Informationsmenge.
Entropie-Schranken-Verifizierung
Das beispielhafte 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.
Diese sind alle ganzzahlig - ein perfekter Match. Huffman-Codierung: 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: optimales Code.
Ein vollständig bearbeitetes Beispiel
Vollständiger Pipeline: gegebenen Wahrscheinlichkeiten, Entropie berechnen, überprüfen, ob ein Code die Grenze erreicht.
Quelle: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 Bit (berechnet oben).
Ein naiver Blockcode: 4 Symbole → 2 Bits jedes → L = 2,0. Überhead über Entropie: 2,0 − 1,75 = 0,25 Bit/Symbol = 12,5% Verschwendung.
Der variablen Länge-Code spart 12,5% im Vergleich zum festen Länge. Für große Nachrichten ist dies beträchtlich.
Entropiesatz von Englisch. Shannon schätzte die Entropie der geschriebenen Englisch auf etwa 1,0 bis 1,3 Bit pro Zeichen, trotz Verwendung von 5-Bit ASCII-Codes. Dieser 4:1 Verhältnis spiegelt die enorme Redundanz in der natürlichen Sprache wider - häufige Buchstaben klumpen, Wörter wiederholen, Grammatik beschränkt Sequenzen.
Kompression kann die Entropie nicht übertreffen
Kompressionsverhältnis: H / (Blockcode-Länge). Für unser Beispiel: 1,75/2,0 = 0,875 - 87,5% Effizienz.
Kann man weiter komprimieren? Nur durch den Kontext: wenn man Pairs oder Triples von Symbole zusammen codiert, dann kann die gemeinsame Entropie H(X,Y) weniger als 2·H(X) sein aufgrund statistischer Abhängigkeiten. Dies ist die Erweiterung des Noiseless Coding Theorems auf n-Gramme.