可变长度符号的Huffman编码

Question

我正在考虑使用Huffman代码来压缩文本，但是使用可变长度的符号(字符串)。例如(使用下划线作为空格)：

huffman-code | symbol
------------------------------------
00           | _
01           | E
100          | THE
101          | A
1100         | UP
1101         | DOWN
11100        | .
11101        |
1111...
(etc...)

如何构造频率表？显然存在一些重叠的问题，序列_TH和THE一样经常出现，但是在表中没有用处( _和THE都有简短的huffman代码)。

这样的算法存在吗？有特别的名字吗？生成频率表的诀窍是什么？我需要标记输入吗？我在文具店/网站上没有发现任何东西。(所有这一切使我也想到了基数树)。

我正在考虑使用一个迭代过程：

1. 为长度为1到N的所有符号生成一个huffman树
2. 从树中移除所有具有N>1且低于某个计数阈值的符号
3. 重新生成第二棵赫夫曼树，但这次用上一棵树标记输入(可能使用基树查找)
4. 重复1，直到我们收敛为止(或几次)

但我不知道如何防止与此重叠的问题(_TH与THE)。

Answer 1

只要正确地标记文本，就不必担心重叠问题。您可以将每个标记定义为一个单词(最长的连续字符流)、标点符号或空白字符(‘、’t‘、\n')。因此，根据定义，令牌/符号不重叠。

但是直接使用Huffman编码并不适合压缩文本，因为它不能利用符号之间的依赖关系。例如，'q‘可能后面跟着'u'，'qu’很可能后面跟着元音，‘感谢’很可能后面跟着'you‘等等。您可能需要查看像'LZ‘这样的高阶编码器，它可以利用这种冗余，方法是将数据转换为查找地址序列、复制长度和偏差符号。下面是是LZ如何工作的一个例子。然后，您可以对这三种流中的每一种应用Huffman编码，以进一步压缩数据。放气算法正是这样工作的。

Answer 2

这不是一个完全的解决办法。

由于您必须同时存储序列和查找表，也许您可以贪婪地选择符号，以最小化存储成本。

步骤1:尝试存储所有长度的符号，并记录它们的计数。

步骤2:对于每个可能的符号，计算节省的空间(或压缩比)。

Encode_length(符号)= log(N) -log(计数(符号))

Space_saved(符号)=长度(符号)*计数(符号)-Encode_length(符号)*计数(符号)-(长度(符号)+Encode_length(符号))

N是所有符号的总频率(我们还不知道，也许是近似的)。

步骤3:选择最佳符号并减去与之重叠的其他符号的频率。

步骤4:如果整个序列尚未编码，则选择下一个最佳符号(即转到步骤2)。

注:这只是一个大纲，它既不完整，也不计算效率。如果您正在寻找一个实用的快速解决方案，您应该使用krjampani的解决方案。这个答案纯粹是学术性的。