当前位置：首页 > article >正文

【数据结构】5——哈夫曼树（Huffman Tree）

article 2024/9/20 23:28:30

数据结构5——哈夫曼树（Huffman Tree）

又称最优二叉树，是一种带权路径长度最短的二叉树。
基于贪心思想的最优二叉树，主要用于数据压缩和编码。

文章目录

数据结构5——哈夫曼树（Huffman Tree）
前言
一、构造哈夫曼树
- 贪心算法
- 代码
二、应用
- - 1. 数据压缩
  - 2. 哈夫曼编码
  - 3. 多媒体压缩
  - 4. 网络路由
  - 5. 编译器优化
  - 6. 其他应用
- 2.代码
- - 文件编码解码
  - - 1
    - 中文内容

前言

定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree）。
性质：
哈夫曼树是带权路径长度最短的树。
权值较大的结点离根较近。
哈夫曼树的总结点数是2n-1（n是叶子节点数）。
哈夫曼树是一种前缀编码，即任一个字符的编码都不是另一个字符编码的前缀。

树的路径长度：从根节点到每个节点的路径长度之和
完全二叉树是路径最短的二叉树
权：给节点的含义赋值实际问题中多叫频率
带权路径长度：到某个节点的路径长度*节点的权

判断树：描述分类过程的二叉树

构建最优前缀码来压缩数据，使得编码长度最小。哈夫曼树广泛应用于文件压缩、传输中的哈夫曼编码算法。
任意字符的编码都不是另一个字符的编码前缀

一、构造哈夫曼树

没有度为1的节点
n个节点，n-1个合并节点

贪心算法

找权值小的的叶子节点

将给定的N个权值{w1, w2, …, wn}看成是有N棵树的森林（每棵树仅有一个结点）。
在森林中选出两个根结点的权值最小的树作为左右子树合并为一棵新树，且新树的根结点权值为其左右子树根结点权值之和。
将选中的两棵树从森林中删除，并把新树加入森林。
重复步骤2和3，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
生成哈夫曼编码：通过遍历哈夫曼树，左分支编码为0，右分支编码为1，为每个字符生成唯一的前缀码。

步骤详解
输入：一个字符及其频率的列表。
输出：一个哈夫曼树的根节点。

字符集和他们的权值 {‘a’: 5, ‘b’: 9, ‘c’: 12, ‘d’: 13, ‘e’: 16, ‘f’: 45}

初始时排序：[(5, ‘a’), (9, ‘b’), (12, ‘c’), (13, ‘d’), (16, ‘e’), (45, ‘f’)]
取出 (5, ‘a’) 和 (9, ‘b’)，合并成一个新节点 (5+9=14)。
插入后队列变为：[(12, ‘c’), (13, ‘d’), (14, 合并节点), (16, ‘e’), (45, ‘f’)]
取出 (12, ‘c’) 和 (13, ‘d’)，合并成一个新节点 (12+13=25)。
插入后变为：[(14, 合并节点), (16, ‘e’), (25, 合并节点), (45, ‘f’)]
取出 (14, 合并节点) 和 (16, ‘e’)，合并成一个新节点 (14+16=30)。
插入后变为：[(25, 合并节点), (30, 合并节点), (45, ‘f’)]
取出 (25, 合并节点) 和 (30, 合并节点)，合并成一个新节点 (25+30=55)。
插入后堆变为：[(45, ‘f’), (55, 合并节点)]
取出 (45, ‘f’) 和 (55, 合并节点)，合并成一个新节点 (45+55=100)。
最小堆中只剩一个节点：[(100, 合并节点)]。

                                        (100)  
									   /     \  
									f(45)    (55)  
								          /       \  
								        (25)      (30) 
								       /   \      /  \  
							   	    c(12) d(13) (14)  e(16) 
							   	                /  \  
								              a(5) b (9) 
哈夫曼编码:
a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

ace ——1100100111，知道直观编码也能倒推出ace
`低频字符的编码长`

代码

import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char  # 节点代表的字符
        self.freq = freq  # 字符出现的频率
        self.left = None  # 指向左子树
        self.right = None  # 指向右子树

    # 定义比较操作，以便 heapq 可以比较节点
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(char_freq):
    # 创建一个优先队列，并将其转换为堆结构
    heap = [HuffmanNode(char, freq) for char, freq in char_freq.items()]
    heapq.heapify(heap)

    # 当堆中有多于一个节点时，进行合并
    while len(heap) > 1:
        node1 = heapq.heappop(heap)  # 弹出频率最小的节点
        node2 = heapq.heappop(heap)  # 弹出第二小的节点

        merged = HuffmanNode(None, node1.freq + node2.freq)  # 创建一个新节点，其频率为两个节点之和
        merged.left = node1  # 左子树为弹出的第一个节点
        merged.right = node2  # 右子树为弹出的第二个节点

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

    return heap[0]  # 返回堆中仅剩的节点，即哈夫曼树的根节点

def print_huffman_tree(node, prefix="", codebook=defaultdict(str)):
    if node is not None:
        if node.char is not None:  # 如果节点有字符（不是内部节点），则记录编码
            codebook[node.char] = prefix
        print(f"{node.char if node.char else '内部节点'}: {node.freq} {prefix}")
        print_huffman_tree(node.left, prefix + "0", codebook)  # 递归左子树，编码增加"0"
        print_huffman_tree(node.right, prefix + "1", codebook)  # 递归右子树，编码增加"1"

    return codebook

# 示例使用
char_freq = {
    'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45
}

root = build_huffman_tree(char_freq)
codebook = print_huffman_tree(root)

# 打印编码
print("Huffman Codes:")
for char, code in codebook.items():
    print(f"{char}: {code}")

二、应用

1. 数据压缩

哈夫曼树最典型的应用是数据压缩，尤其是文本、音频和视频数据的压缩。在数据压缩过程中，哈夫曼树根据字符（或数据单元）出现的频率来构建，频率高的字符被赋予较短的编码，而频率低的字符则被赋予较长的编码。这种编码方式可以显著减少数据的存储空间并降低传输带宽的需求。例如，在文本压缩中，常见字符如’e’、‘t’等可能使用较短的编码，而不常见的字符如’z’、'q’等则使用较长的编码。

2. 哈夫曼编码

哈夫曼编码是基于哈夫曼树的一种前缀编码方式。前缀编码是指没有一个编码是另一个编码的前缀，这种特性确保了编码的唯一性和解码的无歧义性。在哈夫曼编码中，从根节点到叶子节点的路径（左子节点标记为0，右子节点标记为1）形成了对应字符的编码。由于高频字符的路径较短，低频字符的路径较长，因此整体编码的平均长度较短，达到了压缩数据的目的。

3. 多媒体压缩

除了文本数据外，哈夫曼树还广泛应用于音频和视频数据的压缩。在音频和视频编码中，大量的数据是重复的或高度可预测的。通过利用哈夫曼树对这些数据进行编码，可以有效地减少数据的冗余，降低存储和传输的成本。

4. 网络路由

在网络通信中，哈夫曼树也被用于路由决策。通过将网络中的数据包传输路径视为树形结构，并利用哈夫曼树的特性来优化路由选择，可以降低网络拥塞和延迟，提高数据传输的效率。

5. 编译器优化

在编译器设计中，哈夫曼树也被用于表示源代码的语法树。通过构建最优的哈夫曼树来表示语法结构，编译器可以更高效地进行代码分析和优化，从而提高程序的执行效率。

6. 其他应用

此外，哈夫曼树还被应用于通信中的信道编码、文件压缩、图像压缩等多个领域。在这些应用中，哈夫曼树的构建和编码方式都发挥着重要的作用，使得数据能够以高效、节省空间的方式进行存储和传输。

2.代码

文件编码解码

创建一个名为 huffman.txt 的文本文件，填写要编码的内容。内容写英文，中文试了一下表现不太好，代码放在后面

1

import heapq
from collections import defaultdict, Counter

# 哈夫曼树节点类
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(freq_dict):
    priority_queue = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
    heapq.heapify(priority_queue)

    while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(priority_queue, merged)

    return priority_queue[0]

# 获取哈夫曼编码
def get_codes(node, prefix='', code_dict=defaultdict()):
    if node is not None:
        if node.char is not None:
            code_dict[node.char] = prefix
        get_codes(node.left, prefix + '0', code_dict)
        get_codes(node.right, prefix + '1', code_dict)
    return code_dict

# 将文本编码为哈夫曼编码
def encode_text(text, code_dict):
    return ''.join(code_dict[char] for char in text)

# 将哈夫曼编码解码为文本
def decode_text(encoded_text, root):
    decoded_chars = []
    node = root
    for bit in encoded_text:
        if bit == '0':
            node = node.left
        else:
            node = node.right

        if node.char is not None:
            decoded_chars.append(node.char)
            node = root

    return ''.join(decoded_chars)

# 主程序
if __name__ == '__main__':
    # 输入文件和输出文件
    input_file_path = 'input.txt'
    encoded_file_path = 'encoded.bin'
    decoded_file_path = 'decoded.txt'

    # 读取文件内容
    with open(input_file_path, 'r') as file:
        text = file.read()

    # 构建哈夫曼树并获取编码
    freq_dict = Counter(text)
    huffman_tree = build_huffman_tree(freq_dict)
    codes = get_codes(huffman_tree)

    # 打印编码
    print("Huffman Codes:")
    for char, code in codes.items():
        print(f'{char}: {code}')

    # 编码文本
    encoded_text = encode_text(text, codes)

    # 保存编码数据到文件
    with open(encoded_file_path, 'w') as file:
        file.write(encoded_text)

    # 读取编码数据并解码
    with open(encoded_file_path, 'r') as file:
        encoded_text = file.read()

    # 解码文本
    decoded_text = decode_text(encoded_text, huffman_tree)

    # 保存解码后的文本
    with open(decoded_file_path, 'w') as file:
        file.write(decoded_text)

    print(f"\nEncoded text has been written to {encoded_file_path}")
    print(f"Decoded text has been written to {decoded_file_path}")

中文内容


import heapq
from collections import defaultdict, Counter

# 哈夫曼树节点类
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(freq_dict):
    priority_queue = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
    heapq.heapify(priority_queue)

    while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(priority_queue, merged)

    return priority_queue[0]

# 获取哈夫曼编码
def get_codes(node, prefix='', code_dict=defaultdict()):
    if node is not None:
        if node.char is not None:
            code_dict[node.char] = prefix
        get_codes(node.left, prefix + '0', code_dict)
        get_codes(node.right, prefix + '1', code_dict)
    return code_dict

# 将文本编码为哈夫曼编码
def encode_text(text, code_dict):
    return ''.join(code_dict[char] for char in text)

# 将哈夫曼编码解码为文本
def decode_text(encoded_text, root):
    decoded_chars = []
    node = root
    for bit in encoded_text:
        if bit == '0':
            node = node.left
        else:
            node = node.right

        if node.char is not None:
            decoded_chars.append(node.char)
            node = root

    return ''.join(decoded_chars)

# 主程序
if __name__ == '__main__':
    # 输入文件和输出文件
    input_file_path = 'input.txt'
    encoded_file_path = 'encoded.bin'
    decoded_file_path = 'decoded.txt'

    # 读取文件内容（UTF-8 编码）
    with open(input_file_path, 'r', encoding='utf-8') as file:
        text = file.read()

    # 构建哈夫曼树并获取编码
    freq_dict = Counter(text)
    huffman_tree = build_huffman_tree(freq_dict)
    codes = get_codes(huffman_tree)

    # 打印编码
    print("Huffman Codes:")
    for char, code in codes.items():
        print(f'{char}: {code}')

    # 编码文本
    encoded_text = encode_text(text, codes)

    # 保存编码数据到文件（以二进制模式写入）
    with open(encoded_file_path, 'wb') as file:
        # 将编码数据转换为字节流
        encoded_bytes = int(encoded_text, 2).to_bytes((len(encoded_text) + 7) // 8, byteorder='big')
        file.write(encoded_bytes)

    # 读取编码数据并解码
    with open(encoded_file_path, 'rb') as file:
        # 读取字节流并转换为二进制字符串
        encoded_bytes = file.read()
        encoded_text = ''.join(f'{byte:08b}' for byte in encoded_bytes)

    # 解码文本
    decoded_text = decode_text(encoded_text, huffman_tree)

    # 保存解码后的文本
    with open(decoded_file_path, 'w', encoding='utf-8') as file:
        file.write(decoded_text)

    print(f"\nEncoded text has been written to {encoded_file_path}")
    print(f"Decoded text has been written to {decoded_file_path}")