Алгоритм Хаффмана является алгоритмом префиксного кодирования: символы произвольного алфавита кодируются двоичными последовательностями различной длины таким образом, что ни один более короткий код не является префиксом более длинного. При этом, для достижения оптимального кодирования, наиболее часто встречающиеся символы кодируются наиболее короткой последовательностью, а наиболее редко встречающиеся – наиболее длинной.
Для построения кода, всем символам алфавита присваиваются значения приоритетов, соответствующие частоте появления символа.
Затем два символа с наименьшим значением приоритета “склеиваются”, образуя при этом бинарное дерево (выбор символов с одинаковым приоритетом произволен). Результат получает приоритет, равный сумме приоритетов входящих в него символов. Процесс продолжается, пока в итоге не останется одно бинарное дерево.
После этого, “левым” ветвям дерева (с более низким приоритетом) присваивается код “0”, а “правым” (с более высоким) – “1”. Кодом символа является последовательность кодов ветвей, приводящих к нему.
Например, нам нужно оптимально закодировать сообщение “шла_Маша_по_шоссе”. Всего сообщение состоит из 17 символов. Символы алфавита и их приоритеты:
| Символ | Приоритет |
|---|---|
| _ | 3 |
| ш | 3 |
| a | 3 |
| о | 2 |
| с | 2 |
| л | 1 |
| M | 1 |
| п | 1 |
| е | 1 |
“Склеим” символы “п”, “е”:
| Символ | Приоритет |
|---|---|
| _ | 3 |
| ш | 3 |
| a | 3 |
| о | 2 |
| с | 2 |
| пе | 2 |
| л | 1 |
| M | 1 |
Теперь “л” и “м”
| Символ | Приоритет |
|---|---|
| _ | 3 |
| ш | 3 |
| a | 3 |
| о | 2 |
| с | 2 |
| пе | 2 |
| лМ | 2 |
Теперь “пе” и “лМ”:
| Символ | Приоритет |
|---|---|
| пелМ | 4 |
| _ | 3 |
| ш | 3 |
| a | 3 |
| о | 2 |
| с | 2 |
Действуя далее аналогично:
| Символ | Приоритет |
|---|---|
| пелМ | 4 |
| ос | 4 |
| _ | 3 |
| ш | 3 |
| a | 3 |
| Символ | Приоритет |
|---|---|
| аш | 6 |
| пелМ | 4 |
| ос | 4 |
| _ | 3 |
| Символ | Приоритет |
|---|---|
| _ос | 7 |
| аш | 6 |
| пелМ | 4 |
| Символ | Приоритет |
|---|---|
| ашпелМ | 10 |
| _ос | 7 |
| Символ | Приоритет |
|---|---|
| _осашпелМ | 17 |
Приоритет последнего оставшегося узла равен длине сообщения.
Изображение соответствующего дерева:
Таким образом, коды символов:
| Символ | Приоритет | Код |
|---|---|---|
| _ | 3 | 00 |
| о | 2 | 010 |
| с | 2 | 011 |
| a | 3 | 100 |
| ш | 3 | 101 |
| п | 1 | 1100 |
| е | 1 | 1101 |
| л | 1 | 1110 |
| M | 1 | 1111 |
Средний информационный вес символа по формуле Шеннона: \[ H = 4\frac{1}{17}\log_2 17 + 2 \frac{2}{17}\log_2 \frac{17}{2} + 3 \frac{3}{17}\log_2 \frac{17}{3}\] \[ H = \log_2 17 - \frac{9}{17}\log_2 3 - \frac{4}{17} \] \[ H \approx 3.013 \]
Средний информационный вес по расчету:
\[ H = \frac{2\cdot 3+2\cdot 3\cdot 3+2\cdot 2\cdot 3+4\cdot 4}{17} \approx 3.059 \]
Разница оценки по формуле Шеннона и фактической величины не превосходит \[\frac{1}{17} \approx 0.06\]
С ростом общего числа символов в сообщении это различие будет становиться все меньше.