un

guest
1 / ?
back to lessons

Warum die gierige Strategie optimal ist

Der Huffman Algorithmus ist ein gieriger Algorithmus: Bei jedem Schritt wird die lokale optimale Wahl getroffen (die beiden gönstigsten Knoten verbinden) ohne vorauszuschauen. Gierige Algorithmen sind nicht immer global optimal - aber hier sind sie.

Der Optimierungsargument

Angenommen, ein Code C hat den minimalen Durchschnittswert L. Überlegen Sie sich zwei Symbole mit der niedrigsten Wahrscheinlichkeit, z. B. p_a und p_b. In jedem optimalen Code müssen diese beiden Symbole als Schwestergewinne in der tiefsten Ebene des Baumes auftreten. Warum?

Wenn sie nicht gemeinsam einen Elternknoten haben, können Sie das tiefere Symbol mit einer kürzeren Code-Bezeichnung austauschen - um L zu reduzieren. Daher müssen die tiefsten Blattknoten die am wahrscheinlichsten vorkommenden Symbole sein.

Jetzt, wenn Sie a und b zu einem Meta-Symbol ab (mit p_ab = p_a + p_b) kombinieren, ist jeder optimale Code für die reduzierte Alphabetmenge ohne ein Symbol genau der Huffman-Code für die reduzierte Problematik. Die Induktion schliesst das Argument ab.

Geometrische Sicht

Der Huffman Algorithmus konstruiert den binären Baum von unten nach oben und platziert die am wahrscheinlichsten vorkommenden Symbole in der grössten Tiefe. Dies minimiert Σ p_i ü depth(i) = L.

Eineaquivalente Ansicht: Sie werden Blattknoten mit Bezeichnungen zuweisen, um die gewichtete Pfadlænge zu minimieren, wobei der Gewicht jeder Blattknoten seiner Wahrscheinlichkeit entspricht.

Ausführen der gierigen Schritte

Wahrscheinlichkeiten: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Summe = 1.0 ✓

Schritt 1: Niedrigste beiden: C(0.2), D(0.1). Verbinden Sie sie ö CD(0.3). Liste: A(0.4), B(0.3), CD(0.3).

Schritt 2: Niedrigste beiden: B(0.3), CD(0.3) (Tie - beide gülig). Verbinden Sie sie ö BCD(0.6). Liste: A(0.4), BCD(0.6).

Schritt 3: Verbinden Sie A(0.4), BCD(0.6) ö root(1.0). Zuweisen Sie A=0, BCD=1.

Rükwärts: BCD ö B=10 (l=2), CD=11 ö C=110 (l=3), D=111 (l=3).

L = 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 0.4+0.6+0.6+0.3 = 1.9 Bits.

H für p={0.4, 0.3, 0.2, 0.1}: berechnen Sie H = -Ω p_i×log₂(p_i). Verwenden Sie log₂(0.4) ∼ -1.322, log₂(0.3) ∼ -1.737, log₂(0.2) ∼ -2.322, log₂(0.1) ∼ -3.322. Stellen Sie sicher, dass L = 1.9 ≥ H, und berechnen Sie L/H.

Code-Längenvarianz

Zwei Huffman-Codes können die gleiche L erreichen, aber unterschiedliche Verteilungen der Codierlängen aufweisen. Die Varianz der Codierlängen misst diesen Ausdehnungsbereich:

Var(l) = E[l²] − (E[l])²

wobei E[l] = L (durchschnittliche Codierlänge) und E[l²] = Σ p_i · l_i².

Lang vs Buschiger Baumvergleich

Warum Varianz wichtig ist:

1. Pufferanforderungen. Bei der Echtzeitdekodierung nimmt jeder Symbol einen variablen Anzahl von Bits. Hohe Varianz bedeutet, dass einige Symbole viele Bits benötigen – Sie müssen einen größeren Eingabepuffer haben, um garantieren zu können, dass Sie immer ein vollständiges Symbol lesen können.

2. Decodierlatenz. Hohe-Varianz-Codes haben lange Worst-Case-Decodierwege. Niedrig-Varianz-(buschige) Codes binden den Worst-Case enger.

3. Robustheit. Ein verlorenes Bit in einem hohen-Varianz-Code verursacht mehr Synchronisationschaden, weil lange Codewörter vollständig neu gelesen werden müssen.

Empfehlung von Hamming: Wenn mehrere gültige Huffman-Codes vorhanden sind (Auswahlmöglichkeiten), bevorzugen Sie das mit der niedrigeren Varianz – den buschigen Baum.

Berechnung der Varianz für zwei Bäume

Mit p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1 und dem Code A=0, B=10, C=110, D=111:

E[l] = L = 1,9

E[l²] = 0,4·1² + 0,3·2² + 0,2·3² + 0,1·3² = 0,4+1,2+1,8+0,9 = 4,3

Var = 4,3 − 1,9² = 4,3 − 3,61 = 0,69

Überlegen Sie jetzt den buschigen Alternativansatz: B=00, C=01, A=10, D=11 (alle Längen = 2, L=2). Beachten Sie, dass dies KEIN Huffman-Code ist (L=2 > H≈1,846), sondern als Vergleich dient. Berechnen Sie Var für diesen buschigen-Code-Länge-2. Erklären Sie dann: Auch wenn der buschige Code eine höhere L als Huffman hat, was ist die Eigenschaft, die ihn in Echtzeanwendungen vorziehen lässt?

3-Symbol-Huffman-Code von Anfang bis Ende

Ein vollständiges End-to-End-Beispiel: Huffman-Code erstellen, L berechnen, H berechnen, L ≥ H verifizieren, Var berechnen.

Quelle: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.

Huffman erstellen:

Schritt 1: Sortiert: X(0.6), Y(0.3), Z(0.1). Niedrigste zwei: Y(0.3), Z(0.1).

Verbinden → YZ(0.4). Liste: X(0.6), YZ(0.4).

Schritt 2: Verbinden von X(0.6) und YZ(0.4) → root(1.0). Zuweisen: X=0, YZ=1.

YZ → Y=10, Z=11.

Code: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).

L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 Bit.

Entropie: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)

log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322

H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 Bit.

L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8,1% über der Entropie.

Variance: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.

Ihr Zug: Ein vollständiger Pipeline

log₂-Werte zum Referenz: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.

Erstellen Sie einen Huffman-Code für p(A)=0.5, p(B)=0.375, p(C)=0.125. Zeigen Sie die Schritte der Verknüpfung auf. Berechnen Sie L, H, L/H und Var. Stellen Sie einen Einblick zur Verfügung, der L in Bezug auf H für diese Quelle zeigt.