4.7. 4.7. Huffman-kód

Huffman-kód – maximális hatásfokú prefix kód.

Tulajdonságok:

1. Monotonitás. Ha akkor

2. A kódfa teljessége. Legyen ekkor minden hosszúságú kódjelsorozat ki van használva a kódolásnál, azaz maga is kódszó vagy egy rövidebb kódszó kiegészítéséből adódik, vagy pedig az egyik kódjel hozzáírásával valamelyik hosszúságú kódszót kapjuk belőle. Ha volna kihasználatlan ág, akkor azt választva ismét prefix kódot kapnánk, melynek viszont kisebb az átlagos kódhossza.

4.31. Megjegyzés. Optimális, bináris kódfa teljes.

3. és az utolsó kódjelüktől eltekintve azonosak.

4.32. Megjegyzés. Összevonási algoritmus. Az optimális kódfa minden végponttól különböző szögpontjából él indul ki, kivéve esetleg egy végpont előtti szögpontot, amelyből él megy tovább, ahol Ekkor

A teljes kódfánál Tehát az első összevonási lépésben az legkevésbé valószínű elemet kell összevonni, míg az összes többiben az legkevésbé valószínűt.

4.13. ábra - Példa Huffman-féle kódolásra 1. változat

Példa Huffman-féle kódolásra 1. változat

4.14. ábra - Példa Huffman-féle kódolásra 2. változat

Példa Huffman-féle kódolásra 2. változat

4.15. ábra - Példa Huffman-féle kódolásra 3. változat

Példa Huffman-féle kódolásra 3. változat

4.16. ábra - Példa a Huffman kódolásra

Példa a Huffman kódolásra

4.17. ábra - Példa a Huffman kódolásnál az eloszlás ellenőrzésére

Példa a Huffman kódolásnál az eloszlás ellenőrzésére

4.18. ábra - Példa a Huffman kódolásra 1. rész

Példa a Huffman kódolásra 1. rész

4.19. ábra - Példa a Huffman kódolásra 2. rész

Példa a Huffman kódolásra 2. rész