具有可变长度符号的霍夫曼编码

Question

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

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

如何构建频率表？显然存在一些重叠问题，序列_TH出现的频率几乎与 一样THE，但在表中毫无用处（_和THE都有短霍夫曼代码）。

这样的算法存在吗？它有一个特殊的名字吗？生成频率表有哪些技巧？我需要对输入进行标记吗？我在文献/网络中没有找到任何内容。（所有这些让我也想到了基数树）。

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

1. 为长度为 1 到 N 的所有符号生成哈夫曼树
2. 从树中删除所有 N>1 且低于特定计数阈值的符号
3. 重新生成第二棵霍夫曼树，但这次用前一个树对输入进行标记（可能使用基数树进行查找）
4. 重复1直到我们收敛（或几次）

但我不知道如何防止重叠（_THvs THE）的问题。

Answer 1

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

但直接使用霍夫曼编码对于压缩文本来说并不理想，因为它无法利用符号之间的依赖关系。例如，“q”后面可能跟着“u”，“qu”后面可能跟着元音，“thank”后面可能跟着“you”，等等。您可能想要研究像“LZ”这样的高阶编码器，它可以通过将数据转换为查找地址、复制长度和偏差符号的序列来利用这种冗余。举个例子来说明LZ的工作原理。然后，您可以对三个流中的每一个应用霍夫曼编码以进一步压缩数据。DEFLATE算法正是以这种方式工作的。