Эффективная реализация алгоритма Хаффмана?

Question

[agorkov]

По ходу моей научной работы возникла необходимость подсчитать эффективность кода Хаффмана для алфавита из 300 млн. элементов.


Сам алгоритм тривиален, и его реализация не представляет труда. Но на реальной задаче алгоритм работает непозволительно долго. В связи с этим у меня два вопроса:

1. Существуют ли какие-нибудь оптимизации алгоритма по скорости?

2. Насколько адекватной оценкой сверху будет использование кодов Шеннона-Фано?

Comments

[Weageoo]

Уточните, проблема в том, что алгоритм Хаффмана медленно генерирует преффиксные коды для заданного набора {символ; частота}?

Answer 1

[Weageoo]

1) Арифметическое кодирование эффективнее.
2) Алгоритма Хаффмана (или другой алгоритм энтропийного кодирования) используется на шаге фактического сжатия в статистическом алгоритме сжатия данных без потерь PPM (вот для этого алгоритма уже существует множество модификаций; напр. PPMd используется в Rar, 7zip, WinZip).
3) Существует адаптивный алгоритм Хаффмана. Есть и его имплементация на C. Если будете тестировать (сравнивать с обычным хаффманом), то напишите пару слов о результатах.

Comments

[agorkov]

1. Код Хаффмана не обладает префиксным свойством, а значит, не подходит для моих задач.
2. Этот алгоритм много где используется, но не используется алфавит на 300 млн образов. Проблема не в реализации, а в её скорости.
3. Адаптивный алгоритм это другое. Он используется, если неизвестна частота символов в алфавите.

[Weageoo]

Где ж вы такой алфавит-то выкопали из 300 млн. элементов… На самом деле, надеюсь вы не изобретали велосипед может быть неэффективной конкретно ваша реализация, желательно избавится от всех нехвостовых рекурсий (лучше вообще без них). Лучше взять эту или эту имплементацию, протестить.

[Weageoo]

Вряд ли есть способ оптимизировать именно построение оптимального префиксного дерева по алгоритму Хаффмана.

[mejedi]

На 300 млн. имхо что угодно будет тормозить. Например упомянутое арифметическое кодирование — оценить «эффективность» (в смысле сколько бит потребуется для хранения сжатой строки S) легко, а вот реально сжать или разжать — очень небыстро. Потом таблицу частот символов тоже как-то хранить надо?

Посмотрите ради интереса кодировку ORDPATH — может вам этот метод подойдет. На пальцах — квантуем вероятности, и разбиваем все множество символов на группы с одинаковой вероятностью (после квантования). Групп будет сильно меньше чем всего символов. Для кодирования группы используются префиксные коды как в хаффмане. Для кодирования символа используется конкатенация кода группы + номер символа в группе (обычная двоичная кодировка, число разрядов зависит от размера группы).

И оценить, насколько это будет менее эффективно по сравнению с идеальным хаффманом, вроде несложно.

Answer 2

[mayorovp]

Классическим способом ускорения алгоритма Хаффмана является слияние с виртуальным списком.

А именно, заводятся два списка — исходный и очередь.
В начала алгоритма исходный список сортируется по возрастанию частот, очередь пуста.

В процессе работы поддерживается следующий инвариант — элемент с минимальной частотой лежит либо в начале очереди, либо в начале исходного списка.
Шаг алгоритма следующий: извлекаются два минимальных элемента (оба из исходного списка, оба из очереди лили один из исходного, а второй из очереди) и «склеиваются», результат помещается в конец очереди.
Когда в обоих списках остался последний элемент — требуемое дерево построено.

Comments

[agorkov]

Именно так я и делал, но всё равно спасибо.

[mayorovp]

Так и делали, но все равно долго?
В таком случае проблема в сортировке (поскольку порядок сортировки — N logN, а остального алгоритма — N)

Скажите, какой примерный диапазон частот ожидается? Сколько символов в типовом тексте?
Можно попробовать сортировку подсчетом или комбинированную.

Так, если размер текста ограничен числом M, порядка менее (N/log N)^2, то можно попробовать частоты до sqrt(M) упорядочить подсчетом, а более высокие — классическим способом.

[agorkov]

Диапазон частот от ~0.5 до 1/300^6. Размер текста на порядок больше размера алфавита.