如何使用Python實作霍夫曼編碼演算法?
摘要:
霍夫曼編碼是一種經典的資料壓縮演算法,它透過根據字元出現的頻率來產生唯一的編碼,從而實現資料的高效壓縮儲存。本文將介紹如何使用Python來實作霍夫曼編碼演算法,並提供具體的程式碼範例。
import heapq from collections import defaultdict class Node: def __init__(self, frequency, value=None): self.frequency = frequency self.value = value self.left_child = None self.right_child = None def __lt__(self, other): return self.frequency < other.frequency def build_huffman_tree(freq_dict): priority_queue = [] for char, freq in freq_dict.items(): heapq.heappush(priority_queue, Node(freq, char)) while len(priority_queue) > 1: left_child = heapq.heappop(priority_queue) right_child = heapq.heappop(priority_queue) new_node = Node(left_child.frequency + right_child.frequency) new_node.left_child = left_child new_node.right_child = right_child heapq.heappush(priority_queue, new_node) return heapq.heappop(priority_queue)產生霍夫曼編碼表
def generate_huffman_codes(huffman_tree): code_dict = {} def traverse(node, current_code=''): if node.value: code_dict[node.value] = current_code else: traverse(node.left_child, current_code + '0') traverse(node.right_child, current_code + '1') traverse(huffman_tree) return code_dict壓縮和解壓縮資料
def compress_data(data, code_dict): compressed_data = '' for char in data: compressed_data += code_dict[char] return compressed_data def decompress_data(compressed_data, huffman_tree): decompressed_data = '' current_node = huffman_tree for bit in compressed_data: if bit == '0': current_node = current_node.left_child else: current_node = current_node.right_child if current_node.value: decompressed_data += current_node.value current_node = huffman_tree return decompressed_data
總結:
本文介紹如何使用Python實作霍夫曼編碼演算法。主要的步驟包括建立霍夫曼樹、產生霍夫曼編碼表以及壓縮和解壓資料。希望透過本文的介紹和程式碼範例可以幫助讀者更好地理解和應用霍夫曼編碼演算法。以上是如何使用Python實作霍夫曼編碼演算法?的詳細內容。更多資訊請關注PHP中文網其他相關文章!