霍夫曼编码与可变长度符号

Question

我计划使用Huffman编码来压缩文本，但是要用长度不同的符号(字符串)。例如(使用下划线作为空格):

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直到我们收敛（或者重复几次）

但我无法解决这个问题：如何避免这种重叠问题（_TH vs THE）。

- Laurent Grégoire

Answer 1

只要您适当进行文本标记化，就不必担心重叠问题。您可以定义每个标记为单词(最长连续字符流)、标点符号或空格字符(' ','\t',\n')，因此按定义，标记/符号不会重叠。

但是直接使用Huffman编码并不理想，因为它不能利用符号之间的依赖关系。例如，'q'后面很可能跟着'u'，'qu'后面很可能跟着元音，'thank'后面很可能跟着'you'等。您可能需要研究一种高阶编码器，如'LZ'，它可以利用这种冗余性，将数据转换为查找地址、复制长度和偏移符号的序列。这里是LZ工作原理的示例。然后，您可以在每个三个流上应用Huffman编码来进一步压缩数据。DEFLATE算法正是以这种方式工作的。

- krjampani

---

很不幸，这个答案中的两个链接现在都已经失效了。 - Kusalananda

Answer 2

这不是一个完整的解决方案。

由于您需要存储序列和查找表，因此您可以贪心地选择最小化存储成本的符号。

步骤1：在尝试中存储长度不超过k的所有符号，并跟踪它们的计数

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

Encode_length(symbol) = log(N) - log(count(symbol))

Space_saved(symbol) = length(symbol)*count(symbol) - Encode_length(symbol)*count(symbol) - (length(symbol)+Encode_length(symbol))

N是所有符号的总频率（我们还不知道，也许是近似值？）。

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

步骤4：如果整个序列还没有编码，请选择下一个最佳符号（即进入步骤2）

注意：这只是一个概要，既不完整也不计算效率。如果您正在寻找实际快速解决方案，则应使用krjampani的解决方案。此答案纯粹是学术性的。

- ElKamina