Kodowanie arytmetyczne

Z Wikipedii

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.

Spis treści

1 Algorytm kodowania
- 1.1 Przykład 1.
- 1.2 Przykład 2.
2 Dekodowanie
- 2.1 Przykład
3 Praktyczne implementacje
4 Bibliografia
5 Zobacz też

[edytuj] 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_1 + p_2), [p_1 + p_2, p_1 + p_2 + p_3), [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).

[edytuj] 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.

[edytuj] 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.

[edytuj] 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ę

[edytuj] 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.

[edytuj] 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.

[edytuj] Bibliografia

Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999

[edytuj] Zobacz też

ASTD współorganizatorem Międzynarodowego Kongresu Kadry

W dniach 24-27 listopada odbędzie się Międzynarodowy Kongres Kadry - VIII edycja Kongresu Kadry, po raz pierwszy w wydaniu międzynarodowym.

Obrady WTO na razie bez przełomu

W toczących się od poniedziałku rozmowach w Genewie na temat zniesienia barier w światowym handlu w ramach tzw. rundy z Dauhy do soboty nie udało się wypracować porozumienia.

Absurdalne zapisy blokują unijne dotacje

Bardzo dobry projekt może nie dostać dofinansowania, jeżeli np. przedsiębiorca wypełni wniosek... czarnym długopisem. Takie wątpliwe wymogi wymyślają urzędnicy - czytamy w "Rzeczpospolitej".

KE zamroziła ponad 2 mld euro dla Bułgarii

Komisja Europejska zamroziła znacznie więcej środków dla Bułgarii, niż ogłoszone w środę 825 mln euro z przedakcesjnych funduszy ISPA, PHARE i SAPARD - napisał bułgarski dziennk "Sega".

Betacom: 35 proc. zysku na dywidendę?

Zarząd Betacom zamierza wnioskować do Rady Nadzorczej i WZA o przeznaczenie na wypłatę dywidendy około 35 proc. zysku netto za rok obrotowy 2007/08. W kolejnych latach zarząd planuje rekomendować wypłatę dywidendy na poziomie 25-35 proc. zysku - poinformowała spółka w raporcie rocznym.

Linki: Strona g��wna

Encyklopedia