Kodowanie arytmetyczne

Kodowanie arytmetyczne to metoda kodowania źródłowego dyskretnych źródeł sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona przez Petera Eliasa około 1960 roku.

Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego [0,1) wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia tychże wiadomości generowanych przez źródło. Ciąg kodowy reprezentujący kodowane wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału.

Można udowodnić, że przy wyborze odpowiednio długiego ciągu wiadomości do zakodowania, średnia liczba symboli na wiadomość jest mniejsza od H(X) + 2, gdzie H(X) jest entropią źródła, lecz większa bądź co najwyżej równa samej entropii.

Algorytm kodowania

Dany jest zbiór symboli $S=\{x_{1},x_{2},\ldots \}$ oraz stowarzyszony z nim zbiór prawdopodobieństw $p=\{p_{1},p_{2},\ldots \}$. Jeden z symboli jest wyróżniony - jego wystąpienie oznacza koniec komunikatu, zapobiegając wystąpieniu niejednoznaczności; ewentualnie zamiast wprowadzenia dodatkowego symbolu można przesyłać długość kodowanego ciągu.

Na początku dany jest przedział $P=[0,1)$, który dzielony jest na podprzedziały o szerokościach równych kolejnym prawdopodobieństwom $p_{i}$, czyli otrzymywany jest ciąg podprzedziałów $[0,p_{1}),[p_{1},p_{2}),[p_{1}+p_{2},p_{3}),[p_{1}+p_{2}+p_{3},p_{4}),\ldots$. Kolejnym podprzedziałom (ozn. $R_{i}$) odpowiadają symbole ze zbioru $S$.

Algorytm kodowania:

• Dla kolejnych symboli symbol c.
  • Określ który podprzedział bieżącego przedziału $P$ odpowiada literze c - wynikiem jest $R_{i}$.
  • Weź nowy przedział $P:=R_{i}$ - następuje zawężenie przedziału
  • Podziel ten przedział $P$ na podprzedziały w sposób analogiczny jak to miało miejsce na samym początku (chodzi o zachowanie proporcji szerokości podprzedziałów).
• Zwróć liczbę jednoznacznie wskazującą przedział $P$ (najczęściej dolne ograniczenie, albo średnia dolnego i górnego ograniczenia)Maxi king all right

Przykład 1.

Na rysunku pokazano jak zmienia się aktualny przedział $P$ w trzech pierwszych krokach kodowania. Kodowane są cztery symbole o prawdopodobieństwach $p=\{0.6,0.2,0.1,0.1\}$ w kolejności: pierwszy, trzeci, czwarty.

Przykład 2.

Niech $S=\{a,b,c,\#\}$ ($\#$ - koniec komunikatu), prawdopodobieństwa $p=\{0.45,0.3,0.2,0.05\}$.

Zakodowany zostanie ciąg $caba\#$.

• Początkowo przedział $P=[0,1)$, jest on dzielony na podprzedziały $[0,0.45),[0.45,0.75),[0.75,0.95),[0.95,1)$.
• Pierwszym kodowany symbolem jest $c$, któremu odpowiada 3. podprzedział, zatem $P:=R_{3}=[0.75,0.95)$. Nowy przedział znów jest dzielony: $[0.75,0.84),[0.84,0.9),[0.9,0.94),[0.94,0.95)$.
• Kolejnym kodowanym symbolem jest $a$, któremu odpowiada 1. podprzedział, zatem $P:=R_{1}=[0.75,0.84)$. Nowy przedział znów jest dzielony: $[0.75,0.7905),[0.7905,0.8175),[0.8175,0.8355),[0.8355,0.84)$.
• Kolejnym kodowanym symbolem jest $b$, któremu odpowiada 2. podprzedział, zatem $P:=R_{2}=[0.7905,0.8175)$. Nowy przedział znów jest dzielony: $[0.7905,0.80265),[0.80265,0.81075),[0.81075,0.81615),[0.81615,0.8175)$.
• Kolejnym kodowanym symbolem jest (ponownie) $a$, któremu odpowiada 1. podprzedział, zatem $P:=R_{1}=[0.7905,0.80265)$. Nowy przedział znów jest dzielony: $[0.7905,0.795968),[0.795968,0.799612),[0.799612,0.802042),[0.802042,0.80265)$.
• Kolejnym kodowanym symbolem jest $\#$, kończący kodowanie, któremu odpowiada 4. podprzedział, zatem $P:=R_{4}=[0.802042,0.80265)$.
• Na wyjście zostaje zapisana liczba identyfikująca ten przedział - może to być, jak wspomniano, jego dolne ograniczenie, czyli 0.802042.

Dekodowanie

Dekodowanie przebiega prawie tak samo. Z tą różnicą, że przy kodowaniu kolejne litery jednoznacznie określała podprzedziały, przy dekodowaniu natomiast wybierany jest ten podprzedział, do którego należy kodująca liczba. Wybranie podprzedziału powoduje wypisanie powiązanego z nim symbolu.

Formalnie algorytm przebiega następująco:

• $x$ - liczba (kod)
• $P=[0,1)$
• Wykonuj w pętli:
  • Podziel $P$ na podprzedziały $R_{i}$
  • Znajdź podprzedział $R_{i}$ do którego należy $x$.
  • $P:=R_{i}$
  • Wypisz i-ty symbol na wyjście
  • Jeśli i-ty symbol był symbolem końcowy, zakończ pętlę

Przykład

Na rysunku poniżej pokazano pierwsze trzy kroki dekodowania liczby 0.538 (zaznaczona kropką na osi liczbowej); prawdopodobieństwa symboli: $p=\{0.6,0.2,0.1,0.1\}$. W pierwszej iteracji $P=[0,1)$ - liczba 0.538 znajduje się w pierwszym przedziale, a zatem wypisany zostanie pierwszy symbol, a $P:=R_{1}=[0,0.6]$. Teraz 0.538 znajduje się w przedziale 3., wypisany zostanie symbol 3. a $P=R_{3}=[0.48,0.54]$. Itd.

Praktyczne implementacje

Podstawowy algorytm, dość wolny jednak, generuje kolejne bity rozwinięcia dwójkowego. O wiele lepsza realizacja opiera się w całości na działaniach na liczbach całkowitych.

Bibliografia

Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999

Zobacz też

• Kompresja danych (informatyka)
• Program do kompresji plików
• Kompresja bezstratna oraz kompresja stratna
• kodowanie Shannona
• kodowanie Shannona-Fano
• kodowanie Huffmana