algorithm - 如何解码霍夫曼树？

Question

有没有比根据输入数字 0 或 1 向左或向右走更好的方法？

Answer 1

有一些关于霍夫曼树的有效解码算法的论文。就个人而言，出于学术原因，我只使用了其中一个，但那是很久以前的事了。论文的标题是陈洪中、王跃丽和蓝玉峰的“一种高效记忆的快速霍夫曼解码算法”。

该算法O(log n)及时给出结果。为了使用这个算法，你必须用你的树（叶子）的所有符号构建一个表，并且你必须为每个符号指定一个权重：

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

其中 h 是 Huffman 树的高度，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

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 字节填充，并且与所有 Huffman 解压缩一样，您需要知道在开始之前要发出多少个符号。

Answer 3

当然，您可以使用 k-trees 而不是 2-trees 并获得 O(ln_k(n)) 加速。这并不多。

如果最大密钥大小很小（比如 < 8 位）或者你有很多内存，你可以使用直接查找表并得到 O(1)。