tree - 使用 Huffman 代码压缩文件的步骤

Question

我知道有很多涉及霍夫曼代码的问题，包括我自己提出的另一个问题，但我想知道实际编码文本文件的最佳方法是什么。减压似乎微不足道；遍历树，在 0 处向左，在 1 处向右，打印字符。

但是，如何进行压缩？以某种方式将字符的位表示存储在树的节点中？每次遇到字符时都在树中搜索并跟踪步骤？以哪种方式编码有关系吗？

到目前为止，我有一个霍夫曼树，其中叶节点没有与之关联的二进制值。我的麻烦是将二进制值分配给树中的每个字符。

谢谢

Answer 1

好吧，如果您要基于字符对文件进行编码，我看不出问题，只需保留符号的哈希表，然后构造一棵树并使用您想要的任何约定将其写入文件的开头， hten 将新字母应用于文本。看看DEFLATE中采用的方法，它用于压缩 PNG 图像。

编辑

目前还不清楚问题是什么。

每次遇到字符时都在树中搜索并跟踪步骤？

树中的每个节点都代表一个唯一的符号。您不必搜索任何内容，只有在您已经计算了每个符号的出现时，您才能构建霍夫曼树。

所以你已经开发了一种算法来构造一棵树，问题是如何将二进制值分配给节点？或者在哪里存储这些值？树本身自然地表示二进制值，您实际上可以在树构造期间跟踪它们，只需在插入操作中跟踪项目“路径”并将该值存储在节点内，或者如果不创建哈希表想要修改节点实体。