霍夫曼编码是一种数据压缩算法，通常用于无损数据压缩。 这个算法是在麻省理工学院读理学博士(Doctor of Science )时发明的。 这个大人物于1952年发表了相关的论文amethodfortheconstructionofminimum-redundancy codes。 感兴趣的人请看一下。
最近，我们完成了银行客户安全管理系统的团队项目，该项目提供文件压缩/解压缩、加密/解密、加密和在压缩文件中搜索以及基于数据库文件的排序功能。 我实现的部分是霍夫曼编码的压缩(Compression )、解压缩(expression )算法、搜索(search )算法。 在这里分享一下自己的学习心得吧。 水平。
在提出变长编码和前缀编码霍夫曼编码之前，让我们先了解什么是变长编码和前缀编码。
如果一个字符比其他字符频繁出现，则可以使用算法以更少的位数（bit）表示相同的一段文本使该字符为3358www.Sina.com/。 例如，有些字符只能用一个二进制数(0或1 )表示，有些字符可以用两个二进制数)表示) 01或10 )。
假设您有一个字符串“aaabbc”，其中出现频率依次为3、2和1，即a、b和c。 根据频率对这4个字符首先随机定义4种代码。 以下所示。
字符代码a0b10c010经过编码后，此字符串可以表示为0001010010(0|0|10|10|010 ) )，看起来像文本被压缩了一样。 俊秀的鸡翅解码它的时候，会变得模糊。 以下所示。
0|0|0|10|10
aaabbc
0|0|0|10|10|0|10
aaabbab
为什么会出现歧义呢？ 由于此代码不满足可变长度编码（variable-length encoding）(prefix rule )，即前缀编码原则，因此根据上表，字符a的代码0是字符c的代码的前缀，因此解码如果遇到010代码，它可能被解码为字符ab(0|10 )或c (010 )。
霍夫曼编码霍夫曼编码(Huffman-Coding )是一种同时满足变长编码和前缀编码原则的算法。 可以通过连接具有不同权重的不同节点来构建霍夫曼树(最优二叉树)，权重最小的节点远离根节点，权重最大的节点接近根节点。 权重是根据字符在文本中出现的频率确定的。
算法步骤的哈夫曼树结构采用自下而上的方法。
初始化所有叶节点。 每个叶节点表示一个字符，其权重表示每个字符在文本中出现的频率。 每个选择权值最低的两个节点构成新节点，新节点的权重等于左右两个子树的权重之和。 将该新节点与其他叶节点进行比较，选择权重最小的两个节点，包括该新节点但不包括其子节点。 构建新节点。 重复步骤3直到获得完整的哈夫曼树。
假设字符“a”、“b”、“c”、“d”和“e”在文本中以6、9、7、3和5的顺序出现
初始化所有叶节点。
选择具有最小权重的两个节点以生成新节点。 其中，最小权重分别为3和5，因此将生成权重为8的新节点。
然后继续选择最小的两个节点。 3和5已经生成了新节点，所以不需要将3和5与其他节点进行比较。 比较8、6、9和7可以看出，权重为1到3的新节点将被生成，因为6和7最小：
比较剩下的节点8、13、9，由于8和9最小，生成权重为17的新节点：
最后以13和17为权重生成30个新节点，构成完整的霍夫曼树。
根据霍夫曼代码“左0右1”的规则，路径和字符如下：
通过生成的霍夫曼树，可以通过根节点到叶节点的路径获得每个字符的霍夫曼编码。
字符代码a00b11c01d100e101，因此原始字符串能够基于该霍夫曼编码字典生成一一对应的代码，并获得压缩的代码。
代码执行的完整项目代码可以看到我的github 其中文件一个字符的编码不能是另一个字符编码的前缀和project_dev1.c分别是霍夫曼编码的压缩和解压缩算法。
运行环境：
Linux系统，C90语言规格。
命令行指令：
make :执行makefile中所有源代码的编译说明。
生成清除：清除所有已编译的文件。
生成清除：清除在项目运行期间生成的所有中间文件，例如压缩或加密的文件。
./main.out :运行主程序
指定的数据库文件： Customer.txt，数据库文件的内容如下：
执行步骤：
在命令行中键入project_dev2.c编译所有源代码。 命令行
输入./main.out运行主程序。在用户界面选择"1. I want to compress the file"根据提示选择"1. I Efficient Compression"，由于选项二是行程长度压缩算法（Run Length Encoding），相对而言没有哈夫曼编码压缩效率高（尤其在应对重复字符时）。接着输入你要解压的文件，这里可以压缩示例文件"Customer.txt"。或者用户自己创建文件进行压缩。
解压时终端会输出根据哈夫曼树生成的哈夫曼编码以及压缩前后的二进制数，如下所示：
运行完后，你可以在文件夹目录下看到两个导出的文件，其中"Huffman_Codes.txt"是压缩后的哈夫曼编码，"HFT_Model"是哈夫曼树模型，这个模型在解压缩的时候用得上。
回到用户界面，选择"3. I want to decompress the file"，然后输入你要解压缩的文件名"Huffman_Codes.txt"，如下所示：
该程序会将解压后的文件内容输入到终端上：
并且导出解压缩后的文件"HFT_Decompression.txt"到目录中：
回到用户界面，你可以使用其他功能或者直接输入-1退出程序。然后依次输入make clean 和 make cleanf清楚编译文件和程序运行中产生的中间文件"Huffman_Codes.txt",“HFT_Model"和"HFT_Decompression.txt”。