Huffman

哈弗曼编码是一个很经典的压缩算法，压缩率能达到50%，甚至更低。它的基本原理包括四个步骤： 统计文件中每个字符出现的频率。 构建一个哈弗曼树。建树的过程是不断的合并频率最小的两个节点，父亲节点的频率为两个孩子节点的频率之和。如此循环直到合并成一个根节点。叶子节点为不同的字符及其频率。 生成哈弗曼编码。从树根开始对树进行编码，比如进入左孩子的边标记为0，进入右孩子的边标记为1，这里的0和1都是二进制位。这样之后，每个叶子节点都有一个唯一的二进制编码，这就是哈弗曼编码。频率越低的字符哈弗曼编码越长，频率越高的字符哈弗曼编码越短，这样就能起到压缩的效果。 第二遍扫描文件，把字符转换为对应的哈弗曼编码，保存成压缩文件。 解压缩的过程就是解析二进制位，然后查找哈弗曼树，每找到一个叶子节点，就解析出一个字符，直到解析完所有二进制位。下面详细解释我的C++实现。 首先定义一个哈弗曼编码类，对外只提供压缩Compress和解压缩Decompress两个接口。值得注意的是有一个Node结构体，用于构成哈弗曼树的节点。此外count_node的key是字符频率，value是所在节点，且是multimap类型的，所以count_node会自动按字符频率有小到大排序，在构建哈弗曼树时，每次只需要取count_node的前两个节点进行合并即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class HuffmanCode { public: HuffmanCode(); void Compress(string src, string dest); void Decompress(string src, string dest); virtual ~HuffmanCode(); private: void CountLetter(string src); void ConstructHuffmanTree(); void GenerateHuffmanCode(); void WriteHuffmanCode(ofstream &os); void Compressing(string src, string dest); void InsertIntoHuffmanTree(char letter, string &code, int &k); void ConstructHuffmanTreeFromFile(ifstream &is); void Decompressing(ifstream &is, ofstream &os); map<char, int> letter_count; typedef struct Node { int id; bool is_leaf; char letter; int parent, lchild, rchild; Node() { } Node(int i, bool il, char lt, int p, int lc, int rc) : id(i), is_leaf(il), letter(lt), parent(p), lchild(lc), rchild(rc) { } }; multimap<int, Node> count_node; vector<Node> huffman_tree; map<char, vector<char>> letter_hcode; // hufman code for each letter }; 压缩函数Compress串起压缩的整个流程，包括统计字符频率、构建哈弗曼树、生成哈弗曼编码以及最后将原始文件转换成哈弗曼编码的二进制文件。 ...