【贪心算法经典应用】哈夫曼编码原理与算法详解 python

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
备注说明：方便大家阅读，统一使用python，带必要注释，公众号数据分析螺丝钉一起打怪升级

哈夫曼编码是一种广泛使用的数据压缩方法，特别是在无损数据压缩领域。本文将详细介绍哈夫曼编码的原理、算法过程，以及如何使用贪心算法实现这一过程。通过这种方式，我们能有效地理解贪心算法在实际问题解决中的应用。

背景和理论基础

哈夫曼编码由David A. Huffman于1952年提出，它是一种利用字符频率来构造最优前缀码的算法。其核心思想是创建一个低成本的编码，用较短的代码表示频率高的字符，用较长的代码表示频率低的字符，从而实现数据的有效压缩。

前缀码：任何字符的编码都不是其他字符编码的前缀，这消除了解码时的歧义性。
贪心策略：在构造编码树时，总是选择两个最小频率的字符进行合并，这保证了最终的编码总成本（即编码的长度和频率的乘积）最小。

哈夫曼编码原理

考虑字符串 “aabacabad”，我们如何构建哈夫曼编码呢？

步骤 1: 统计频率

首先，计算字符串中每个字符的出现频率：

a: 5
b: 2
c: 1
d: 1

步骤 2: 初始化优先队列

对每个字符创建一个节点，并根据其频率放入优先队列（最小堆）中。每个节点是一个树的叶子节点。

初始队列（按频率排序）:

节点     频率
---------------
[c:1]
[d:1]
[b:2]
[a:5]

步骤 3: 构建哈夫曼树

哈夫曼编码的目的是将常用字符编码为较短的码字，而不常用字符编码为较长的码字。字符的频率直接影响其在哈夫曼树中的位置：

高频字符被放在树的较高层（更靠近根节点），这样从根节点到这些字符的路径较短，因此产生的编码也较短。
低频字符被放在树的较低层（更远离根节点），这样路径较长，编码也较长。

这种策略使得编码的总长度（即编码长度乘以频率的总和）最小化，从而实现有效的压缩。
使用以下算法构建哈夫曼树，直到队列中只剩一个节点：

合并两个最小频率的节点：从队列中取出两个最小的节点，合并为一个新节点，其频率是两个节点频率的和，这两个节点成为新节点的子节点。
将新节点重新加入队列。

第一次合并（合并 ‘c’ 和 ‘d’）

新节点: [cd]，频率: 2
结构:
    [cd:2]
   /     \
[c:1]   [d:1]

队列更新为：

[b:2]
[cd:2]
[a:5]

第二次合并（合并 ‘b’ 和 ‘cd’）

新节点: [bcd]，频率: 4
结构:
    [bcd:4]
   /      \
[b:2]    [cd:2]
        /    \
     [c:1]  [d:1]

队列更新为：

[bcd:4]
[a:5]

第三次合并（合并 ‘bcd’ 和 ‘a’）

新节点: [abcda]，频率: 9 (这是根节点)
结构:
      [abcda:9]
     /        \
  [a:5]      [bcd:4]
            /      \
         [b:2]    [cd:2]
                 /    \
              [c:1]  [d:1]

队列清空，树构建完成。

步骤 4: 生成编码

在哈夫曼编码过程中，每个字符的编码由其在哈夫曼树中的位置决定，具体来说，是由从根节点到该字符对应叶子节点的路径决定。路径中左转表示“0”，右转表示“1”。

‘a’ 的路径直接左转，因此编码为 “0”。
‘b’ 的路径是向右转，然后左转，因此编码为 “10”。
‘c’ 的路径是向右转，再向右转，然后左转，因此编码为 “110”。
‘d’ 的路径是向右转，再向右转，然后右转，因此编码为 “111”。

最终编码：

a -> 1
b -> 01
c -> 001
d -> 000

效率分析

首先，基于字符 “aabacabad”，我们确定字符频率及其对应的哈夫曼编码和固定长度编码：

字符	频率	哈夫曼编码	哈夫曼位数	固定编码	固定位数
a	5	1	1	00	2
b	2	01	2	01	2
c	1	001	3	10	2
d	1	000	3	11	2

计算总位数需求

下面，我们计算每种编码策略的总位数需求：

哈夫曼编码总位数

对于 ‘a’：5个字符 ✖️ 1位/字符 = 5位
对于 ‘b’：2个字符 ✖️2位/字符 = 4位
对于 ‘c’：1个字符 ✖️3位/字符 = 3位
对于 ‘d’：1个字符 ✖️3位/字符 = 3位

哈夫曼编码总位数 = 5 + 4 + 3 + 3 = 15位

固定长度编码总位数

每个字符使用2位编码（固定）
对于 ‘a’：5个字符 ✖️ 2位/字符 = 10位
对于 ‘b’：2个字符 ✖️2位/字符 = 4位
对于 ‘c’：1个字符 ✖️2位/字符 = 2位
对于 ‘d’：1个字符 ✖️ 2位/字符 = 2位

固定编码总位数 = 10 + 4 + 2 + 2 = 18位

压缩效率比较表

最后，我们整理以上计算结果，形成一个压缩效率比较表：

编码类型	总位数	压缩效率
哈夫曼编码	15位	高
固定长度编码	18位	低

结论

从表中可见，哈夫曼编码通过对字符使用变长编码，使得频率高的字符使用更短的编码，有效减少了总编码长度。相比之下，固定长度编码不区分字符频率，导致其总位数使用较多，压缩效率较低。哈夫曼编码尤其在处理非均匀分布的大数据集时，能显著优化数据存储和传输效率。

通过这种方式，哈夫曼编码不仅提供了理论上的最优压缩方案，而且在实际应用中广泛用于多种数据压缩场景，包括网络数据传输和文件存储。

哈夫曼编码Python算法

这里使用贪心算法来构建哈夫曼树，它是哈夫曼编码核心过程中的一个主要部分。贪心算法在此过程中的应用体现在选择过程中 —— 每次从所有可用的节点中选择两个频率最低的节点来合并。这种方法是基于局部最优选择，目的是构建全局最优的哈夫曼树。
贪心策略

在构建哈夫曼树的过程中，我们按以下贪心策略操作：

选择最小元素：每次从节点集合（初始时为优先队列）中选取两个频率最小的节点。这是一种贪心选择，因为合并这两个节点可以保证后续构建的树的总权重增加最小。
合并操作：将这两个最小节点合并为一个新的节点，其频率是两个子节点频率之和。这个新节点随后会被重新加入到节点集合中参与后续的合并操作。
重复过程：重复上述过程，直到节点集合中只剩一个节点，这个节点就是哈夫曼树的根节点，代表了构建完成的哈夫曼树。

代码示例

import heapq
from collections import Counter, defaultdict

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char   # 存储字符
        self.freq = freq   # 存储频率
        self.left = None   # 左子树
        self.right = None  # 右子树

    # 定义比较操作，以支持优先队列中的节点排序
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    """构建哈夫曼树并返回根节点"""
    # 统计字符频率
    frequency = Counter(text)
    # 创建优先队列（最小堆）
    heap = [HuffmanNode(char, freq) for char, freq in frequency.items()]
    heapq.heapify(heap)

    # 当堆中节点数大于1时，执行合并操作
    while len(heap) > 1:
        left = heapq.heappop(heap)  # 取出频率最小的节点
        right = heapq.heappop(heap) # 取出频率第二小的节点

        merged = HuffmanNode(None, left.freq + right.freq)  # 创建新的内部节点
        merged.left = left
        merged.right = right

        heapq.heappush(heap, merged)  # 将新节点添加回堆中

    return heap[0]  # 堆中最后剩下的节点为根节点

def huffman_codes(node, prefix="", code={}):
    """生成哈夫曼编码表"""
    if node is not None:
        if node.char is not None:
            code[node.char] = prefix
        huffman_codes(node.left, prefix + "0", code)
        huffman_codes(node.right, prefix + "1", code)
    return code

def encode(text, code):
    """使用哈夫曼编码表来编码文本"""
    return ''.join(code[char] for char in text)

def main():
    text = "aabacabad"  # 示例文本
    root = build_huffman_tree(text)  # 构建哈夫曼树
    code = huffman_codes(root)  # 生成哈夫曼编码表

    encoded_text = encode(text, code)  # 编码文本
    print("原始文本:", text)
    print("字符频率:", Counter(text))
    print("哈夫曼编码表:", code)
    print("编码后的文本:", encoded_text)

if __name__ == "__main__":
    main()