4

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

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）的问题。

4

2 回答 2

3

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

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

于 2014-09-06T15:33:59.807 回答
1

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

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

第 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 的解决方案。这个答案纯粹是学术性的。

于 2014-09-06T15:40:45.000 回答