哈夫曼编码

‌哈夫曼编码是一种数据压缩算法，由‌ (David A. Huffman) 于 1952 年提出，它是一种可变长度编码方式，根据字符出现的概率来决定编码长度，使得出现概率大的字符编码长度短，而出现概率小的字符编码长度长，从而减少整体编码的长度。这种编码方式特别适用于文本数据的压缩，因为它能够有效地减少数据存储空间或传输所需的带宽。

哈夫曼编码的基本原理

1. 构建哈夫曼树： 首先，根据文本中每个字符出现的频率或概率，构建一棵哈夫曼树。这棵树的特点是频率高的字符对应的节点离根节点更近，而频率低的字符离根节点更远。

2. 生成编码： 在哈夫曼树中，从根节点到每个字符节点的路径就是该字符的编码。通常，左子树的路径用 0 表示，右子树的路径用 1 表示。

# 哈夫曼编码的具体方法：

1. 先按字符出现的概率从小到大排序；

2. 取出频率最小的两个字符，构建一棵二叉树，并将其根节点的频率设置为两个字符的频率之和；

3. 将原序列中的两个字符频率删除，并将新生成的(频率)节点插入到序列中，得到新的字符序列；

4. 重复步骤1、2、3,直到得到一棵包含所有字符的二叉树，对于每条从根节点到叶子节点的路径，用 0 表示向左走，用 1 表示向右走，就能得到对应字符的哈夫曼编码。

### 夫曼编码的方法并不唯一

哈夫曼编码的特点

• 高效压缩： 哈夫曼编码能够显著减少数据的大小，特别适用于文本数据的压缩。
• 无损压缩： 由于哈夫曼编码是一种可逆的编码方式，解码后的数据与原始数据完全相同，无信息损失。
• 自适应调整： 哈夫曼编码可以动态地适应数据中字符频率的变化，因此在处理动态变化的数据流时非常有用。