Datenkompression: Arithmetische Codierung unklar

Question

Kann jemand bitte arithmetische Codierung für die Datenkomprimierung mit Implementierungsdetails erklären? Ich habe im Internet gesurft und Mark Nelsons Post gefunden, aber die Technik der Implementierung ist für mich tatsächlich unklar, nachdem ich viele Stunden lang versucht habe.

Mark Nelsons Erklärung auf Arithmetik-Codierung bei

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

Die Grundidee bei der arithmetischen Komprimierung ist die Möglichkeit, eine Wahrscheinlichkeit mit der genauen Menge der erforderlichen Datenlänge zu codieren.

Diese Datenmenge ist bekannt, durch Shannon bewährt und kann einfach unter Verwendung der folgenden Formel berechnet werden: -log2 (p)

Zum Beispiel, wenn p = 50%, dann müssen Sie 1 Bit. Und wenn p = 25%, benötigen Sie 2 Bits.

Das ist einfach genug für Wahrscheinlichkeiten, die eine Potenz von 2 sind (und in diesem speziellen Fall könnte Huffman-Codierung genug sein). Aber was ist, wenn die Wahrscheinlichkeit 63% beträgt? Dann brauchst du -log2 (0.63) = 0.67 Bits. Sounds tricky ...

Diese Eigenschaft ist besonders wichtig, wenn Ihre Wahrscheinlichkeit hoch ist. Wenn Sie etwas mit einer Genauigkeit von 95% vorhersagen können, benötigen Sie nur 0,074 Bits, um eine gute Schätzung zu liefern. Was bedeutet, dass Sie viel komprimieren werden.

Nun, wie geht das?

Nun, es ist einfacher als es klingt. Sie teilen Ihren Bereich abhängig von Wahrscheinlichkeiten auf. Wenn Sie zum Beispiel einen Bereich von 100, 2 möglichen Ereignissen und eine Wahrscheinlichkeit von 95% für das erste Ereignis haben, dann sagen die ersten 95 Werte "Ereignis 1" und die letzten 5 verbleibenden Werte sagen "Ereignis 2" .

OK, aber auf Computern sind wir es gewohnt, Potenzen von 2 zu verwenden. Zum Beispiel haben Sie mit 16 Bit eine Bandbreite von 65536 möglichen Werten. Tun Sie das Gleiche: Nehmen Sie die ersten 95% des Bereichs (also 62259), um "Event 1" zu sagen, und den Rest, um "Event 2" zu sagen. Sie haben offensichtlich ein Problem des "Rundens" (Genauigkeit), aber solange Sie genügend Werte zum Verteilen haben, spielt es keine Rolle. Außerdem sind Sie nicht auf 2 Ereignisse beschränkt, Sie könnten unzählige Ereignisse haben. Es kommt nur darauf an, dass die Werte abhängig von den Wahrscheinlichkeiten jedes Ereignisses zugewiesen werden.

OK, aber jetzt habe ich 62259 mögliche Werte, um "Event 1" zu sagen, und 3277, um "Event 2" zu sagen. Welches soll ich nehmen ? Nun, jeder von ihnen wird tun. Ob 1, 30, 5500 oder 62256, es bedeutet immer noch "Ereignis 1".

In der Tat, die Entscheidung, welcher Wert ausgewählt wird, hängt nicht von der aktuellen Schätzung ab, sondern von den nächsten.

Angenommen, ich habe "Ereignis 1". Jetzt muss ich einen Wert zwischen 0 und 62256 wählen. Bei der nächsten Schätzung habe ich die gleiche Verteilung (95% Event 1, 5% Event 2). Ich werde einfach die Verteilungskarte mit diesen Wahrscheinlichkeiten zuordnen. Nur diesmal ist es auf 62256 Werte verteilt. Und wir fahren so fort und reduzieren den Wertebereich bei jeder Schätzung.

In der Tat definieren wir "Bereiche", die mit jeder Schätzung enger werden. Irgendwann gibt es jedoch ein Genauigkeitsproblem, da sehr wenige Werte übrig bleiben.

Die Idee ist, den Bereich einfach wieder "aufzublasen". Zum Beispiel wird jedes Mal, wenn der Bereich unter 32768 (2^15) liegt, das höchste Bit ausgegeben und der Rest mit 2 multipliziert (effektiv werden die Werte um ein Bit nach links verschoben). Indem Sie so fortfahren, geben Sie Bits nacheinander aus, da sie durch die Reihe von Vermutungen festgelegt werden.

Jetzt wird die Beziehung mit der Komprimierung offensichtlich: Wenn der Bereich schnell verschmälert wird (zB 5%), geben Sie eine Menge Bits aus, um den Bereich wieder über den Grenzwert zu bringen. Auf der anderen Seite, wenn die Wahrscheinlichkeit sehr hoch ist, verengt sich der Bereich sehr langsam. Sie können sogar viele Vermutungen haben, bevor Sie Ihre ersten Bits ausgeben. So ist es möglich, ein Ereignis auf "einen Bruchteil eines Bits" zu komprimieren.

Ich habe absichtlich die Begriffe "Wahrscheinlichkeit", "raten", "Ereignisse" verwendet, um diesen Artikel generisch zu halten. Aber für die Datenkomprimierung müssen Sie sie nur so ersetzen, wie Sie Ihre Daten modellieren möchten. Zum Beispiel kann das nächste Ereignis das nächste Byte sein; In diesem Fall haben Sie 256 davon.

Answer 2

Erstmal Danke liegen mir Kompression auf das Konzept der Arithmetik für die Einführung!

kann ich sehen, daß dieses Verfahren die folgenden Schritte aufweist:

1. Mapping Erstellen: für jeden Buchstaben den Anteil des Vorkommens berechnen, die für jedes Alphabet einer Bereichsgröße gibt. Dann sie bestellen und tatsächlichen Bereiche von 0 bis 1
2. eine Meldung gegeben zuweisen berechnen den Bereich (ziemlich einfach IMHO)
3. Finden Sie den optimalen Code

Der dritte Teil ist ein bisschen schwierig. Verwenden Sie den folgenden Algorithmus.

Sei b die optimale Darstellung. Initialisiere es in eine leere Zeichenfolge (''). Sei x der Minimalwert und y der Maximalwert.

1. Doppel x und y: x = 2 * x, y = 2 * y
2. Wenn beide von ihnen größer als 1 append 1 bis b. Gehen Sie zu Schritt 1.
3. Wenn beide kleiner als 1 sind, hängen Sie 0 an b an. Gehen 1.
4. Wenn x < 1, aber zu dem Schritt y> 1 ist, dann fügen Sie 1 bis b und Stop

b enthält im wesentlichen den Bruchteil der Zahl Sie senden. Z.B. Wenn b = 011 ist, dann entspricht der Bruchteil 0,011 im Binärwert.

Welchen Teil der Implementierung verstehen Sie nicht?

Answer 3

Vielleicht könnte dieses Skript nützlich sein, um ein besseres mentales Modell des arithmetischen Coders zu erstellen: . Ursprünglich wurde es erstellt, um das Debuggen der arithmetischen Coder-Bibliothek zu erleichtern und die Erzeugung von Komponententests dafür zu vereinfachen. Es erzeugt jedoch schöne ASCII-Visualisierungen, die auch für das Verständnis der arithmetischen Codierung nützlich sein könnten.

Ein kleines Beispiel. Stellen Sie sich vor, wir haben ein Alphabet von 3 Symbolen: 0, 1 und 2 mit Wahrscheinlichkeiten 1/10, 2/10 und 7/10 entsprechend. Und wir wollen die Sequenz [1, 2] kodieren.Script gibt die folgende Ausgabe (vorerst -b N Option ignorieren):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

ersten 6 Zeilen (vor ==== Linie) stellen einen Bereich von 0,0 bis 1,0, das rekursiv auf Intervallen proportional zur Symbolwahrscheinlichkeiten unterteilt ist. Annotierten Erste Zeile:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

Dann unterteilen wir jedes Intervall wieder:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

Beachten Sie, dass einige Intervalle sind nicht unterteilt. Dies geschieht, wenn nicht genügend Platz vorhanden ist, um jedes Subintervall innerhalb einer gegebenen Genauigkeit darzustellen (was durch die Option -b spezifiziert wird).

Jede Zeile entspricht einem Symbol aus dem Eingang (in unserem Fall - Sequenz [1, 2]). Indem wir Subintervallen für jedes Eingangssymbol folgen, erhalten wir ein letztes Intervall, das wir mit einer minimalen Anzahl von Bits codieren wollen. In unserem Fall ist es ein erstes Subintervall 2 auf einer zweiten Leitung:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

Nach 7 Zeilen (nach ====) stellen die gleichen Intervall 0,0 bis 1,0, aber aufgegliedert nach Binärnotation. Jede Zeile ist ein bisschen Ausgabe, und indem Sie zwischen 0 und 1 wählen, wählen Sie links oder rechts Halb-Subintervall. Beispielsweise die Bits 01[0.25, 05) auf einer zweiten Leitung Subintervall entspricht:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

Die Idee des arithmetischen Codierers zu Ausgangsbits (0 oder 1), bis das entsprechende Intervall vollständig in sein wird (oder gleich) das Intervall bestimmt durch die Eingabesequenz. In unserem Fall ist es 0011. Die Zeile ~~~~ zeigt, wo wir genügend Bits haben, um das gewünschte Intervall eindeutig zu identifizieren.

Vertikale Linien, die durch das Symbol | gebildet werden, zeigen den Bereich der Bitfolgen (Zeilen), die zum Codieren der Eingabesequenz verwendet werden könnten.