3

我目前正致力于在 Java 中实现一个基于霍夫曼算法的程序，并且我正处于需要将编码内容输出到文件的阶段。我对如何实现解码所需的标头和 eof 有点困惑。对于我现在的标题，我有输入文件中出现的所有唯一值及其频率，但是在一些文章中我看到人们用 0 或 1 代表节点然后频率（我有点困惑因为它没有说明符号是什么）。

另外，对于我理解的EOF，我像符号一样对其进行编码，以便对其进行读取和解码，但是我不确定我可以为它使用什么绝对不会出现的值？我知道它需要 1 的权重，但不确定如何确保它实际上不在文件中。

4

2 回答 2

5

我必须为作业做一次，这就是我们使用的方法。

通过使用 0 和 1 对树的结构（而不​​是频率）进行编码来对标头进行编码。“0”表示沿树移动，“1”表示我们在叶节点处。这导致了一种对树进行唯一编码的预排序遍历。

例如，像 (((ab) c) (de)) 这样的树将被编码为“0001 a1 b1 c01 d1 e”，其中 a,b,c,d,e 是它们的 ASCII 形式。

这是图形形式的树：

     / \
   /\   /\
 /\  c d  e
a  b

对于 EOF，我们使用文件中的最后 3 位来指定需要读取最后两个字节中的多少。一旦我们读取了最后一个字节（所以我们正在处理倒数第二个字节），我们检查了最后 3 位：它们编码了要读取的更多位，减去 6。因此110101xxxxxxx000意味着“读取110101（6 位）并丢弃其他所有内容”。1101011xxxxxx001意思是“读取1101011（7位）并丢弃其余的”等。

这样做意味着我们不必有一个特殊的值来表示 EOF，我们仍然可以一次读取一个字节的文件（尽管我们实际上需要在我们工作的地方读取一个字节）。

（对于EOF我没有读过你的文章，所以我不知道我们的想法是否适用于你的方法。）

于 2011-11-20T02:02:07.367 回答
2

霍夫曼编码指定如何从一些字符序列创建霍夫曼树，然后如何将其编码为位序列。

它没有指定您应该如何对树进行编码或如何准确计算要读取多少位。位的确切计数是一个问题，因为您只能将整个字节保存到文件中。所以你需要一些方法来准确地确定在哪位结束。

对于树的编码，有几个选项。其中之一是记录每个字符的计数，并让解码器从中重建树。其他选择是以某种方式直接对树进行编码，例如使用 0-1 方法管理（我假设您提到的文章）描述。

然后是自适应霍夫曼编码，它根本不需要树，但更复杂。

为了决定何时结束，您可以将字符总数写入文件并使用它来决定何时停止。或者，如果您使用字符计数对树进行编码，则可以免费获得此计数。

另一种选择是使用 EOF 字符。这是 Huffman 树中的一个字符，但不编码任何正常值。假设您正在编码字节，您可以将其想象为第 257 个值。（您可以为 EOF 令牌使用一些正常值，例如零字节，但这需要您绝对确定它不会出现在输入文件中。）

于 2011-11-20T02:31:33.933 回答