哈夫曼编码实现文件压缩解压

哈夫曼编码是一种无损数据压缩算法，可以用于文件压缩和解压缩。下面我将介绍如何使用Python实现哈夫曼编码的文件压缩和解压缩。

1. 哈夫曼编码实现文件压缩

首先，我们需要构建哈夫曼编码树。可以使用优先队列来实现。具体步骤如下：

- 遍历文件，统计每个字符出现的频率。
- 将每个字符和它的频率作为叶子节点插入到优先队列中。
- 从优先队列中取出两个频率最小的节点，将它们作为左右子节点构建一个新节点，并将新节点插入到优先队列中。
- 重复上述步骤，直到队列中只剩下一个节点，这个节点就是哈夫曼编码树的根节点。

接着，我们可以使用深度优先遍历来生成每个字符的哈夫曼编码。具体步骤如下：

- 从根节点开始，如果当前节点是叶子节点，则输出它的字符和哈夫曼编码。
- 如果当前节点有左子节点，则在哈夫曼编码的末尾添加0，并进入左子节点。
- 如果当前节点有右子节点，则在哈夫曼编码的末尾添加1，并进入右子节点。

最后，我们可以使用生成的哈夫曼编码来压缩文件。具体步骤如下：

- 遍历文件，将每个字符替换为它的哈夫曼编码。
- 将所有哈夫曼编码连接起来，每8个位表示一个字节，将其写入压缩文件中。
- 将哈夫曼编码表写入压缩文件中。

下面是实现代码：

import heapq
import os

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):
    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, HuffmanNode(char, freq))
    
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        new_node = HuffmanNode(None, node1.freq + node2.freq)
        new_node.left = node1
        new_node.right = node2
        heapq.heappush(heap, new_node)
    
    return heap[0]

def generate_huffman_codes(node, code, code_dict):
    if node.char is not None:
        code_dict[node.char] = code
        return
    
    generate_huffman_codes(node.left, code + '0', code_dict)
    generate_huffman_codes(node.right, code + '1', code_dict)

def compress_file(input_file, output_file):
    # Step 1: Build frequency dictionary
    freq_dict = {}
    with open(input_file, 'rb') as f:
        byte = f.read(1)
        while byte:
            if byte in freq_dict:
                freq_dict[byte] += 1
            else:
                freq_dict[byte] = 1
            byte = f.read(1)
    
    # Step 2: Build huffman tree
    root = build_huffman_tree(freq_dict)
    
    # Step 3: Generate huffman codes
    code_dict = {}
    generate_huffman_codes(root, '', code_dict)
    
    # Step 4: Compress input file
    with open(input_file, 'rb') as f_in, open(output_file, 'wb') as f_out:
        # Write huffman code table
        for char, code in code_dict.items():
            f_out.write(bytes([len(code)]))
            f_out.write(bytes([char]))
            f_out.write(code.encode('utf-8'))
        
        # Write compressed data
        byte = f_in.read(1)
        bits = ''
        while byte:
            bits += code_dict[byte]
            while len(bits) >= 8:
                byte_out = int(bits[:8], 2)
                f_out.write(bytes([byte_out]))
                bits = bits[8:]
            byte = f_in.read(1)
        if len(bits) > 0:
            byte_out = int(bits + '0' * (8 - len(bits)), 2)
            f_out.write(bytes([byte_out]))

2. 哈夫曼编码实现文件解压缩

文件解压缩的过程与文件压缩的过程相反。具体步骤如下：

- 读取哈夫曼编码表，生成字符与哈夫曼编码的对应关系。
- 读取压缩文件，将每个字节转换为8位二进制数。
- 遍历二进制数，从哈夫曼编码表中查找对应的字符。
- 将解压后的字符写入解压文件中。

下面是实现代码：

def decompress_file(input_file, output_file):
    # Step 1: Read huffman code table
    code_dict = {}
    with open(input_file, 'rb') as f:
        byte = f.read(1)
        while byte:
            code_len = int.from_bytes(byte, byteorder='big')
            char = f.read(1)
            code = f.read(code_len).decode('utf-8')
            code_dict[code] = char
            byte = f.read(1)
    
    # Step 2: Decompress input file
    with open(input_file, 'rb') as f_in, open(output_file, 'wb') as f_out:
        # Skip huffman code table
        f_in.seek(sum([2 + len(code) for code in code_dict.keys()]))
        
        # Read compressed data
        byte = f_in.read(1)
        bits = ''
        while byte:
            bits += bin(int.from_bytes(byte, byteorder='big'))[2:].rjust(8, '0')
            byte = f_in.read(1)
        
        # Write decompressed data
        while len(bits) > 0:
            for code, char in code_dict.items():
                if bits.startswith(code):
                    f_out.write(char)
                    bits = bits[len(code):]
                    break

综上所述，我们可以使用以上代码实现哈夫曼编码的文件压缩和解压缩。