Gibt es einen theoretisch nachgewiesenen optimalen Komprimierungsalgorithmus?

7

Ist die Huffman-Codierung immer optimal, da sie Shanons Ideen verwendet? Was ist mit Text, Bild, Video, ... Komprimierung?

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

algorithms information-theory data-compression Zeta.Investigator
quelle
2
Sie könnten auf en.wikipedia.org/wiki/Kolmogorov_complexity
Dávid Natingga
DavidToths Link ist die Antwort. Kurz gesagt "nein". Sie können nicht beweisen, dass Daten minimal komprimiert sind (was es natürlich unmöglich macht, einen optimalen Algorithmus zu beweisen)
edA-qa mort-ora-y
2
@ edA-qamort-ora-y: "Sie können nicht beweisen, dass Daten minimal komprimiert sind" - dies ist nicht wahr. Vgl. das Problem des Anhaltens, das im Allgemeinen nicht zu entscheiden ist, aber natürlich gibt es einige Programme, für die wir nachweisen können, dass es anhält oder nicht anhält. Vgl. auch die beschäftigte Biberfunktion; Einige Werte der Funktion sind bekannt.
Jukka Suomela
@JukkaSuomela, ja, meine Formulierung war in dieser Hinsicht nicht gründlich. Sie können natürlich bestimmte Datensätze haben, von denen gezeigt werden kann, dass sie optimal komprimiert sind. Ich vermute jedoch, dass die Größe solcher Daten extrem klein ist.
edA-qa mort-ora-y
Eine coole Metrik, die Sie interessieren könnte, ist der normalisierte Kompressionsabstand (NCD). Vitanyi & Li haben unter anderem Papiere darüber. Kurz gesagt, es funktioniert recht gut für alle Arten von Daten und stellt in gewissem Sinne alle anderen Metriken in den Vordergrund. Wenn Sie möchten, finden Sie im Vitanyi & Li-Buch über die Komplexität von Kolmogorov einen guten Einstieg.
Juho

Antworten:

9

Die Huffman-Codierung ist optimal für eine Symbol-zu-Symbol-Codierung, bei der die Wahrscheinlichkeiten jedes Symbols unabhängig und vorher bekannt sind. Wenn diese Bedingungen jedoch nicht erfüllt sind (wie in Bild, Video), werden andere Codierungstechniken wie LZW, JPEG usw. verwendet. Weitere Informationen finden Sie im Buch "Einführung in die Datenkomprimierung" von Khalid Sayood.

Arani
quelle
Abgesehen von rein zufälligen Daten glaube ich nicht, dass ein Datentyp diese Bedingungen erfüllt.
edA-qa mort-ora-y
2
Die anderen Techniken sind jedoch nicht von Symbol zu Symbol. So erreichen sie eine bessere Komprimierung. Und das ist auch der Grund, warum Huffman-Codierung für sich genommen selten verwendet wird.
Svick
6

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

Yuval Filmus
quelle
6

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

Einige Komprimierungsalgorithmen komprimieren einige Arten von Dateien, die kleiner als der Huffman-Algorithmus sind , daher ist Huffman nicht optimal. Diese Algorithmen nutzen die eine oder andere Einschränkung des Huffman-Optimalitätsnachweises aus.

Wann immer wir (a) haben, codieren wir jedes Symbol unabhängig in einer ganzzahligen Anzahl von Bits, und (b) jedes Symbol ist "unabhängig" von den anderen Symbolen, die wir übertragen (keine gegenseitige Information, 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 komprimierten Dateien).

(a) Symbol für Symbol: Durch Lockerung der binären Huffman-Einschränkung, dass jedes Eingabesymbol als ganzzahlige Anzahl von Bits codiert werden muss, sind mehrere Komprimierungsalgorithmen, wie z. B. die Bereichscodierung, niemals schlechter als und normalerweise besser als Standard-Huffman .

(b) nicht verwandte Symbole: Die meisten realen Datendateien enthalten einige gegenseitige Informationen zwischen Symbolen. Man kann es besser machen als einfaches Huffman, indem man die Symbole "dekorreliert" und dann den Huffman-Algorithmus für diese dekorrelierten Symbole verwendet.

(c) bekannte Wahrscheinlichkeitsverteilung: Normalerweise kennt der Empfänger die genaue Wahrscheinlichkeitsverteilung nicht. Typische Huffman-Komprimierungsalgorithmen senden also zuerst eine Frequenztabelle und dann die komprimierten Daten. Mehrere "adaptive" Komprimierungsalgorithmen, wie z. B. die Polar Tree-Codierung, können eine bessere Komprimierung als Huffman erzielen, da sie auf die Wahrscheinlichkeitsverteilung konvergieren oder sich an eine sich ändernde Wahrscheinlichkeitsverteilung anpassen, ohne jemals explizit eine Häufigkeitstabelle zu senden.

Bücher und Papiere, die eine solche Komprimierung diskutieren, die besser als Huffman ist:

David Cary
quelle
2

Die optimale Komprimierungsrate hängt von der Entropie der Daten ab.

Aus dem Wikipedia-Artikel http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem :

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

user1149913
quelle
warum wird das herabgestimmt?
Sasho Nikolov