Чтобы построить дерево Хаффмана для фразы «Мама мыла раму», нужно выполнить следующие шаги:

1. Сделать частотный анализ. 5 Записать, сколько раз встречается каждая буква в фразе: 5 м — 3 раза, а — 3 раза, ы — 1 раз, л — 1 раз, р — 1 раз, у — 1 раз. 5

2. Построить бинарное дерево таким образом, чтобы сумма частот для каждого поддерева была минимальной. 5 Листьями дерева являются символы, а корнем — сколько раз в тексте символы встречаются, суммарно. 5

3. Взять две буквы, которые встречаются реже всего, и сделать поддерево. 5 Начнём слева направо, с букв ы и л. 5 Они встречаются 1 раз каждая. 5

4. Взять буквы р и у, они тоже встречаются по одному разу. 5 Сделать слияние этих двух деревьев (так как сумма будет = 4, что меньше, чем если бы добавить к любому из деревьев буквы м или а). 5

5. Добавить к получившемуся букву м, и потом букву а. 5

6. Каждому переходу налево присвоить 0, а переходу направо — 1 (можно и наоборот, результат не изменится). 5

7. Записать фразу в битах, записывая переходы нулями и единичками. 5 Так, букве а соответствует 1, букве м — 01, букве у — 0011, и так далее. 5

Коды Хаффмана минимизируют среднюю длину битовой последовательности для данной фразы. 1