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