Adaptive arithmetische kodierende Verwirrung

Question

Ich bin verwirrt über den Punkt der adaptiven arithmetischen Codierung.

Ich verstehe, dass die statische arithmetische Codierung die Verwendung von voreingestellten Wahrscheinlichkeiten von Symbolen beinhaltet, die während des gesamten Prozesses statisch bleiben.Ich verstehe auch, dass die adaptive Arithmetikcodierung alle Wahrscheinlichkeiten nach jedem aufgetretenen Symbol ändern.

Was ist jedoch der Punkt, um die Wahrscheinlichkeit nach jedem Symbol zu ändern?Warum sollten Sie nicht zuerst eine gesamte Datei durchgehen und die Wahrscheinlichkeiten ermitteln und dann die Arithmetikkodierung als zweiter Durchgang durchführen?

Darüber hinaus verstehe ich nicht, wie die Wahrscheinlichkeit von Symbolen die Kompression beeinflusst?Wenn wir die echten Wahrscheinlichkeiten der Symbole in der Datei kennen, die wir komprimieren, erstellt dies die Datei kleiner?

Answer 1

Zunächst überlegen, "durch eine ganze Datei durchgehen". Es gibt ein paar Annahmen, die es wert sind, darüber nachzudenken.

Dateien können sehr groß sein und sie zweimal durchqueren, können teuer sein. Dies ist ein Grund, warum die meisten realen Komprimierungsstandards um Blöcke oder Windows basieren.

Es gibt Situationen, in denen Sie nicht "die gesamte Datei" haben, um damit zu beginnen, wie beispielsweise ein Kommunikationskanal. tls (vor 1.3, zumindest) unterstützt die Komprimierung beispielsweise.

Dateien sind nicht immer homogen. Archive (z. B. teer ) ist ein Fall im Punkt. Ein statistisches Modell, das für einen Teil einer Datei geeignet ist, ist möglicherweise nicht für einen anderen Teil geeignet. Adaptive Coding passt sich auch an.

In Bezug auf Ihre letzte Frage, wenn sowohl der Encoder als auch der Decoder die echten Wahrscheinlichkeiten der Symbole in der Datei, die wir komprimieren, kannten, dann müsste das nicht übertragen werden. Und in der Tat tun wir dies manchmal in der realen Welt. Der JPEG-Standard gibt beispielsweise Standardcodierungs-Tabellen für diese Zeiten an, in denen sie angemessen sind, und lässt einen Codierer ihre eigenen liefern, wenn sie nicht sind.

Übertragen einer statischen Codierungstabelle effizient (d. H. Komprimieren) ist ein nicht -triviales Problem, insbesondere für ein großes Code-Alphabet. Für ein gut entworfenes Schema sollten die Kosten für die Übertragung der Tabelle gleich den "Lernkosten" der Verwendung eines adaptiven Codes sein.