Сколько бит займёт текст
Архивист хочет заранее знать, сколько места займёт текст, если закодировать его кодом Хаффмана. Сам код ему не нужен — только итог: сколько бит займут все знаки текста вместе, если у каждого знака свой двоичный код, ни один код не начинает другой, а длины кодов выбраны наилучшим образом. Служебные данные — таблицу кода, заголовки — не считаем.
Известно, сколько раз встречается каждый знак. Если знак в тексте один, ему всё равно нужен код хотя бы из одного бита.
Среди тестов — знаки «Войны и мира» и её английского перевода, слова романа и буквы генома фага лямбда.
Вход
В первой строке число разных знаков n (1 ≤ n ≤ 200 000). Во второй — n чисел: сколько раз встречается каждый знак, от 1 до 109.
Выход
Одно число — наименьшее суммарное число бит.
Примеры
Пример 1
5 15 7 6 6 5
87
Пример 2
1 42
42
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Наилучшие длины кодов даёт код Хаффмана. Но строить дерево и обходить его, чтобы узнать глубины листьев, не обязательно.
2Подсказка 2
Каждая склейка двух деревьев с весами a и b опускает все листья обоих деревьев на один уровень. На сколько бит при этом удлиняется закодированный текст?
3Подсказка 3
Ответ на прошлую подсказку — ровно на a + b: каждое вхождение каждого знака из этих деревьев получает ещё один бит.
4Идея
Цена кода Хаффмана равна сумме весов всех склеек. Это видно и из дерева: вес внутреннего узла — сколько раз через него проходят коды знаков, а каждый такой проход — один бит. Поэтому достаточно кучи с числами: достаём два наименьших, прибавляем их сумму к ответу и кладём сумму обратно.
5Разбор
n − 1 раз: два извлечения из кучи, сложение, вставка. Ответ для знаков «Войны и мира» — 14 119 218 бит, ровно столько считает листинг из статьи.
Первый пример — тот, где сверху получается хуже. Шеннон — Фано делит частоты 15, 7, 6, 6, 5 на {15, 7} и {6, 6, 5}, коды 00, 01, 10, 110, 111 и всего 89 бит. Хаффман склеивает 5 + 6 = 11, 6 + 7 = 13, 11 + 13 = 24, 15 + 24 = 39: сумма 87, у частого знака код из одного бита.
Знак один — склеек нет, но код из нуля бит не годится: получатель не узнает, сколько знаков в тексте. Ответ — его число вхождений.
5+Решение
6Сложность
O(n log n) с кучей. Если частоты отсортировать, хватит двух очередей и O(n) после сортировки: суммы склеек выходят неубывающими.
7Типичные ошибки
- Деление сверху. Код Шеннона — Фано не всегда оптимален (первый пример).
- 32 бита. В девятом тесте ответ около 2·1015; уже сумма двух частот может не влезть в
int32. В Go беритеint64. - Числа с плавающей точкой.
float64точно хранит целые только до 253 ≈ 9·1015; здесь хватает, но привычка опасная. - Один знак. Цикл склеек не выполняется ни разу, и ответ 0 — неверный.
- Сортировка один раз. После склейки сумма должна вернуться в кучу на своё место: если просто склеивать соседей отсортированного списка слева направо, дерево станет гусеницей.