100种算法【Python版】第52篇——无损压缩之霍夫曼编码
本文目录
- 1 算法步骤
- 2 算法示例
- 3 算法应用
-
- 3.1 压缩字符串
- 3.2 压缩RGB图像
霍夫曼编码是一种无损数据压缩算法，用于根据字符出现的频率为每个字符分配变长编码。其基本思路是使用频率较高的字符分配较短的编码，而频率较低的字符分配较长的编码，从而实现数据压缩。
1 算法步骤
- 统计字符频率：
- 计算输入文本中每个字符的出现次数，构建字符频率表。
- 构建霍夫曼树：
- 将每个字符及其频率视为一棵树的叶子节点，插入优先队列（最小堆）。
- 反复从堆中取出频率最小的两个节点，合并成一个新节点（其频率为两个节点频率之和），并将新节点插入堆中。
- 直到堆中只剩下一个节点，该节点即为霍夫曼树的根节点。
- 生成霍夫曼编码：
- 从霍夫曼树的根节点开始，递归遍历树：
- 左子树编码为 0，右子树编码为 1，直到到达叶子节点为止，记录每个字符的编码。
- 从霍夫曼树的根节点开始，递归遍历树：
- 编码和解码：
- 使用生成的编码表对输入文本进行编码。
- 可以根据编码表将编码文本解码回原始文本。
2 算法示例
假设有以下文本：</