Pythonにおけるハフマン符号化の実装方法

以下に、Pythonでのハフマン符号化の実装例をいくつか紹介します。

1. 文字列の頻度をカウントする関数の実装:

from collections import Counter
def count_frequency(text):
    frequency = Counter(text)
    return frequency

2. ハフマンツリーを構築する関数の実装:

import heapq
class HuffmanNode:
    def __init__(self, char, frequency):
        self.char = char
        self.frequency = frequency
        self.left = None
        self.right = None
    def __lt__(self, other):
        return self.frequency < other.frequency
def build_huffman_tree(frequency):
    heap = []
    for char, freq in frequency.items():
        heapq.heappush(heap, HuffmanNode(char, freq))
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged_node = HuffmanNode(None, node1.frequency + node2.frequency)
        merged_node.left = node1
        merged_node.right = node2
        heapq.heappush(heap, merged_node)
    return heapq.heappop(heap)

3. ハフマン符号を生成する関数の実装:

def generate_huffman_codes(root, current_code, codes):
    if root.char:
        codes[root.char] = current_code
        return
    generate_huffman_codes(root.left, current_code + "0", codes)
    generate_huffman_codes(root.right, current_code + "1", codes)
def huffman_encoding(text):
    frequency = count_frequency(text)
    huffman_tree = build_huffman_tree(frequency)
    codes = {}
    generate_huffman_codes(huffman_tree, "", codes)
    encoded_text = ""
    for char in text:
        encoded_text += codes[char]
    return encoded_text, huffman_tree
def huffman_decoding(encoded_text, huffman_tree):
    decoded_text = ""
    current_node = huffman_tree
    for bit in encoded_text:
        if bit == "0":
            current_node = current_node.left
        else:
            current_node = current_node.right
        if current_node.char:
            decoded_text += current_node.char
            current_node = huffman_tree
    return decoded_text

これらの関数を使用して、テキストをハフマン符号化および復号化することができます。例えば以下のように使用できます:

text = "Hello, world!"
encoded_text, huffman_tree = huffman_encoding(text)
decoded_text = huffman_decoding(encoded_text, huffman_tree)
print("元のテキスト:", text)
print("符号化されたテキスト:", encoded_text)
print("復号化されたテキスト:", decoded_text)

上記のコードは、ハフマン符号化の基本的な実装例です。必要に応じてカスタマイズや最適化を行うことができます。