Materiały pochodzą z Platformy

Edukacyjnej Portalu

www.szkolnictwo.pl

Wszelkie treści i zasoby edukacyjne publikowane na łamach Portalu www.szkolnictwo.pl mogą być wykorzystywane przez jego
Użytkowników

wyłącznie

w zakresie własnego użytku osobistego oraz do użytku w szkołach podczas zajęć dydaktycznych. Kopiowanie, wprowadzanie zmian,
przesyłanie,

publiczne

odtwarzanie

i wszelkie wykorzystywanie tych treści do celów komercyjnych jest niedozwolone. Plik można dowolnie modernizować na potrzeby
własne

oraz

do

wykorzystania

w szkołach podczas zajęć dydaktycznych.

Kodowanie Huffmana,

Kodowanie Huffmana,

kodowanie arytmetyczne

kodowanie arytmetyczne

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 amerykańskiego
profesora Petera Eliasa około 1960 roku.



Ideą tego kodu jest przedstawienie ciągu wiadomości
jako podprzedziału przedziału jednostkowego P –
[0,1)

wyznaczonego

rekursywnie

na

podstawie

prawdopodobieństw

wystąpienia

tych

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.

Peter Elias

1923-2001

Kodowanie arytmetyczne



Pojedyncze

słowo

kodowe

jest

przyporządkowane

każdemu

możliwemu

zbiorowi wiadomości ze źródła.



Każde słowo kodowe może być traktowane jako
jednostronnie domknięty podprzedział przedziału
[0,1).



Poprzez przypisanie każdemu słowu kodowemu
wystarczająco dużo znaczących bitów, można
odróżnić jeden podprzedział od innego i w ten
sposób zdekodować ciąg bitów, przypisując mu
zbiór wiadomości wygenerowanych przez źródło.

Algorytm kodowania

Dany jest zbiór symboli S – {x

1

, x

2

, …} oraz stowarzyszony z nim

zbiór prawdopodobieństw p – {p

1

, p

2

, …}. 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

. Kolejnym podprzedziałom (ozn. R

i

) odpowiadają symbole ze zbioru.

Algorytm kodowania:



dla kolejnych symboli x

i



określamy, który podprzedział bieżącego przedziału

odpowiada danej literze x

i

- wynikiem jest R

i



bierzemy nowy przedział P:= R

i

– następuje zawężenie

przedziału



dzielimy ten przedział na podprzedziały tak aby zostały

zachowane proporcje szerokości podprzedziałów



zostaje zwrócona liczba jednoznacznie wskazującą przedział

(najczęściej dolne ograniczenie, albo średnia dolnego i górnego
ograniczenia).

Kodowanie arytmetyczne – przykład 1

Rozważmy kodowanie zbioru wiadomości: AADB@

Kodowan

y tekst

Prawdopodobień

stwo

Skumulowane

prawdopodobień

stwo

Przedział

A

0,2

0,2

[0,0;

0,2)

A

0,4

0,6

[0,2;

0,6)

D

0,1

0,7

[0,6;

0,7)

B

0,2

0,9

[0,7;

0,9)

@

(koniec)

0,1

1,0

[0,9;

1,0)

Kodowanie arytmetyczne – przykład 1 cd.

Kodujemy

A

i otrzymujemy przedział

[0.0; 0.2)

Drugą liczbę

A

kodujemy i otrzymujemy przedział

[0.0; 0.04)

Kodujemy

D

i otrzymujemy przedział

[0.028; 0.036)

Kodujemy

B

i otrzymujemy przedział

[0.0296; 0.0328)

Kodujemy

@

i otrzymujemy przedział

[0.03248; 0.0328)

Przedział lub dowolna liczba z niego reprezentuje

kodowany zbiór wiadomości



dla ustalonej długości tekstu n, każdy ciąg jest
odwzorowany na przedział rozłączny z przedziałami
odpowiadającymi

innym

ciągom.

Gwarantuje

to

jednoznaczność kodowania



wygenerowanie znacznika dla konkretnego ciągu nie
wymaga wyznaczania bądź pamiętania znaczników
innych ciągów



nadajemy dowolną liczbę z ostatniego zawężonego
zakresu



żeby można było otrzymać zakodowane wiadomości,
dekoder musi znać model źródła i nadaną liczbę

Dekodowanie arytmetyczne –
przykład 1 cd.



Dekodowanie składa się z serii porównań odebranej
liczby z zakresami reprezentującymi wiadomości ze
źródła



W prezentowanym przykładzie liczba ta może wynosić np.
0.03248, 0.0325 lub 0.0327. Ponieważ należy ona do
przedziału [0.0; 0.2) dekoder rozpoznaje pierwszą wiadomość
jako

A

, co zawęża przedział do [0.0; 0.2).



Dekoder jest w stanie wywnioskować, że następna wiadomość
zawęzi przedział na jeden z możliwych sposobów: do [0.0;
0.04) dla

A

, do [0.04; 0.12) dla

B

, do [0.12; 0.14) dla

C

, do

[0.14; 0.18) dla D i [0.18; 0.2) dla

@

.



Ponieważ odebrana liczba mieści się w przedziale [0.0; 0.04),
zatem podejmuje decyzję, że następna nadana wiadomość to

A

.



Procedura kontynuowana jest aż do określenia wszystkich
wiadomości w nadanym zbiorze.

Wady kodowania arytmetycznego



dekoder musi wiedzieć, kiedy zakończyć proces. Są
możliwe dwa rozwiązania



zakończenie

wiadomością

„stop”

(@

w

przykładzie) – to rozwiązanie jest najbardziej
preferowane



koder

musi

przesłać

liczebność

zbioru

kodowanych wiadomości



w praktycznej realizacji kodera i dekodera niezbędna
jest precyzja i złożoność wykonywanych operacji



podczas kodowania są ograniczone pojemności
rejestrów (możliwe jest przepełnienie)



występują błędy w dekodowaniu

Zastosowanie kodowania
arytmetycznego

Kodowanie

arytmetyczne

najczęściej

wykorzystywane jest w formatach:



JBIG



JPEG / MPEG



JPEG-2000



H.263



H.26L



PPM



DMM

Kodowanie arytmetyczne – przykład 2

Rozważmy kodowanie zbioru wiadomości: bac

Kodowan

y tekst

Prawdopodobień

stwo

Skumulowane

prawdopodobień

stwo

Przedział

a

0,2

0,2

[0,0;

0,2)

b

0,5

0,7

[0,2;

0,7)

c

0,3

1,0

[0,7;

1,0)

Dla każdego znaku komunikatu
przypisujemy

podprzedział

przedziału [0,1).
Dla każdego komunikatu przedział
ten nazywa się przedziałem
komunikatu

Kodowanie arytmetyczne – przykład 2 cd.

Kodujemy komunikat: bac

Wynikowy przedział to [0,27; 0,3)

Dekodowanie arytmetyczne – przykład 3

Dekodujemy liczbę 0.49, znamy początkowe przedziały i

długość komunikatu 3:

Wynikowy komunikat to bbc

Algorytm kodowania Huffmana

Kodowanie Huffmana to jedna z najprostszych i

łatwych
w implementacji metod kompresji bezstratnej.
Została opracowana w 1952 roku przez Amerykanina
Davida Huffmana.

Algorytm Huffmana jest wykorzystywany w wielu

profesjonalnych metodach kompresji tekstu, obrazów i
dźwięków, również w połączeniu z innymi metodami.

Redukcja wielkości danych przy stosowaniu tego

algorytmu wynosi ok 50 %.

W przypadku obrazów i dźwięków kodowane są nie

same znaki np. piksele, ale również miejsca między
kolejnymi znakami.

David

Huffman

1925-1999

Cechy algorytmu Huffmana



generuje kod zero-jedynkowy



kod każdego znaku nie jest początkowym fragmentem

kodu innego znaku



generowany kod jest kodem prefix-free (0, 1), który

pozwala na jednoznaczne dekodowanie



jest tworzony tak, aby średnia długość kodu znaku

była możliwie najkrótsza – w tym celu wykorzystuje się
informację o częstości występowania znaku w tekście.

W celu wykorzystania algorytmu Huffmana musimy

zbudować jego reprezentację w postaci

drzewa.

Charakterystycznymi cechami drzewa są:



oznaczenia drzewa 0 i 1



znaki dla których tworzymy kod znajdują się w liściach

drzewa

a

c

g

0

0

1

1

a

c

g

0

10 11

Algorytm Huffmana przykład

Prześledźmy teraz działanie algorytmu Huffmana na

przykładzie

sześciu

wybranych

liter.

W

kółkach

mamy

częstotliwość występowania w języku polskim napisanej niżej litery.

8,7

1

1,2

9

3,4

5

3,1

0

7,9

0

4,6

3

A

B

D

K

O

R

W celu zbudowania drzewa Huffmana ze zbioru usuwamy dwie
najmniejsze częstotliwości czyli w naszym przypadku 1,29 i 3,10. Na
ich miejsce wstawiamy ich sumę 1,29 + 3,10 = 4,39 i podczepiamy
wierzchołki z usuniętymi częstotliwościami pod nowy wierzchołek.

8,7

1

1,2

9

3,4

5

3,1

0

7,9

0

4,6

3

A

D

B

K

O

R

4,3

9

Algorytm Huffmana przykład

Ponownie ze zbioru usuwamy
dwie najmniejsze częstotliwości
czyli 3,45 i 4,39. Łączymy je i
otrzymujemy.

8,7

1

1,2

9

3,4

5

3,1

0

7,9

0

4,6

3

A

B

K

O

R

4,3

9

7,8

4

D

8,7

1

1,2

9

3,4

5

3,1

0

7,9

0

4,6

3

A

B

K

O

4,3

9

7,8

4

D

Następnym

krokiem

jest dodanie do siebie
4,63 i 7,83 po czym
otrzymujemy:

12,4

7

R

Algorytm Huffmana przykład

Kolejne dwie najmniejsze częstotliwości to 7,90 i 8,71, po
czym otrzymaliśmy 2 drzewa:

8,71

1,29

3,45

3,10

7,90

4,63

B

K

4,39

7,84

D

12,4

7

R

A

O

16,6

1

Algorytm Huffmana przykład

Na końcu dodajemy dwie ostatnie częstotliwości – 13,47 i 16,61.
Ostatecznie otrzymujemy jedno drzewo.

8,71

1,29

3,45

3,10

7,90

4,63

B

K

4,39

7,84

D

12,4

7

R

A

O

16,6

1

Algorytm Huffmana przykład

Po otrzymaniu jednego drzewa należy każde rozgałęzienie
odpowiednio oznaczyć 0 lub 1. Każdą lewą gałąź 0, a prawą
1 (lub odwrotnie).

8,71

1,29

3,45

3,10

7,90

4,63

B

K

4,39

7,84

D

12,4

7

R

A

O

16,6

1

0

0

0

0

0

1

1

1

1

1

Litera

Zakodow
ana
wartość

A

00

B

1010

D

100

K

1011

O

01

R

11

Algorytm Huffmana przykład –
kodowanie, dekodowanie

Posiadając tabelę możemy łatwo zakodować dowolne
kombinacje liter (wyrazy). Np.:

Lite

ra

Zakodow

ana

wartość

A

00

B

1010

D

100

K

1011

O

01

R

11

R

O

D

A

K

1

1

0

1

10

0

0

0

101

1

B

R

O

D

A

101

0

1

1

01 10

0

00

W analogiczny sposób dokonujemy dekodowania
zakodowanego ciągu znaków, np.: 10110111101000.
Dzięki temu, że kod jest prefiksowy łatwo można podzielić
ten ciąg 0 i 1 na odpowiednie kody liter :

101

1

0

1

101

0

1

1

00

K

O

R

B

A

Odkodujmy ciąg znaków: 1011001000010101100

101

1

0

0

10

0

0

0

101

0

1

1

0

0

K

A

D

A

B

R

A

Kodowanie Huffmana
podsumowanie



kodowanie Huffmana stanowi kanon kompresji



jest adaptowane dla każdego tekstu



długości ciągów kodowych dobierane są do
statystyki źródła wiadomości



kodowanie opiera sie o częstość występowania
znaków



wykorzystywane w:



kodowaniu faksów



standardzie kompresji:



JPEG



MPEG-1



MPEG-2

Bibliografia



Drozdek A.: Wprowadzenie do kompresji danych, WNT

1999



K. Sayood , Kompresja danych. Wprowadzenie, 1.

READ ME, Warszawa, 2002



W. Skarbek, Multimedia . Algorytmy i standardy

kompresji, Akademicka Oficyna Wydawnicza PLJ,

Warszawa, 1998



P. Wróblewski : Algorytmy, struktury danych i

techniki programowania, Helion, Gliwice 2001



http://pl.wikipedia.org/wiki/



http://en.wikipedia.org/wiki/



http://www.ucsc.edu/currents/99-00/10-

18/inmemoriam.html