Как построить дерево Хаффмана для фразы «Мама мыла раму»?

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

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

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

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

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

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

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

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

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