Эффективная передача кодов Хаффмана?

Question

[agorkov]

Моя научная работа связана с компрессией данных и сейчас я пытаюсь решить одну весьма специфическую задачу.


Есть входной алфавит из N m-битных  чисел (N>=10^6; m=24). Для каждого из N символов известна частота его появления. На основе этой информации для всех символов получены коды Хаффмана.


Задача заключается в том, чтобы создать передачу из которой можно однозначно восстановить как сами m-битные числа, так и их Хаффмановские коды. Разумеется, передача должна иметь минимально возможный объём.


Вариант, до которого я сам додумался требует N*(m+2)-1 бит. Если у кого-то получится улучшить мой результат, поделитесь вашим решением.

Comments

[Mrrl]

Есть ли какие-нибудь ограничения на число символов, по которому строилась статистика? Потому что в общем случае, когда максимальная длина кода одного из символов может равняться N-1, Ваш результат улучшить трудно, но в реальности длина ограничена более разумным числом (логарифмом объема входных данных). И какое ожидается соотношение между N и m, т.е. какая доля m-битных чисел присутствует в алфавите?

Answer 1

[Mrrl]

Что-то не так в условии. 24-битных чисел всего 16*10^6, их никак не наберется 2^9.
И вопрос — нужно получить именно заданные коды Хаффмана, или достаточно, чтобы получились какие-нибудь эквивалентные по длине (а алгоритмы упаковки и распаковки сами договорятся, чтобы распакованные коды были именно теми, которые используются при упаковке основного сообщения)?

Comments

[Mrrl]

* имелось в виду не 2^9, а 10^9

[agorkov]

Конечно, имелось в виду 10^6 символов. Но задача на самом деле более общая: эффективно передавать деревья для произвольных и весьма больших m и N.

[Mrrl]

10^6 это уже хорошо. Тогда остается вопрос, достаточно ли закодировать какой-нибудь из эквивалентных кодов и какова максимальная глубина дерева (она зависит от размера исходной статистики). Если одного кода хватит, а глубина, скажем, не больше 31, то достаточно 21 бита на символ (точнее, 2^m+N*5 на весь букварь): маска присутстующих символов и длина кода каждого из них.

[agorkov]

Нужно передавать именно Хаффмановские коды. Максимальная высота дерева может быть равна N-1. И такие ситуации точно будут встречаться.

[Mrrl]

Чтобы глубина равнялась N-1, нужно, чтобы частота одного из символов была не больше phi^(-N), т.е. 1 символ на 10^200000. Я верю, что когда-нибудь мы будем работать с такими объемами информации — но когда?
И «Нужно передавать именно Хаффмановские коды» — это ответ не на тот вопрос. Вопрос был: если заданный код — {0,10,11}, а алгоритм будет выдавать {1,00,01}, это будет недопустимо, или можно как-нибудь договориться с генератором кода?

Answer 2

[Mrrl]

В случае, если нужно передать действительно произвольный код Хаффмана, то выиграть почти ничего нельзя. Код определяется N-элементным вектором m-битных чисел (с условием, что все элементы различны) — это буквы, отсортированные по кодам, и расстановкой скобок в выражении из N операндов — это двоичное дерево. Число векторов равно (2^m)!/(2^m-N)!, число деревьев — C(N,2*N)/(4*N-2). Если N заметно меньше, чем 2^m, то первое из этих чисел можно оценить как 2^(m*N), а второе — как 2^(2*N)/(4*N-2)/sqrt(pi*N). Общее число бит в их произведении — примерно m*N+2*N.
По мере приближения N к 2^m появляется возможность выиграть до 1.4*N бит (за счет того, что (2^m)!< (2^m)^(2^m).