Архиватор · Шаг 1 из 4
Дерево Хаффмана
Сжатие по Хаффману даёт частым символам короткие коды, а редким — длинные. Коды берутся из дерева: его строят снизу, раз за разом соединяя два самых редких куска в один. Буква «а» в русском тексте встречается в сотню раз чаще «ъ» — и получит код в три бита вместо десяти.
Что сделать
Постройте дерево Хаффмана по частотам символов — строго по правилу ничьих, чтобы архив распаковался чем угодно.
Что приходит
chastoty— словарь «символ → сколько раз встретился»; символы — числа или строки
Что вернуть
Дерево: лист — сам символ, узел — пара (левое, правое); один символ — он сам; пустой словарь — None.
Допишите функцию derevo в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
В проекте
Архиватор строит дерево по частотам байтов файла, а распаковщик — заново, по частотам из архива. Одно и то же дерево у обоих выходит только благодаря правилу ничьих.
{97: 5, 98: 2, 99: 1}: сначала соединяются два самых редких — 99 (раз) и 98 (два раза) — в узел (99, 98) весом 3. Потом он и 97 — в корень. Ответ ((99, 98), 97).
derevo({97: 5, 98: 2, 99: 1})
((99, 98), 97)
Каждому символу — номер: символы по возрастанию получают номера 0, 1, 2… Каждый новый узел получает следующий свободный номер.
Пока кусков больше одного: взять кусок с наименьшим весом (при равных весах — с меньшим номером), потом таким же правилом второй. Соединить их в узел (первый, второй) — первый слева, — с весом, равным сумме, и вернуть в общую кучу.
Оставшийся кусок — ответ. Один символ — ответ сам символ (кортежем его не оборачивать). Пустой словарь — None.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.