使用霍夫曼代码压缩文件的步骤 [英] Steps to compress a file using Huffman Code

问题描述

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

I know there are many questions involving Huffman Code, including another one from myself, but I am wondering what would be the best way to actually encode a text file. Decompression seems trivial; traversing the tree, going left at 0 and right on 1, printing the character.

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

Though, how does one go about compression? Somehow store the bit representation of the character in it's node the tree? Search the tree for the character each time it is encountered and trace the steps? Does it matter which way this is coded?

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

Thus far, I have a huffman tree where the leaf nodes do not have a binary value associated with them. My trouble is assigning the binary values to each character in the tree.

谢谢

推荐答案

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

Well, if you are going to encode a file on a character basis, i can't see the problem, just keep the hash table of symbols, then construct a tree & write it in the beginning of a file using whatever convention you want, hten apply new alphabet to the text. Take a look at the approach taken in DEFLATE, which is used to compress PNG images.

编辑

目前还不清楚问题出在哪里.

It is not really clear what the problem is.

在树中搜索每个字符 遇到的时间并追踪 步骤?

Search the tree for the character each time it is encountered and trace the steps?

树中的每个节点代表一个唯一的符号.您无需搜索任何内容，只有在已经计算了每个符号的出现次数之后，您才能构造霍夫曼树.

Each node in the tree represents an unique symbol. You don't have to search for anything, you can construct the Huffman tree only when you have already calculated each symbol's occurrence.

因此，您已经开发了一种构造树的算法，问题在于如何将二进制值分配给节点?还是在哪里存储这些值?树本身很自然地表示二进制值，您实际上可以在树的构造过程中跟踪它们，只需在插入操作中跟踪项路径"并将其存储在节点中即可；如果不这样做，则可以创建哈希表要修改节点实体.

So you have already developed an algorithm to construct a tree and the problem is about how to assign the binary values to the nodes? Or where to store these values? The tree itself represents binary values naturally, you can actually track them during the tree construction, just keep the track of an items 'path' in the insert operation and store that value inside a node, or create a hash table if you don't want to modify the node entity.

这篇关于使用霍夫曼代码压缩文件的步骤的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！