Huffman 編碼

Vibe Prompt

「幫我實作 Huffman 編碼：輸入字串 'hello world'，輸出每個字元的 Huffman 編碼與壓縮率。」

import heapq
from collections import 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 huffman_encoding(text):
    freq = Counter(text)
    heap = [HuffmanNode(c, f) for c, f in freq.items()]
    heapq.heapify(heap)
    
    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)
    
    codes = {}
    def build_code(node, prefix=""):
        if node.char:
            codes[node.char] = prefix
        else:
            build_code(node.left, prefix + "0")
            build_code(node.right, prefix + "1")
    build_code(heap[0])
    
    encoded = ''.join(codes[c] for c in text)
    original_bits = len(text) * 8
    compressed_bits = len(encoded)
    return codes, encoded, compressed_bits / original_bits

codes, encoded, ratio = huffman_encoding("hello world")
print(f"Huffman 編碼表: {codes}")
print(f"原始: 88 bits → 壓縮後: {len(encoded)} bits")
print(f"壓縮率: {ratio:.1%}")