Как расшифровать дерево Хаффмана?

Есть несколько статей об эффективных алгоритмах декодирования для деревьев Хаффмана. Лично я использовал только один из них, по академическим соображениям, но это было давно. Заголовок статьи был "Эффективная и быстрая память. Алгоритм декодирования Хаффмана» Хун-Чунг Чена, Юэ-Ли Ванга и Ю-Фенг Лана.

Алгоритм дает результаты за O(log n) время. Чтобы использовать этот алгоритм, вы должны построить таблицу со всеми символами вашего дерева (листьями), и для каждого символа вы должны указать вес:

w(i) = 2 ^ (h - l)

где h — высота дерева Хаффмана, а l — уровень символа и количество:

count(i) = count(i-1) + w(i)

Количество корня count(0) равно его весу.

Когда у вас есть все это, в алгоритме есть 3 простых шага, которые описаны в статье.

Не знаю, это ли вы искали.

Да, есть, и вы можете использовать таблицы поиска.

Обратите внимание, что вы будете использовать довольно много памяти для хранения этих таблиц, и вам придется либо отправить эту таблицу с данными (вероятно, полностью сводя на нет эффект сжатия), либо построить таблицу перед распаковкой (что сведет на нет некоторые, если не все ускорение, которое вы получаете от этого.)

Вот как будет работать таблица.

Скажем, для выборки сжатых данных последовательности битов для символов следующие:

1 -> A
01 -> B
00 -> C

Что вы делаете сейчас, так это создаете таблицу, индексированную по байтам (поскольку вам нужно прочитать минимум 1 байт для декодирования первого символа), содержащую такие записи:

key      symbol       bit-shift
1xxxxxxx    A             7
01xxxxxx    B             6
00xxxxxx    C             6

X означает, что вам нужно хранить записи со всеми возможными комбинациями для этих x с этими данными. Для первой строки это означает, что вы создадите таблицу, в которой каждый байтовый ключ с установленным старшим битом будет отображаться в A/7.

В таблице будут записи для всех 256 ключевых значений, половина из которых сопоставлена ​​с A/7, а 25% — с B/6 и C/6, в соответствии с приведенными выше правилами.

Конечно, если самая длинная последовательность битов для символа составляет 9-16 байтов, вам нужна таблица с 16-битным целым числом и так далее.

Теперь, когда вы декодируете, вот как вы это сделаете:

read first and second byte as key, append them together

loop:
   look up the first 8 bits of the current key in the table
   emit symbol found in table
   shift the key bitwise to the left the number of bits specified in the table
   if less than 8 bits left in the key, get next byte and append to key

в конце просто добавьте 0 байтов, и, как и при любой декомпрессии Хаффмана, вам нужно знать, сколько символов выдавать, прежде чем начать.

Конечно, вместо 2-деревьев вы можете использовать k-деревья и получить ускорение O(ln_k(n)) . Это не много.

Если максимальный размер ключа мал (скажем, ‹ 8 бит) или у вас много памяти, вы можете использовать таблицу прямого поиска и получить O (1).