import heapq
from collections import Counter, defaultdict

class HuffmanNode:
    """ハフマン木のノード"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char    # リーフの場合のシンボル
        self.freq = freq    # 頻度（確率）
        self.left = left    # 左の子（0に対応）
        self.right = right  # 右の子（1に対応）

    def __lt__(self, other):
        # heapqでの比較用
        return self.freq < other.freq

    def is_leaf(self):
        return self.left is None and self.right is None


def build_huffman_tree(freq_dict):
    """頻度辞書からハフマン木を構築する"""
    # 各シンボルをリーフノードとしてヒープに追加
    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, HuffmanNode(char=char, freq=freq))

    # ノードが1つになるまで統合を繰り返す
    while len(heap) > 1:
        # 最小の2ノードを取り出す
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # 新しい親ノードを作成
        parent = HuffmanNode(
            freq=left.freq + right.freq,
            left=left,
            right=right
        )
        heapq.heappush(heap, parent)

    return heap[0]  # 根ノードを返す


def build_codebook(root):
    """ハフマン木から符号表を構築する"""
    codebook = {}

    def _traverse(node, code):
        if node.is_leaf():
            codebook[node.char] = code if code else '0'
            return
        if node.left:
            _traverse(node.left, code + '0')
        if node.right:
            _traverse(node.right, code + '1')

    _traverse(root, '')
    return codebook


def huffman_encode(text, codebook):
    """テキストをハフマン符号で符号化する"""
    return ''.join(codebook[ch] for ch in text)


def huffman_decode(encoded, root):
    """ハフマン符号を復号する"""
    decoded = []
    node = root
    for bit in encoded:
        if bit == '0':
            node = node.left
        else:
            node = node.right

        if node.is_leaf():
            decoded.append(node.char)
            node = root  # 根に戻る

    return ''.join(decoded)


# テスト
text = "ABRACADABRA"
print(f"元のテキスト: {text}")
print(f"テキスト長: {len(text)} 文字")

# 頻度を計算
freq = Counter(text)
print(f"頻度: {dict(freq)}")

# ハフマン木を構築
tree = build_huffman_tree(freq)

# 符号表を構築
codebook = build_codebook(tree)
print(f"符号表: {codebook}")

# 符号化
encoded = huffman_encode(text, codebook)
print(f"符号化結果: {encoded}")
print(f"符号化後のビット数: {len(encoded)}")

# 復号
decoded = huffman_decode(encoded, tree)
print(f"復号結果: {decoded}")
print(f"正しく復号できたか: {text == decoded}")

# 圧縮率の計算
original_bits = len(text) * 8  # ASCII: 1文字8ビット
compressed_bits = len(encoded)
print(f"\n固定長(ASCII): {original_bits} bits")
print(f"ハフマン符号: {compressed_bits} bits")
print(f"圧縮率: {compressed_bits / original_bits:.2%}")

# エントロピーとの比較
import numpy as np
probs = np.array(list(freq.values())) / len(text)
H = -np.sum(probs * np.log2(probs))
avg_len = len(encoded) / len(text)
print(f"\nエントロピー H(X): {H:.4f} bits/symbol")
print(f"平均符号長: {avg_len:.4f} bits/symbol")
print(f"冗長度: {avg_len - H:.4f} bits/symbol")

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
import heapq

class HuffmanNode:
    """ハフマン木のノード"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq

    def is_leaf(self):
        return self.left is None and self.right is None

def build_huffman_tree(freq_dict):
    """ハフマン木を構築"""
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq_dict.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, parent)
    return heap[0]

def build_codebook(root):
    """符号表を構築"""
    codebook = {}
    def _traverse(node, code):
        if node.is_leaf():
            codebook[node.char] = code if code else '0'
            return
        if node.left:
            _traverse(node.left, code + '0')
        if node.right:
            _traverse(node.right, code + '1')
    _traverse(root, '')
    return codebook

def analyze_compression(text, label):
    """テキストのハフマン符号化を分析"""
    freq = Counter(text)
    n = len(text)
    probs = np.array([freq[c] / n for c in freq])

    # エントロピー
    H = -np.sum(probs * np.log2(probs))

    # ハフマン符号を構築
    tree = build_huffman_tree(freq)
    codebook = build_codebook(tree)

    # 平均符号長
    avg_len = sum(freq[c] * len(codebook[c]) for c in freq) / n

    # 固定長符号の符号長
    fixed_len = np.ceil(np.log2(len(freq)))

    return {
        'label': label,
        'n_chars': n,
        'n_unique': len(freq),
        'entropy': H,
        'avg_huffman': avg_len,
        'fixed_len': fixed_len,
        'compression_ratio': avg_len / 8,  # vs ASCII
        'redundancy': avg_len - H,
        'codebook': codebook
    }

# さまざまなテキストでテスト
texts = {
    'English-like': 'the quick brown fox jumps over the lazy dog ' * 20,
    'Repetitive': 'aaaaaabbbbccd' * 50,
    'Uniform': ''.join([chr(65 + i % 26) for i in range(500)]),
    'Binary': '0110100110010110' * 40,
    'Japanese-sim': 'あいうえおかきくけこさしすせそ' * 30,
}

results = []
for label, text in texts.items():
    result = analyze_compression(text, label)
    results.append(result)
    print(f"\n--- {label} ---")
    print(f"  文字数: {result['n_chars']}, 種類数: {result['n_unique']}")
    print(f"  エントロピー: {result['entropy']:.4f} bits/symbol")
    print(f"  ハフマン平均符号長: {result['avg_huffman']:.4f} bits/symbol")
    print(f"  冗長度: {result['redundancy']:.4f} bits/symbol")
    print(f"  圧縮率 (vs 8-bit): {result['compression_ratio']:.2%}")

# 可視化: エントロピーと平均符号長の比較
fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# 左: 各テキストのエントロピーと平均符号長
ax = axes[0]
labels = [r['label'] for r in results]
entropies = [r['entropy'] for r in results]
avg_lens = [r['avg_huffman'] for r in results]
fixed_lens = [r['fixed_len'] for r in results]

x = np.arange(len(labels))
width = 0.25
ax.bar(x - width, entropies, width, label='H(X) (entropy)', color='steelblue')
ax.bar(x, avg_lens, width, label='Huffman avg length', color='salmon')
ax.bar(x + width, fixed_lens, width, label='Fixed-length', color='lightgreen')
ax.set_xticks(x)
ax.set_xticklabels(labels, rotation=15, ha='right')
ax.set_ylabel('Bits per symbol', fontsize=12)
ax.set_title('Entropy vs Average codeword length', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3, axis='y')

# 右: 冗長度の比較
ax = axes[1]
redundancies = [r['redundancy'] for r in results]
colors = ['steelblue' if r < 0.5 else 'salmon' for r in redundancies]
ax.barh(labels, redundancies, color=colors, edgecolor='black', linewidth=0.5)
ax.set_xlabel('Redundancy (bits/symbol)', fontsize=12)
ax.set_title('Huffman code redundancy = L - H(X)', fontsize=13)
ax.grid(True, alpha=0.3, axis='x')

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
import heapq

class HuffmanNode:
    """ハフマン木のノード"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    def __lt__(self, other):
        return self.freq < other.freq
    def is_leaf(self):
        return self.left is None and self.right is None

def build_huffman_tree(freq_dict):
    """ハフマン木を構築"""
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq_dict.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, parent)
    return heap[0]

def compute_positions(node, x=0, y=0, dx=2.0, positions=None):
    """木の各ノードの描画位置を計算"""
    if positions is None:
        positions = {}
    pos_id = id(node)
    positions[pos_id] = (x, y, node)

    if node.left:
        compute_positions(node.left, x - dx, y - 1, dx / 2, positions)
    if node.right:
        compute_positions(node.right, x + dx, y - 1, dx / 2, positions)

    return positions

# テスト用のデータ
text = "ABRACADABRA"
freq = Counter(text)

# ハフマン木を構築
tree = build_huffman_tree(freq)

# 位置を計算
positions = compute_positions(tree, dx=3.0)

# 可視化
fig, ax = plt.subplots(figsize=(12, 8))

# エッジと0/1ラベルを描画
def draw_tree(node, x, y, dx, ax):
    if node.left:
        lx, ly = x - dx, y - 1
        ax.plot([x, lx], [y, ly], 'k-', linewidth=1.5)
        ax.text((x + lx) / 2 - 0.15, (y + ly) / 2 + 0.1, '0',
                fontsize=12, color='blue', fontweight='bold')
        draw_tree(node.left, lx, ly, dx / 2, ax)
    if node.right:
        rx, ry = x + dx, y - 1
        ax.plot([x, rx], [y, ry], 'k-', linewidth=1.5)
        ax.text((x + rx) / 2 + 0.15, (y + ry) / 2 + 0.1, '1',
                fontsize=12, color='red', fontweight='bold')
        draw_tree(node.right, rx, ry, dx / 2, ax)

draw_tree(tree, 0, 0, 3.0, ax)

# ノードを描画
for pos_id, (x, y, node) in positions.items():
    if node.is_leaf():
        circle = plt.Circle((x, y), 0.3, color='lightgreen',
                             ec='black', linewidth=1.5, zorder=5)
        ax.add_patch(circle)
        ax.text(x, y, f"{node.char}\n({node.freq})", ha='center', va='center',
                fontsize=10, fontweight='bold', zorder=6)
    else:
        circle = plt.Circle((x, y), 0.3, color='lightyellow',
                             ec='black', linewidth=1.5, zorder=5)
        ax.add_patch(circle)
        ax.text(x, y, f"{node.freq}", ha='center', va='center',
                fontsize=10, zorder=6)

ax.set_xlim(-5, 5)
ax.set_ylim(-5, 1)
ax.set_aspect('equal')
ax.set_title(f'Huffman Tree for "{text}"', fontsize=14)
ax.axis('off')
plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
from itertools import product
import heapq

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    def __lt__(self, other):
        return self.freq < other.freq
    def is_leaf(self):
        return self.left is None and self.right is None

def build_huffman_tree(freq_dict):
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq_dict.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, parent)
    return heap[0]

def build_codebook(root):
    codebook = {}
    def _traverse(node, code):
        if node.is_leaf():
            codebook[node.char] = code if code else '0'
            return
        if node.left:
            _traverse(node.left, code + '0')
        if node.right:
            _traverse(node.right, code + '1')
    _traverse(root, '')
    return codebook

# 情報源の定義
symbols = ['A', 'B', 'C']
probs = [0.7, 0.2, 0.1]
H = -sum(p * np.log2(p) for p in probs)

# ブロックサイズごとの平均符号長を計算
block_sizes = range(1, 7)
avg_lengths = []

for k in block_sizes:
    # k次拡大情報源の確率分布を計算
    block_freq = {}
    for block in product(range(len(symbols)), repeat=k):
        p_block = np.prod([probs[s] for s in block])
        block_name = ''.join([symbols[s] for s in block])
        block_freq[block_name] = p_block

    # ハフマン木を構築
    tree = build_huffman_tree(block_freq)
    codebook = build_codebook(tree)

    # 1シンボルあたりの平均符号長
    avg_len = sum(block_freq[b] * len(codebook[b]) for b in block_freq) / k
    avg_lengths.append(avg_len)
    print(f"ブロックサイズ k={k}: L/k = {avg_len:.4f} bits/symbol "
          f"(冗長度 = {avg_len - H:.4f})")

print(f"\nエントロピー H(X) = {H:.4f} bits/symbol")

# 可視化
fig, ax = plt.subplots(figsize=(10, 6))

ax.plot(list(block_sizes), avg_lengths, 'bo-', linewidth=2, markersize=8,
        label='Block Huffman L/k')
ax.axhline(H, color='red', linewidth=2, linestyle='--',
           label=f'H(X) = {H:.4f}')

# 理論上界
theory_upper = [H + 1/k for k in block_sizes]
ax.plot(list(block_sizes), theory_upper, 'g--', linewidth=1.5,
        label='H(X) + 1/k (upper bound)')

ax.fill_between(list(block_sizes), H, theory_upper,
                alpha=0.1, color='green')

ax.set_xlabel('Block size k', fontsize=12)
ax.set_ylabel('Average bits per symbol', fontsize=12)
ax.set_title('Block Huffman coding: convergence to entropy', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
ax.set_xticks(list(block_sizes))

plt.tight_layout()
plt.show()