код хаффмана как строить, дерево совсем не понимаю
Задали разобрать алгоритм Хаффмана, надо построить коды для букв по их частотам. Например буквы с частотами: A=5, B=2, C=1, D=1.
Я читал что там какое-то дерево строят, объединяют самые редкие буквы... но у меня получается какая-то ерунда и коды не сходятся с ответом. Можете на этих частотах прям по шагам показать, как строится дерево и откуда берутся 0 и 1?
2 ответа
Хаффман строится снизу вверх. Главная идея: частым буквам — короткие коды, редким — длинные. Делаем так: каждый раз берём ДВЕ самые маленькие частоты, объединяем в один узел с суммой, и повторяем, пока не останется один узел.
Твои буквы: A=5, B=2, C=1, D=1.
Шаг 1. Два самых маленьких: C=1 и D=1. Объединяем → новый узел (CD)=2. Осталось: A=5, B=2, (CD)=2.
Шаг 2. Два самых маленьких: B=2 и (CD)=2. Объединяем → узел (BCD)=4. Осталось: A=5, (BCD)=4.
Шаг 3. Объединяем A=5 и (BCD)=4 → корень = 9. Всё, дерево готово.
Теперь расставляем биты: на каждой развилке левая ветка = 0, правая = 1 (можно наоборот, главное единообразно). Спускаемся от корня к каждой букве и собираем код:
корень
├─0─ A -> A = 0
└─1─ (BCD)
├─0─ B -> B = 10
└─1─ (CD)
├─0─ C -> C = 110
└─1─ D -> D = 111
Итого: A=0, B=10, C=110, D=111. Видишь — частая A получила 1 бит, редкие C и D по 3 бита. Это и есть смысл Хаффмана: экономим на частых.
Лайфхак чтоб не путаться: всегда выписывай частоты в строчку и на каждом шаге подчёркивай два наименьших. Если несколько одинаковых — бери любые два, ответ по длине кодов получится тот же.
И да — коды Хаффмана всегда удовлетворяют условию Фано (ни один не префикс другого), потому что буквы сидят только в листьях дерева.
Где обычно ошибаются: берут не два самых маленьких, а первые попавшиеся, или забывают, что новый объединённый узел ТОЖЕ участвует в следующих шагах наравне с буквами.
Быстрая самопроверка: посчитай сумму (частота × длина кода) по всем буквам — это общая длина закодированного текста, у правильного Хаффмана она минимальна. Если у соседа получилось меньше — где-то ты объединил не те узлы.
