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

Question

есть ли лучший способ, чем просто идти влево или вправо на основе введенной цифры 0 или 1?

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Допустим, для выборочной части сжатых данных битовые последовательности для символов выглядят следующим образом:

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

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

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

Символ х означает, что вам необходимо хранить записи со всеми возможными комбинациями этих х с этими данными.Для первой строки это означает, что вы должны создать таблицу, в которой каждый байт-ключ с установленным старшим битом будет отображаться в 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 байтови, как и при любой декомпрессии Хаффмана, вам нужно знать, сколько символов испустить, прежде чем начать.

Answer 3

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

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