Gibt es einen theoretisch nachgewiesenen optimalen Komprimierungsalgorithmus?

cs.stackexchange https://cs.stackexchange.com/questions/3316

Frage

Ist Huffman -Codierung stets Optimal, da es Shanons Ideen verwendet? Was ist mit Text, Bild, Video, ... Komprimierung?

Ist dieses Thema noch im Feld aktiv? Welche klassischen oder modernen Referenzen sollte ich lesen?

War es hilfreich?

Lösung

Die Codierung von Huffman ist optimal für ein Symbol-zu-Symbol-Codieren, bei dem die Wahrscheinlichkeiten jedes Symbols unabhängig und vorhändig bekannt sind. Wenn diese Bedingungen jedoch nicht erfüllt sind (wie im Bild, Video), werden andere Codierungstechniken wie LZW, JPEG usw. verwendet. Für weitere Details können Sie das Buch "Einführung in die Datenkomprimierung" von Khalid Sayood durchlaufen.

Andere Tipps

Es gibt eine Version des Lempel-Ziv-Algorithmus, der in einigen Szenarien optimal ist. Wenn der Eingang von einer ergodischen Markov-Kette stammt, entspricht die asymptotische Rate des Lempel-Ziv-Algorithmus der Entropie. Weitere Informationen dazu finden Sie in Kapitel 13 von Cover und Thomas.

Die Huffman -Komprimierung mit bestimmten Annahmen, die normalerweise nicht für reale Dateien gelten, kann als optimal erwiesen werden.

Mehrere Komprimierungsalgorithmen komprimieren einige Arten von Dateien kleiner als der Huffman -Algorithmus, Deshalb ist Huffman nicht optimal. Diese Algorithmen nutzen den einen oder anderen Vorbehalt im Huffman -Optimalitätsbeweis.

Wann immer wir (a) haben, codieren wir jedes Symbol unabhängig in einer ganzzahligen Anzahl von Bits, und (b) Jedes Symbol ist mit den anderen Symbolen, die wir übertragen, "nicht verwandt" (keine gegenseitigen Informationen, statistisch unabhängig usw.) und (c) Der Empfänger kennt die Wahrscheinlichkeitsverteilung jedes möglichen Symbols, dann ist die Huffman -Komprimierung optimal (erzeugt die kleinsten Druckdateien).

(a) Symbol für Symbol: Durch Entspannen der binären Huffman-Beschränkung, dass jedes Eingangssymbol als ganzzahlige Anzahl von Bits codiert werden muss, sind mehrere Komprimierungsalgorithmen, wie z. .

(b) Nicht verwandte Symbole: Die meisten realen Datendateien haben einige gegenseitige Informationen zwischen den Symbolen. Man kann es besser machen als ein einfaches Huffman, indem man die Symbole "dekorrelieren" und dann den Huffman -Algorithmus auf diesen Dekorrelatymbolen verwendet.

(c) Bekannte Wahrscheinlichkeitsverteilung: Normalerweise kennt der Empfänger die genaue Wahrscheinlichkeitsverteilung nicht. Daher senden typische Huffman -Komprimierungsalgorithmen zuerst eine Frequenztabelle und senden dann die komprimierten Daten. Mehrere "adaptive" Komprimierungsalgorithmen, wie z. B. polare Baumcodierung, können eine bessere Komprimierung als Huffman erzielen, da sie die Wahrscheinlichkeitsverteilung konvergieren oder sich an eine sich ändernde Wahrscheinlichkeitsverteilung anpassen, ohne jemals explizit eine Frequenztabelle zu senden.

Bücher und Papiere über die so besser als Huffman-Komprimierung diskutierte:

Die optimale Komprimierungsrate hängt mit der Entropie der Daten zusammen.

Aus dem Wikipedia -Artikel http://en.wikipedia.org/wiki/shannon%27S_Source_Coding_theorem:

N iid zufällige Variablen mit jeweils Entropie H (x) können in mehr als NH (x) -Bits mit vernachlässigbarem Risiko eines Informationsverlusts komprimiert werden, da N tendenziell unendlich ist. Wenn sie jedoch in weniger als NH (x) -Bits komprimiert werden, ist es praktisch sicher, dass Informationen verloren gehen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top