Изменения

Пусть <tex>A=\{a_{1},a_{2},...\ldots ,a_{n}\}</tex> — алфавит из <tex>n </tex> различных символов, <tex>W=\{w_{1},w_{2},...\ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...\ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:

1. * <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,

2. Сумма * cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)

Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева ]] по следующему алгоритму:

* # Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.* # Из списка выберем два узла с наименьшим весом.* # Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.* # Добавим к списку только что сформированный узел вместо двух объединенных узлов.* # Если в списке больше одного узла, то повторим пункты со второго по пятый.

[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для строки "слова <tex>abracadabra</tex>"]]

Закодируем слово "<tex>abracadabra</tex>". Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемой строкекодируемом слове) <tex>W=\{5, 2, 2, 1, 1\}</tex>:

Затем опять объединим в один узел два минимальных по весу узла: {{---}} <tex>r</tex> и <tex>cd</tex>:

На последнем шаге объединим два узла <tex>brcd</tex> и <tex>a</tex>.:

Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово: бинарную (бинарная последовательность, обозначающую обозначающая путь по дереву к этому символу от корня ):

Таким образом, закодированное слово "<tex>abracadabra</tex>" будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов (англ. ''Constant length coding''), то закодированная строка заняла закодированное слово заняло бы <tex>33</tex> бита, что существенно больше.