Кто-нибудь знает, как декодировать дерево хаффмана?

Question

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

Answer 1

Есть некоторые документы об эффективных алгоритмах декодирования для деревьев Хаффмана. Лично я использовал только один из них по академическим причинам, но это было давно. Название статьи: «A Memory Efficient and Fast Huffman Decoding Algorithm" by Hong-Chung Chen, Yue-Li Wang and Yu-Feng Lan.

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

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

где Н представляет собой высоту дерева Хаффмана и л является уровнем символа, и отсчет:

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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