Kodowanie arytmetyczne
Kodowanie arytmetyczneKodowanie arytmetyczne – 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 co najmniej równa samej entropii. Algorytm kodowaniaDany jest zbiór symboli oraz stowarzyszony z nim zbiór prawdopodobieństw . Jeden z symboli jest wyróżniony – jego wystąpienie oznacza koniec komunikatu, co zapobiega 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 pi, czyli otrzymywany jest ciąg podprzedziałów . Kolejnym podprzedziałom (ozn. Ri) odpowiadają symbole ze zbioru S. Algorytm kodowania: - Dla kolejnych symboli c:
- Określ, który podprzedział bieżącego przedziału P odpowiada literze c – wynikiem jest Ri.
- Weź nowy przedział P: = Ri – następuje zawężenie przedziału
- Podziel ten przedział P na podprzedziały w sposób analogiczny do tego, 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).
Przykład 1.Na rysunku pokazano, jak zmienia się aktualny przedział P w trzech pierwszych krokach kodowania. Kodowane są trzy symbole z czteroelementowego zbioru o prawdopodobieństwach p = {0,6;0,2;0,1;0,1}, w kolejności: pierwszy, trzeci, czwarty. Przykład 2.Niech ( – koniec komunikatu), prawdopodobieństwa p = {0,45,0,3,0,2,0,05}. Zakodowany zostanie ciąg . - 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 kodowanym symbolem jest c, któremu odpowiada 3. podprzedział, zatem P: = R3 = [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: = R1 = [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: = R2 = [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: = R1 = [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: = R4 = [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.
DekodowanieDekodowanie przebiega prawie tak samo. Różnica polega na tym, że przy kodowaniu kolejne litery jednoznacznie określały 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 Ri
- Znajdź podprzedział Ri, do którego należy x.
- P: = Ri
- Wypisz i-ty symbol na wyjście
- Jeśli i-ty symbol był symbolem końcowy, zakończ pętlę
PrzykładNa rysunku poniżej pokazano pierwsze trzy kroki dekodowania liczby 0,538 (zaznaczonej 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: = R1 = [0,0,6]. Teraz 0,538 znajduje się w przedziale 3., wypisany zostanie symbol 3., a P = R3 = [0,48,0,54] itd. Praktyczne implementacjePodstawowy 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ż
Inne hasła zawierające informacje o "Kodowanie arytmetyczne":
Jajko w kulturze
...
Historia nauki
...
Claude E. Shannon
...
Algorytm genetyczny
...
Ciąg arytmetyczny
...
Kodowanie arytmetyczne
Kodowanie arytmetyczne – metoda
kodowania źródłowego
dyskretnych źródeł
sygnałów
, stosowana jako jeden ...
Kompresja (informatyka)
statyczne.Czasami, np. w algorytmie
PNG
, stosowane są modele pośrednie. Algorytmy kompresji bezstratnej
Kodowanie Huffmana
Kodowanie arytmetyczne
Kodowanie Shannona
,
Shannona-Fano
LZ77
,
LZSS
,
LZP
LZ78
,
LZW
,
LZMW
,
LZAP
LZMA
PNG
RLE
PPM
Deflate
Bzip2
(oparty m.in. o ...
Kryptologia
...
Unicode
...
Mitochondrium
...
Inne lekcje zawierające informacje o "Kodowanie arytmetyczne":
Pierwiastki (plansza 9)
...
Sieci komputerowe - Warstwowy model OSI (plansza 5)
...
Algorytmy genetyczne (plansza 31)
...
|