Warum eliminiert die Huffman-Codierung die Entropie, die Lempel-Ziv nicht hat?

Der beliebte DEFLATE-Algorithmus verwendet Huffman-Codierung über Lempel-Ziv.

Wenn wir eine zufällige Datenquelle haben (= 1-Bit-Entropie / Bit), ist es im Allgemeinen wahrscheinlich , dass keine Codierung, einschließlich Huffman, diese im Durchschnitt komprimiert. Wenn Lempel-Ziv "perfekt" wäre (was sich für die meisten Klassen von Quellen annähert, da die Länge unendlich ist), würde das Nachkodieren mit Huffman nicht helfen. Natürlich ist Lempel-Ziv nicht perfekt, zumindest nicht mit begrenzter Länge, und daher bleibt eine gewisse Redundanz bestehen.

Diese verbleibende Redundanz beseitigt die Huffman-Codierung teilweise und verbessert dadurch die Komprimierung.

Meine Frage ist: Warum wird diese verbleibende Redundanz durch Huffman-Codierung und nicht durch LZ erfolgreich beseitigt? Welche Eigenschaften von Huffman versus LZ machen dies möglich? Würde ein erneutes Ausführen von LZ (dh ein zweites Codieren der komprimierten LZ-Daten mit LZ) etwas Ähnliches bewirken? Wenn nein, warum nicht? Ebenso würde das Komprimieren zuerst mit Huffman und anschließend mit LZ funktionieren, und wenn nicht, warum?

UPDATE: Es ist klar, dass auch nach LZ eine gewisse Redundanz bestehen bleibt. Mehrere Leute haben darauf hingewiesen. Was nicht klar ist: Warum wird die verbleibende Redundanz von Huffman besser angegangen als von LZ? Was ist daran einzigartig im Gegensatz zur ursprünglichen Quellenredundanz, bei der LZ besser funktioniert als Huffman?

Dies war ursprünglich ein Kommentar, aber es wurde zu lang.

Wenn Sie sich DEFLATE ansehen, komprimiert Huffman die Ausgabe von LZ77. LZ77 sendet (wenn dies weniger Bits als die Rohdaten erfordert) einen Zeiger früher in die zu komprimierende Zeichenfolge und eine Übereinstimmungslänge, die angibt, wie viele Symbole nach dem Zeiger verwendet werden sollen. Die Theorie zeigt, dass diese Technik auch ohne zusätzliche Komprimierung schließlich zur Quellenentropie konvergiert. Bei der Datenkomprimierung können Sie jedoch jederzeit eine nicht zufällige Verteilung komprimieren. Es gibt keinen Grund zu der Annahme, dass die Ausgabe von LZ77 - die Zeiger und die Übereinstimmungslängen - völlig zufällig ist. Sie müssen konvergieren, um die Zufälligkeit in der asymptotischen Grenze zu vervollständigen, da LZ77 asymptotisch optimal ist, aber in der Praxis nur ein endliches Wörterbuch verwendet wird. Vermutlich bleiben sie also weit genug vom Zufall entfernt, dass Sie gewinnen, wenn Sie sie weiter komprimieren. Natürlich verwenden Sie einen Huffman-Code für die Zeiger und einen anderen für die Übereinstimmungslängen, da diese beiden Prozesse unterschiedliche Statistiken haben.

Warum Huffman anstelle von LZ für die zweite Komprimierungsrunde verwenden? Der große Vorteil von LZ gegenüber Huffman besteht in der Behandlung von Abhängigkeiten zwischen Symbolen. Wenn auf Englisch ein Buchstabe ein "q" ist, ist der nächste höchstwahrscheinlich ein "u" und so weiter. Handelt es sich bei den Symbolen um unabhängige Ereignisse, ist Huffman einfacher und eignet sich genauso gut oder besser für kurze Zeichenfolgen. Für die Ausgabe von LZ77 ist meine Intuition, dass die Symbole ziemlich unabhängig sein sollten, sodass Huffman besser funktionieren sollte.

Bei der Datenkomprimierung geht es in Wirklichkeit um zwei Dinge: Modellierung und Codierung. Algorithmen der LZ-Familie modellieren den Text als Verkettung exakter Wiederholungen, was für viele Zufallsquellen asymptotisch optimal und für viele reale Texte einigermaßen gut ist. Für einige Eingaben kann dieses Modell jedoch ziemlich schlecht sein. Beispielsweise können Sie LZ nicht verwenden, um ein Suffix-Array direkt zu komprimieren, obwohl das Suffix-Array genauso komprimierbar ist wie der ursprüngliche Text.

$(p, \ell, c)$$p$$\ell$$c$

$\log n$$n$

Kurz gesagt, Huffman schlägt LZ bei der Komprimierung der Tupel, da sein Modell (feste Verteilung im Vergleich zu exakten Wiederholungen) besser zu den Daten passt.

Ich glaube, die Antwort liegt in der Größe des Nachschlagewörterbuchs.

Daten haben ein Gefühl von Lokalität (das heißt, wenn ein Datenelement verwendet wurde, wird es wahrscheinlich bald wieder verwendet), und der LZ-Algorithmus nutzt dies bei der Konstruktion des Nachschlagewörterbuchs aus. Es wird ein Versuch mit einer begrenzten Anzahl möglicher Knoten generiert, um die Suche schnell zu halten . Wenn es die Größenbeschränkung erreicht, wird ein weiterer Versuch unternommen, den vorherigen zu "vergessen". Daher muss die Nachschlagetabelle für die einfacheren Zeichen erneut erstellt werden. Werden jedoch einige Wörter nicht mehr verwendet, werden sie nicht mehr im Speicher gespeichert, sodass eine kleinere Codierung verwendet werden kann.

Daher kann mit der Huffman-Codierung eine LZ-Ausgabe weiter reduziert werden, da durch statistische Analyse diese Redundanz bei der Erstellung der Nachschlageversuche erkannt werden kann.

Vielleicht bin ich hier nicht auf dem richtigen Weg, aber die Huffman-Codierung untersucht die gesamte Eingabe, um die Codierungstabelle (Baum) zu erstellen, während Lempel-Ziv im weiteren Verlauf codiert. Dies ist sowohl ein Vorteil als auch ein Nachteil für Huffman. Der Nachteil liegt auf der Hand, dass wir den gesamten Input sehen müssen, bevor wir beginnen können. Der Vorteil ist, dass Huffman Statistiken berücksichtigt, die an einer beliebigen Stelle in der Eingabe auftreten, während Lempel-Ziv schrittweise darauf aufbauen muss. Oder anders ausgedrückt, Lempel-Ziv hat eine "Richtung", die Huffman nicht hat.

Aber all dies ist nur meine naive Art, mir vorzustellen, wie die Dinge sind. Wir würden hier einen echten Beweis brauchen, um zu sehen, wie genau Huffman Lempel-Ziv übertrifft.

Die kurze Antwort lautet: LZ ist ein "universeller" Algorithmus, bei dem die genaue Verteilung der Quelle nicht bekannt sein muss (nur die Annahme, dass die Quelle stationär und ergodisch ist erforderlich). Aber Huffman ist nicht; es muss die genaue Verteilung kennen, von der die Quelle abgetastet wird (um den Huffman-Baum zu erstellen). Durch diese zusätzlichen Informationen erreicht Huffman enge Kompressionsgarantien. Für praktische Dateikomprimierungsalgorithmen kann Huffman jedoch ungünstiger sein, da zunächst empirische Statistiken der Datei gesammelt und dann in einer zweiten Hälfte die eigentliche Komprimierung durchgeführt werden müssen, während LZ online implementiert werden kann.

Weitere Details finden Sie in Standardtexten zur Informationstheorie, z. B. Elements of Information Theory von Cover und Thomas.