Konstrukcję optymalnego kodu prefiksowego zaproponował David Huffman. W tym punkcie wykładu przedstawimy metodę budowy drzewa kodowego dla optymalnego kodu prefiksowego Huffmana.

Drzewo kodowe Huffmana jest drzewem binarnym, lokalnie pełnym. W każdym wierzchołku wewnętrznym tego drzewa pamiętamy sumę częstości znaków występujących w poddrzewach tego wierzchołka. Każdy wierzchołek drzewa będzie więc miał, oprócz referencji do lewego i prawego poddrzewa, atrybut f, oznaczający częstość występowania znaku lub grupy znaków odpowiadających drzewu o korzeniu w tym węźle. W liściach będą pamiętane dodatkowo znaki kodowanego alfabetu. Do zapamiętania alfabetu oraz wierzchołków tworzonego drzewa, algorytm Huffmana używa kolejki priorytetowej.

1. Utwórz kolejkę priorytetową pq zawierającą węzły tworzonego drzewa. Początkowo elementami kolejki są liście drzewa. Porządek elementów w kolejce priorytetowej zależy od częstości przypisanej znakom.

2. Drzewo kodowe buduje się od dołu, od liści, które są traktowane jako drzewa z jednym tylko węzłem. W każdym kroku algorytmu, zamiast kolejnych dwóch wierzchołków, których częstości są najmniejsze, wstawiamy do kolejki priorytetowej pq nowy węzeł, którego etykietą jest suma częstości przypisanych usuniętym węzłom. Punkt 2 powtarzamy, tak długo, aż w kolejce priorytetowej pozostanie tylko jeden element. Będzie to korzeń drzewa kodowego.

Algorytm Huffmana można zaimplementować na wiele sposobów, które zależą od konkretnej implementacji kolejki priorytetowej. Jedną z możliwości, jest użycie kopca zaimplementowanego w tablicy. Opracowanie szczegółów tego algorytmu pozostawiamy Czytelnikowi jako ćwiczenie. Zwróćmy uwagę, że algorytm Huffmana w pewnych przypadkach może działać niejednoznacznie, w tym sensie, że jeśli częstości występowania dwóch grup znaków są takie same, to wybór kolejności odpowiadających im węzłów można ustalić dowolnie, gdyż nie ma on wpływu na długość otrzymanego kodu, ale drzewa kodowe mogą się różnić.

W przedstawionym poniżej algorytmie "HuffmanKod" zakładamy, że TAB jest tablicą,w której znajdują się znaki kodowanego alfabetu oraz ich częstości występowania w pewnym pliku.

HuffmanKod(TAB : tablica){
	//utwórz kolejkę priorytetową z elementów //danej tablicy TAB , uporządkowaną //ze względu na atrybut f
	n := TAB.length;	// n jest liczbą znaków alfabetu
	for i :=1 to (n-1) do
	v := new node;
	v.left := min(pq); pq := delmin(pq);	// min(pq) wybiera węzeł o najmniejszym atrybucie f
	v.right := min(pq); pq := delmin(pq);
	v.f := v.left.f + v.right.f
	pq := insert(v,pq);	//dołączenie nowego węzła do kolejki priorytetowej
	od;
}

Algorytm rozpoczynamy od utworzenia kolejki priorytetowej, której elementami są liście tworzonego drzewa kodowego. Koszt utworzenia tej kolejki, o ile zastosujemy algorytm konstrukcji kopca w tablicy, wynosi O(n), gdzie n jest liczbą znaków kodowanego alfabetu. W drugiej części algorytmu konstruujemy drzewo. Zauważmy, że po n-1 krokach, gdzie n jest liczbą znaków kodowanego alfabetu, kolejka zawiera tylko jeden węzeł. Rzeczywiście, w każdej iteracji, z kolejki są wyjmowane dwa elementy i wstawiany jeden nowy węzeł. Oznacza to, że po każdej iteracji liczba elementów zmniejsza się o jeden. Jeśli kolejka priorytetowa została zaimplementowana jako kopiec, to każda z wykonywanych w pętli operacji kosztuje O(lg n) porównań. Wynika stąd, że koszt wykonania pętli "for" możemy oszacować z góry przez O(n ´ lg n). Ostatecznie, koszt całego algorytmu możemy oszacować przez O(n ´ lg n).

Uwaga Algorytm Huffmana jest algorytmem zachłannym w tym sensie, że w każdym kroku wybiera węzły o najmniejszej częstości.

Przyjmijmy, że w pewnym tekście występują tylko litery A, F, H, M, N, U, a ich częstości występowania w tysiącach wynoszą odpowiednio:40,8,9,11,7,25. Kolejne fazy działania algorytmu Huffmana przedstawiono na rysunku 11.3.

Z otrzymanego drzewa kodowego łatwo odczytujemy kody liter A - 0, F - 1101, H - 1110, M - 1111, N - 1100, U - 10 . Ciąg 11101011011101111101100 jest kodem słowa HUFFMAN.

Pytanie 4: Czy koszt algorytmu Huffmana zmieni się, jeśli zamiast struktury kopca, użyjemy tablicy uporządkowanej za pomocą optymalnego algorytmu sortowania, a wstawianie nowego węzła do tablicy zrealizujemy tak jak w algorytmie InsertionSort?