April 12th, 2013

nyaload

length limited huffman coding

Захотелось мне недавно сделать так, что бы код Хаффмана был не длинее чем 16 бит. Что бы расшифровщик был простой-простой и быстрый, с минимумом ветвлений -
таблица [произвольные 16 бит из потока] -> [символ; сколько бит потока пропустить].

Прочитал про мега-алгоритм с монетками на википедии (package-merge algorithm). Понял, что я его буду делать долго-долго. Сделал очень просто, генерирую коды Хаффмана много раз. Каждый раз - добавляю возрастающую (экспоненциально на 10%) константу к частотам, пока коды не станут короткими настолько, что самый длинный уместится в 16 бит. Разница между размерами файла при идеальном неограниченном коде, и при таком тупо-переборном ограниченном - на 0.2 процента.

Более того, алгоритм, который я много раз запускаю — хуже квадратичного, N раз сортирую ~N элементов. Не писать же 5 багоопасных строк вставки в сортированный массив, если можно просто отсортировать :) Таблица всего лишь для сотни разных символов, и генерится меньше секунды. По сравнению с записью, чтением и обработкой гигабайтов с диска - всё равно ерунда. Хороший компромисс между простотой-эффективностью. Итого: код помещается на одном экране, на общую производительность тупость алгоритма не влияет (я даже не мерял, сколько он там тупит - 0.01 секунды или 1.5).