Kompresja danych: Niepewne kodowanie arytmetyczne

Question

Czy ktoś może wyjaśnić kodowanie arytmetyczne dla kompresji danych ze szczegółami implementacji? Przeszukałem Internet i odnalazłem stanowisko nelsona, ale technika implementacji jest dla mnie niejasna po wielu godzinach. wyjaśnienie

Mark Nelsona na kodowanie arytmetyczne mogą być zlokalizowane w

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

Answer 1

Główną ideą kompresji arytmetycznej jest możliwość kodowania prawdopodobieństwa przy użyciu dokładnej ilości wymaganej długości danych.

Ta ilość danych jest znany, świadczy Shannon i mogą być obliczane tylko przy użyciu następującego wzoru: -log2 (p)

Przykładowo, gdy p = 50%, to konieczne 1 bit. A jeśli p = 25%, potrzebujesz 2 bitów.

Jest to dość proste dla prawdopodobieństw o ​​sile 2 (w tym szczególnym przypadku kodowanie Huffmana może wystarczyć). Ale co, jeśli prawdopodobieństwo wynosi 63%? Następnie potrzebujesz -log2 (0.63) = 0.67 bitów. Brzmi trudno ...

Ta właściwość jest szczególnie ważna, jeśli prawdopodobieństwo jest wysokie. Jeśli potrafisz przewidzieć coś z 95% dokładnością, potrzebujesz tylko 0,074 bitów, aby przedstawić dobre domysły. Co oznacza, że ​​będziesz dużo kompresować.

Teraz, jak to zrobić?

Cóż, to jest prostsze niż się wydaje. Będziesz dzielił swój zakres w zależności od prawdopodobieństw. Na przykład, jeśli masz zakres 100, 2 możliwe zdarzenia i prawdopodobieństwo 95% dla pierwszego, to pierwsze 95 wartości powie "Zdarzenie 1", a ostatnie 5 pozostałych wartości powie "Zdarzenie 2" .

OK, ale na komputerach jesteśmy przyzwyczajeni do używania mocy 2. Na przykład, z 16 bitami, masz zakres 65536 możliwych wartości. Zrób to samo: weź 1. 95% zakresu (czyli 62259), aby powiedzieć "Wydarzenie 1", a pozostałe powiedz "Wydarzenie 2". Najwyraźniej masz problem "zaokrąglania" (precyzji), ale dopóki masz wystarczająco dużo wartości do dystrybucji, nie ma to większego znaczenia. Co więcej, nie jesteś ograniczony do 2 wydarzeń, możesz mieć niezliczoną liczbę zdarzeń. Liczy się tylko to, że wartości są przydzielane w zależności od prawdopodobieństw każdego zdarzenia.

OK, ale teraz mam 62259 możliwych wartości do powiedzenia "Zdarzenie 1" i 3277 do powiedzenia "Zdarzenie 2". Który powinienem wybrać ? Cóż, każdy z nich to zrobi. Wether to 1, 30, 5500 lub 62256, nadal oznacza "Event 1".

W rzeczywistości decydowanie, która wartość wybrać nie będzie zależało od bieżącego odgadnięcia, ale od następnych.

Załóżmy, że mam "Zdarzenie 1". Teraz muszę wybrać dowolną wartość z przedziału od 0 do 62256. Przy następnym założeniu mam taką samą dystrybucję (95% Zdarzenie 1, 5% Zdarzenie 2). Po prostu przydzielę mapę dystrybucji z tymi prawdopodobieństwami. Tyle, że tym razem jest on rozprowadzany po 62256 wartościach. I kontynuujemy tak, zmniejszając zakres wartości za każdym razem.

Tak więc definiujemy "zakresy", które ograniczają się do każdego odgadnięcia. W pewnym momencie istnieje jednak problem dokładności, ponieważ pozostają bardzo małe wartości.

Ideą jest po prostu "nadmuchanie" zakresu ponownie. Na przykład, za każdym razem, gdy zakres spada poniżej 32768 (2^15), wysyłasz najwyższy bit i mnożymy resztę przez 2 (skutecznie przesuwając wartości o jeden bit w lewo). Przez ciągłe robienie tego w ten sposób, wyprowadzasz bity jeden po drugim, ponieważ są one ustalane według serii domysłów.

Teraz relacja z kompresją staje się oczywista: gdy zakres jest zawężany szybko (np. 5%), wyprowadzasz wiele bitów, aby uzyskać zasięg powyżej limitu. Z drugiej strony, gdy prawdopodobieństwo jest bardzo wysokie, zakres zawęża się bardzo powoli. Przed wydrukowaniem pierwszych bitów możesz mieć wiele domysłów. W ten sposób można skompresować zdarzenie do "ułamka sekundy".

Celowo użyłem terminów "prawdopodobieństwo", "domysły", "zdarzenia", aby zachować ogólny charakter tego artykułu. Ale w przypadku kompresji danych wystarczy je zastąpić sposobem, w jaki modelujesz dane. Na przykład następnym zdarzeniem może być następny bajt; w tym przypadku masz ich 256.

Answer 2

Przede wszystkim dzięki za wprowadzenie mnie do pojęcia kompresji arytmetycznej!

można zobaczyć, że sposób ten obejmuje następujące etapy:

1. Tworzenie odwzorowanie: Oblicz część wystąpienia dla każdej litery co daje zakres wielkości dla każdego z alfabetu. Następnie zamówić je i przypisać rzeczywiste wynosi od 0 do 1
2. Biorąc pod uwagę komunikat obliczyć zakresu (całkiem proste IMHO)
3. znaleźć optymalny kod

Trzecia część jest nieco kłopotliwe. Użyj następującego algorytmu.

Niech b będzie optymalną reprezentacją. Zainicjuj go na pusty ciąg ("'). Niech x będzie wartością minimalną, a y - wartością maksymalną.

1. double x i y: x * x = 2, y = 2 * y
2. Jeżeli obie są większe niż 1 do dołączania do 1 b. Przejdź do kroku 1.
3. Jeśli oba są mniejsze niż 1, dodaj 0 do b. Przejdź do kroku 1.
4. jeśli x < 1, ale y> 1, a następnie dołączyć do 1 b i zatrzymać

b zasadniczo zawiera część ułamkową liczby jesteś przekazującego. Na przykład. Jeśli b = 011, to frakcja odpowiada 0,011 w systemie binarnym.

Której części wdrożenia nie rozumiesz?

Answer 3

Może ten skrypt może być przydatny do zbudowania lepszego modelu mentalnego kodera arytmetycznego: gen_map.py. Pierwotnie został stworzony, aby ułatwić debugowanie arytmetycznej biblioteki koderów i uprościć generowanie testów jednostkowych. Jednak tworzy ładne wizualizacje ASCII, które również mogą być przydatne w zrozumieniu kodowania arytmetycznego.

Mały przykład. Wyobraźmy sobie, że mamy alfabet 3 symboli: 0, 1 i 2 z prawdopodobieństwami 1/10, 2/10 i 7/10 odpowiednio. I chcemy kodować sekwencję [1, 2].Skrypt daje następujący wynik (ignoruj ​​-b N opcję teraz)

$ ./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 

Pierwsze 6 linii (przed ==== linii) obejmują zakres od 0,0 do 1,0, który jest podzielony na rekurencyjnie odstępach proporcjonalna do prawdopodobieństwa symboli. Odnotowany pierwszy wiersz:

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

Następnie podzielić każdy przedział raz:

[ 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 

uwaga, że ​​niektóre przedziały nie są podzielone. Dzieje się tak, gdy nie ma wystarczającej ilości miejsca, aby reprezentować każdy podinterval z zadaną precyzją (która jest określona przez opcję -b).

Każda linia odpowiada symbolowi z wejścia (w naszym przypadku - sekwencja [1, 2]). Podążając za podprzedziałami dla każdego symbolu wejściowego, otrzymamy końcowy interwał, który chcemy zakodować z minimalną ilością bitów. W tym przypadku jest to pierwszy 2 podprzedziału w drugim wierszu:

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

Po 7 linii (po ====) stanowią tym samym przedziale od 0,0 do 1,0, ale podzielony według notacji binarnej. Każda linia jest trochę wyjściowa i wybierając między 0 a 1, wybierasz lewą lub prawą połowę podprzedania. Na przykład bity 01 odpowiada podprzedziale [0.25, 05) na drugiej linii:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

Idea arytmetyczna koder ma bitów wyjściowych (0 lub 1), aż odpowiedni odstęp będzie całkowicie wewnątrz (lub równy) określony przedział przez sekwencję wejściową. W naszym przypadku jest to 0011. Linia ~~~~ pokazuje, gdzie mamy wystarczającą liczbę bitów, aby jednoznacznie określić interwał, jaki chcemy.

Pionowe linie utworzone przez symbol | pokazują zakres sekwencji bitów (wierszy), które mogą być użyte do zakodowania sekwencji wejściowej.