Выберем фразу . Как в примере § ., заменим пробелы символом «_»: МАМА_МЫЛА_РАМУ. Подсчитаем частоты: А — , М — , _ — , Ы — , Л — , Р — , У — . Проверка: символов, столько же во фразе с двумя пробелами.
По алгоритму Хаффмана на каждом шаге соединяем две вершины с наименьшими весами.
Ы() и Л() соединяем в вершину (), потому что обе частоты минимальны.
Р() и У() соединяем в ещё одну вершину (), потому что это оставшиеся частоты, равные .
_() и (Ы, Л)() соединяем в вершину (), поскольку теперь наименьший вес равен .
(Р, У)() и М() соединяем в вершину (): после предыдущего шага среди оставшихся вершин их веса наименьшие.
А() и (_, Ы, Л)() соединяем в вершину (), так как из весов , и выбираем два наименьших.
() и () соединяем в корень (), поскольку остались только эти две вершины.
На каждом разветвлении верхнему ребру припишем , нижнему — . Один из возможных вариантов дерева:
├──
│ ├──
│ │ ├── Р()
│ │ └── У()
│ └── М()
└──
├──
│ ├── _()
│ └──
│ ├── Ы()
│ └── Л()
└── А()
Читаем биты от корня до буквы: Р — , У — , М — , _ — , Ы — , Л — , А — . Например, МАМА кодируется как . Длина кода всей фразы равна бит. Полученное дерево удовлетворяет правилу: ни один код не является началом другого, поскольку символы помещены только в листьях.
