Algorytmy kompresji kodowanie huffmana kodowanie arytmetyczne

background image

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.

background image

Kodowanie Huffmana,

Kodowanie Huffmana,

kodowanie arytmetyczne

kodowanie arytmetyczne

background image

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

background image

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.

background image

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).

background image

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)

background image

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ę

background image

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.

background image

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

background image

Zastosowanie kodowania
arytmetycznego

Kodowanie

arytmetyczne

najczęściej

wykorzystywane jest w formatach:

JBIG

JPEG / MPEG

JPEG-2000

H.263

H.26L

PPM

DMM

background image

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

background image

Kodowanie arytmetyczne – przykład 2 cd.

Kodujemy komunikat: bac

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

background image

Dekodowanie arytmetyczne – przykład 3

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

długość komunikatu 3:

Wynikowy komunikat to bbc

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
Algorytmy kompresji kodowanie huffmana kodowanie arytmetyczne(1)
Kodowanie i kompresja danych
Wykład 6 6 kodowanie mowy
Kodowanie informacji
Kodowanie
Kodowanie pytań
kodowanie tekstu
POZIOMY KODOWANIA TEMPORALNEGO
Kodowanie zbior pytan wykład
KODOWANIE (metody), Metodologia badań społecznych
kodowanie sterownikow Audi A4, auta, Diagnostyka dokumety, procedury diagnostyczne
INSTRUKCJA KODOWA, studia, 3 semestr, badania marketingowe
KODOWANIE LICZB
BW12 teoria informacji i kodowania turbokody

więcej podobnych podstron