Kodowanie Huffmana - Wikipedia, wolna encyklopedia














/**/





/**/
#centralNotice .siteNoticeSmall{display:none;}
#centralNotice .siteNoticeSmallAnon{display:none;}
#centralNotice .siteNoticeSmallUser{display:none;}
#centralNotice.collapsed .siteNoticeBig{display:none;}
#centralNotice.collapsed .siteNoticeSmall{display:block;}
#centralNotice.collapsed .siteNoticeSmallUser{display:block;}
#centralNotice.collapsed .siteNoticeSmallAnon{display:block;}
#centralNotice.anonnotice .siteNoticeSmallUser{display:none !important;}
#centralNotice.usernotice .siteNoticeSmallAnon{display:none !important;}


/**/

/**/

var wgFlaggedRevsParams = {"tags": {"accuracy": 2}};
var wgFlaggedRevsParams2 = {"tags": {"reliability": 3, "completeness": 2, "npov": 2, "presentation": 1}};
var wgStableRevisionId = 14871897;
var wgAjaxFeedback = {"sendingMsg": "Zapisywanie...", "sentMsg": "Dziękujemy!"}
var wgAjaxReview = {"sendingMsg": "Zapisywanie...", "sentMsg": "Oznaczanie zakończone!", "actioncomplete": "Operacja wykonana"}


@import "/w/index.php?action=raw&ctype=text/css&title=MediaWiki%3AGadget-btm-actions.css";@import "/w/index.php?action=raw&ctype=text/css&title=MediaWiki%3ANowicjusze.css";





if (wgNotice != '') document.writeln(wgNotice);
/*
Styles for Notices
*/

.notice-wrapper, .notice-collapsed-wrapper {
margin: 0;
padding: 0;
font-family: Arial,Helvetica,Tahoma,sans-serif;
color: #333;
background-color: #ddd;
font-size: 1.2em;
font-weight: 200;
}
.siteNoticeSmallUser {
font-size: 1.2em;
text-align: left;
}

.notice-wrapper a,
.notice-collapsed-wrapper a
{
color: #006699;
}

.notice-wrapper a:hover { text-decoration: underline; }
.notice-collapsed-wrapper a:hover { text-decoration: underline; }

.notice-wrapper
{
border: 1px solid #bbb;
background-color: #fcfcfc;
background-repeat: no-repeat;
height: 115px;
font-size: 1.4em;
padding: 5px 5px;
}

.notice-collapsed-wrapper
{
border: 1px solid #bbb;
text-align: left;
background-color: #fcfcfc;
font-size: 1.7em;
padding: 5px 5px;
}

.toggle-box
{
float: right;
font-size: 0.6em;
}

.notice-text
{
padding: 0 120px;
margin-left: auto;
margin-right: auto;
margin-bottom: 5px;
}

.amount-raised
{
color: #fff;
padding-left: 175px;
font-size: 1em;
float: left;
}

.goal
{
color: #333;
font-size: 1em;
text-align: right;
position: relative;
left: -30px
}

.red-button
{
background-image: url(http://upload.wikimedia.org/centralnotice/images/button-red.png);
width: 158px;
height: 27px;
color: #fff;
font-size: 0.7em;
font-weight: bold;
text-align: center;
display: table-cell;
vertical-align: middle;
font-family: Verdana, Arial, Helvetica,Tahoma,sans-serif;
cursor: pointer;
}

.red-button a
{
color: white;
}





[Ukryj]


Wikipedia może działać tylko dzięki Twojemu wsparciu.





Wesprzyj nas �






[Pokaż]


Wesprzyj Wikipedię, społeczny projekt non-profit.



Wesprzyj nas �







[Pokaż]

Wesprzyj Wikipedię, społeczny projekt non-profit. �"

Wesprzyj nas



/* */


         Nauczycieli i wykładowców zapraszamy do współpracy �ó Uruchomiono mechanizm wersji przejrzanych podnoszący jakość artykułów Wikipedii.



Kodowanie Huffmana[edytuj]

Z Wikipedii

Skocz do: nawigacji, szukaj
Kodowanie Huffmana (ang. Huffman coding) to jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.
Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej kompresji danych,
dlatego też praktycznie nie używa się go samodzielnie. Często
wykorzystuje się go jako ostatni etap w różnych systemach kompresji,
zarówno bezstratnej jak i stratnej, np. MP3 lub JPEG. Pomimo, że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych.




Spis treści
[ukryj]

1 Kodowanie Huffmana
2 Algorytm statycznego kodowania Huffmana

2.1 Przykład
2.2 Praktyczne zastosowanie
2.3 Przykład kodowania po 2 znaki naraz
2.4 Przykładowa implementacja algorytmu budowy drzewa


3 Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi
4 Algorytm dynamicznego kodowania Huffmana
5 Inne algorytmy kompresji bezstratnej
6 Zobacz też





//


Kodowanie Huffmana [edytuj]
Dany jest alfabet źródłowy (zbiór symboli) oraz zbiór stowarzyszonych z nim prawdopodobieństw . Symbolami są najczęściej bajty,
choć nie ma żadnych przeszkód żeby było nimi coś innego (np. pary
znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego
zestawu danych, np. poprzez wyznaczenie częstotliwości występowania
znaków w tekstach danego języka. Częściej jednak wyznacza się je
indywidualnie dla każdego zestawu danych.
Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów
bitowych), których długość jest odwrotnie proporcjonalna do
prawdopodobieństwa pi. Tzn. im częściej dany symbol występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.
Własności kodu Huffmana są następujące:

jest kodem prefiksowym; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;
średnia długość kodów jest najmniejsza spośród kodów prefiksowych;
jeśli prawdopodobieństwa są różne, tzn. pj > pi, to długość kodu dla symbolu xj jest niewiększa od kodu dla symbolu xi;
słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość;
dwa najdłuższe symbole różnią się tylko jednym, ostatnim bitem.

Kompresja polega na zastąpieniu symboli otrzymanymi kodami.

Algorytm statycznego kodowania Huffmana [edytuj]
Algorytm Huffmana:

Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.
Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.
Dopóki na liście jest więcej niż jedno drzewo powtarzaj:

Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.
Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw
usuniętych drzew, natomiast one same stają się jego lewym i prawym
poddrzewem. Korzeń drzewa nie przechowuje symbolu.



Drzewo, które pozostanie na liście, jest nazywane drzewem Huffmana – prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są symbole.
Algorytm Huffmana jest algorytmem niedeterministycznym
ponieważ nie określa w jakiej kolejności wybierać drzewa z listy, jeśli
mają takie samo prawdopodobieństwo. Nie jest również określone, które z
usuwanych drzew ma stać się lewym bądź prawym poddrzewem. Jednak bez
względu na przyjęte rozwiązanie średnia długość kodu pozostaje taka sama.
Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący:

Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie).
Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu):

Jeśli skręcasz w prawo dopisz do kodu bit o wartości 1.
Jeśli skręcasz w lewo dopisz do kodu wartości 0.



Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zależy od jego położenia w drzewie.


Przykład [edytuj]
Mamy symbole A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].

Łączymy węzły odpowiadające symbolom (A) i (B). Teraz mamy (A + B) = 0.3, (C) = 0.3, (D) = 0.4
Łączymy węzły odpowiadające drzewku (A + B) oraz (C). Teraz mamy ((A + B) + C)=0.6 i (D) = 0.4
Łączymy węzły odpowiadające drzewku ((A + B) + C) oraz (D). Teraz mamy tylko jeden wolny węzeł - drzewko (((A + B) + C) + D) = 1.0
Obliczamy kody znaków:

A = lewo, lewo, lewo= 000
B = lewo, lewo, prawo = 001
C = lewo, prawo = 01
D = prawo = 1



Jak łatwo sprawdzić średnia długość kodu wyniesie: .
Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku. Z kolei entropia źródła wynosi: E = �ł 0.1log20.1 �ł 0.2log20.2 �ł 0.3log20.3 �ł 0.4log20.4 = 1.8464
- optymalne kodowanie powinno charakteryzować się taką właśnie średnią
długością kodu. Jednak widać, że jest ona większa - efektywność wynosi
w tym przypadku .


Praktyczne zastosowanie [edytuj]
Jednym z głównych problemów stosowania statycznego algorytmu
Huffmana jest konieczność transmisji całego drzewa lub całej tablicy
prawdopodobieństw. W przypadku transmisji drzewa, węzły są odwiedzane w
porządku preorder,
węzeł wewnętrzny może zostać zapisany na jednym bicie (ma zawsze dwóch
synów), liście natomiast wymagają jednego bitu plus taka liczba bitów
jaka jest potrzebna do zapamiętania symbolu (np. 8 bitów). Np. drzewo z
przykładu może zostać zapisane jako: (1, 0, 'd', 1, 0, 'c', 1, 0, 'b',
0, 'a'), czyli 7 + 4 · 8 = 39 bitów.
Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań
pamięciowych, uzyskuje się kodując kilka kolejnych znaków na raz, nawet
jeżeli nie są one skorelowane.

Przykład kodowania po 2 znaki naraz [edytuj]

Symbole to tak jak wtedy - A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].
Jeśli liczba symboli jest nieparzysta, robimy coś z pierwszym lub ostatnim symbolem. Nie jest to w praktyce duży problem.
Zastępujemy symbole parami symboli - AA, AB, AC, AD, BA, BB, BC,
BD, CA, CB, CC, CD, DA, DB, DC, DD o prawdopodobieństwach odpowiednio -
[0.01, 0.02, 0.03, 0.04, 0.02, 0.04, 0.06, 0.08, 0.03, 0.06, 0.09,
0.12, 0.04, 0.08, 0.12, 0.16].
Drzewko rośnie po kolei:

(AA + AB) = 0.03
(BA + AC) = 0.05
(CA + (AA + AB)) = 0.06
(BB + AD) = 0.08
(DA + (BA + AC)) = 0.09
(BC + CB) = 0.12
((CA + (AA + AB)) + BD) = 0.14
(DB + (BB + AD)) = 0.16
((DA + (BA + AC)) + CC) = 0.18
(CD + DC) = 0.24
((BC + CB) + ((CA + (AA + AB)) + BD)) = 0.26
(DD + (DB + (BB + AD))) = 0.32
(((DA + (BA + AC)) + CC) + (CD + DC)) = 0.42
(((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD)))) = 0.58
((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 1.0



Zatem odpowiednim parom znaków odpowiadają:

AA - 101010
AB - 101011
AC - 00011
AD - 11111
BA - 00010
BB - 11110
BC - 1000
BD - 1011
CA - 10100
CB - 1001
CC - 001
CD - 010
DA - 0000
DB - 1110
DC - 011
DD - 110

Średnia liczba bitów przypadająca na parę symboli to 3.73, a więc średnia liczba bitów
na symbol to 1.865. Jest to znacznie lepsza kompresja (6.75% zamiast 5%
przy maksymalnej możliwej 7.68%) niż poprzednio. Używając większej
liczby znaków można dowolnie przybliżyć się do kompresji maksymalnej,
jednak znacznie wcześniej wyczerpie się pamięć, ponieważ wymagania pamięciowe rosną wykładniczo do liczby kompresowanych jednocześnie symboli.

Przykładowa implementacja algorytmu budowy drzewa [edytuj]
Zwracana jest tablica (2*N-1) węzłów, z czego N pierwszych odpowiada
odpowiednim symbolom, a ostatni korzeniowi drzewa. Algorytm
wyszukiwania węzłów o najmniejszej wartości nie jest specjalnie
efektywny. W rzeczywistym kodzie raczej należałoby utworzyć posortowaną
tablicę wolnych węzłów i efektywnie zakodować operację jednoczesnego
usunięcia z niej 2 skrajnych elementów i wprowadzenia 1 nowego.

struct Node {
int value;
struct Node *left, *right, *parent;
};

struct Node* make_huffman_tree (int symbols, int *values)
{
struct Node *nodes = malloc (sizeof (struct Node) * (symbols * 2 - 1));
int first_free_node = symbols;
struct Node *tmp1, *tmp2;
int i;

for (i=0; i<symbols; ++i)
{
nodes[i].left = NULL;
nodes[i].right = NULL;
nodes[i].parent = NULL;
nodes[i].value = values[i];
}
while (first_free_node != (symbols * 2 - 1))
{
tmp1 = NULL;
tmp2 = NULL;
for (i=0; i<first_free_node; ++i)
{
if (nodes[i].parent)
continue;
if (!tmp1)
{
tmp1 = &nodes[i];
}
else if (!tmp2)
{
tmp2 = &nodes[i];
}
else if (tmp1->value > nodes[i].value)
{
tmp2 = tmp1;
tmp1 = &nodes[i];
}
}
nodes[first_free_node].left = tmp1;
nodes[first_free_node].right = tmp2;
nodes[first_free_node].parent = NULL;
nodes[first_free_node].value = tmp1->value + tmp2->value;
tmp1->parent = &nodes[first_free_node];
tmp2->parent = &nodes[first_free_node];
first_free_node ++;
}

return nodes;
}

int main()
{
struct Node *nodes;
int value_table[4] = {1,2,3,4};

nodes = make_huffman_tree (4, value_table);

return 0;
}


Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi [edytuj]
Jeśli kodowane są pary symboli (tak jak w przykładzie powyżej), albo
trójki symboli, czy ogólnie n-tki symboli, to rozmiar drzewa Huffmana
rośnie znacząco - drzewo Huffmana należy zapisać razem z zakodowanym
komunikatem, aby można go było zdekodować; także im większe drzewo, tym
dłuższe stają się kody rzadziej występujących symboli. C. Weaver
zaproponował modyfikację algorytmu Huffmana, która redukuje pamięć
potrzebną do zapamiętania drzewa. Pomysł został opracowany przez
Michaela Hankamera, który opublikował wyniki w artykule "A modified
Huffman procedure with reduced memory reqiument" (IEEE Transactions on Communication COM-27, 1979, s. 930-932).
Modyfikacja polega na wprowadzeniu dodatkowego symbolu nazywanego ELSE, który zastępuje
wszystkie rzadko występujące symbole - jeśli pojedynczy symbol opisuje
N bitów, to symbol trafi do zbioru ELSE, gdy jego prawdopodobieństwo .
Prawdopodobieństwo przypisane do ELSE jest równe sumie zastępowanych
przez niego symboli. Przy kodowaniu symbolu należącego do klasy ELSE
zapisywany jest kod dla ELSE, oraz nieskompresowany symbol; np. gdy kod
ELSE to 0102, to kodując symbol 'H' (kod ASCII 7210 = 010010002) zapisane zostanie .
Dzięki temu drzewo staje się mniejsze, ponieważ zachowuje tylko
symbole nie należące do ELSE i to w zupełności wystarczy, ponieważ
symbole ze zbioru ELSE są bezpośrednio zapisane w komunikacie.
Zastosowanie tej modyfikacji może nawet polepszyć nieco stopień
kompresji w stosunku do niezmodyfikowanej wersji algorytmu.

Algorytm dynamicznego kodowania Huffmana [edytuj]
Dynamiczne kodowanie Huffmana to kodowanie danych o nieznanej
statystyce. Statystykę buduje się w miarę napływania danych i co znak
lub co daną liczbę znaków poprawia drzewo Huffmana.
Zaletą kodowania dynamicznego jest to, że nie ma potrzeby przesyłania drzewa kodów. Zamiast tego identyczną procedurę poprawiania drzewa muszą przeprowadzać zarówno koder jak i dekoder.
Istnieją dwa algorytmy pozwalające poprawić drzewo Huffmana:

algorytm Fallera-Gallera-Knutha (pomysłodawcami byli Newton Faller i Robert Galler, metodę ulepszył Donald Knuth),
algorytm Vittera (dalsze ulepszenia metody FGK opracowane przez Jeffreya Vittera).

U podstaw algorytmu FGK leżą następujące założenie co do formy drzewa:

każdy węzeł drzewa, oprócz liści, ma zawsze dwóch potomków;
z każdym węzłem związany jest licznik: w liściach przechowuje liczbę wystąpień danego symbolu (lub wartość proporcjonalną), w pozostałych węzłach sumę liczników dzieci;
przy przejściu drzewa wszerz od prawej do lewej i odczycie
liczników powiązanych z każdym węzłem uzyskuje się ciąg liczb
nierosnących.

W algorytmie Vittera zaostrzone zostało ostatnie założenie:

również otrzymuje się ciąg liczb nierosnących, lecz w obrębie
podciągów o tych samych wartościach na początku znajdują się te
pochodzące z węzłów wewnętrznych, a na końcu z liści.

Gdy licznik w jakimś liściu zwiększy się, algorytmy modyfikują
(przemieszczając niektóre węzły) jedynie niewielki fragment drzewa,
zachowując wyżej wymienione własności. Algorytm Vittera jest nieco bardziej złożony, jednak daje lepsze wyniki, tj. krótsze kody, niż algorytm FKG.

Inne algorytmy kompresji bezstratnej [edytuj]

Transformata Burrowsa-Wheelera
PPM


Zobacz też [edytuj]

kodowanie arytmetyczne
kodowanie Shannona-Fano
kod Golomba
kod unarny
kod Tunstalla
Kompresja danych (informatyka)
program do kompresji plików






Źródło: �śhttp://pl.wikipedia.org/wiki/Kodowanie_Huffmana”
Kategoria: Algorytmy kompresji



artykułdyskusjaedytujhistoria i autorzy


Widok



Artykuł
dyskusja
edytuj
historia i autorzy



osobiste


Logowanie i rejestracja






if (window.isMSIE55) fixalpha();

Szukaj



 





nawigacja


Strona główna
Kategorie artykułów
Bieżące wydarzenia
Losuj stronę




zmiany


Zgłoś błąd
Zgłoś złą grafikę
Częste pytania (FAQ)
Kontakt z Wikipedią
Wspomóż Fundację




dla edytorów


Ostatnie zmiany
Zasady edycji
Pomoc
Portal wikipedystów




narzędzia


Linkujące
Zmiany w dolinkowanych
Strony specjalne
Wersja do druku Link do tej wersjiCytowanie tego artykułu



W innych językach


�żŁ"�ą�ąبŁ�ة
�Śesky
Deutsch
Eesti
Ε��ην�ąκ�Ź
English
Espa�ąol
Ł��ż�ą�ł�Ś
Fran�żais
�śę���
�
Italiano
�ó�ęרית
Nederlands
ćĄćśŹŁ�ś
Português
� Ń�Ń�Ń�ки�ą
Suomi
Svenska
ąą"ą�ą�ó
Ti�żng Vi�t
T�źrk�że
中ć
�









Tę stronę ostatnio zmodyfikowano 15:51, 18 lis 2008.
Tekst udostępniany na licencji GNU Free Documentation License. (patrz: Prawa autorskie)
Wikipedia® jest zarejestrowanym znakiem towarowym Wikimedia Foundation. Możesz przekazać dary pieniężne Fundacji Wikimedia.
Zasady ochrony prywatności
O Wikipedii
Informacje prawne




if (window.runOnloadHook) runOnloadHook();