import numpy as np

def verify_kraft_inequality(code_lengths):
    """
    验证Kraft不等式
    
    参数:
        code_lengths: 码字长度列表
    
    返回:
        Kraft和，以及是否满足不等式
    """
    kraft_sum = sum(2**(-l) for l in code_lengths)
    return kraft_sum, kraft_sum <= 1 + 1e-10

# 示例1：Huffman码（前缀码）
huffman_lengths = [1, 2, 3, 3]  # 例如概率[0.5, 0.25, 0.125, 0.125]
kraft_sum, valid = verify_kraft_inequality(huffman_lengths)
print("示例1：Huffman码")
print(f"  码长: {huffman_lengths}")
print(f"  Kraft和: {kraft_sum:.4f}")
print(f"  满足不等式? {valid}")
print()

# 示例2：定长码
fixed_lengths = [2, 2, 2, 2]  # 4个符号，每个2比特
kraft_sum, valid = verify_kraft_inequality(fixed_lengths)
print("示例2：定长码")
print(f"  码长: {fixed_lengths}")
print(f"  Kraft和: {kraft_sum:.4f}")
print(f"  满足不等式? {valid}")
print()

# 示例3：不满足Kraft不等式的情况
invalid_lengths = [1, 1, 1]  # 3个符号，每个1比特（不可能）
kraft_sum, valid = verify_kraft_inequality(invalid_lengths)
print("示例3：无效码")
print(f"  码长: {invalid_lengths}")
print(f"  Kraft和: {kraft_sum:.4f}")
print(f"  满足不等式? {valid}")

示例1：Huffman码
  码长: [1, 2, 3, 3]
  Kraft和: 1.0000
  满足不等式? True

示例2：定长码
  码长: [2, 2, 2, 2]
  Kraft和: 1.0000
  满足不等式? True

示例3：无效码
  码长: [1, 1, 1]
  Kraft和: 1.5000
  满足不等式? False

import numpy as np

def source_coding_theorem_demo():
    """
    演示信源编码定理
    """
    
    # 二元信源
    p = 0.8
    H = -p * np.log2(p) - (1-p) * np.log2(1-p)
    
    print("信源编码定理演示")
    print("=" * 60)
    print(f"信源: P(X=0)={p}, P(X=1)={1-p}")
    print(f"熵 H(X) = {H:.4f} bits/symbol")
    print()
    
    # 不同块长的压缩率
    print("不同编码方案的压缩率:")
    print("-" * 60)
    
    # 方案1：逐符号编码（定长）
    R_fixed = np.ceil(np.log2(2))  # 2个符号需要1比特
    print(f"逐符号定长编码: R = {R_fixed:.4f} bits/symbol")
    
    # 方案2：Huffman编码（逐符号）
    # 对于二元信源，Huffman就是逐符号
    R_huffman = 1.0
    print(f"逐符号Huffman编码: R = {R_huffman:.4f} bits/symbol")
    
    # 方案3：块Huffman编码（n=2）
    n = 2
    # 可能的双符号组合及其概率
    probs_n2 = [p**2, p*(1-p), (1-p)*p, (1-p)**2]
    probs_n2.sort(reverse=True)
    
    # Huffman码长（近似）
    # 最高概率符号：1比特
    # 次高：2比特
    # 其余：3比特
    if len(probs_n2) == 4:
        lengths_n2 = [1, 2, 3, 3]
        avg_length_n2 = sum(l * pr for l, pr in zip(lengths_n2, probs_n2))
        R_block2 = avg_length_n2 / n
        print(f"块长为2的Huffman编码: R = {R_block2:.4f} bits/symbol")
    
    # 方案4：块长为8的Huffman编码（模拟）
    n = 8
    # 典型集大小约 2^(nH)
    typical_size = 2**(n * H)
    total_size = 2**n
    # 压缩率 ≈ log2(typical_size) / n = H
    R_block8 = np.log2(typical_size) / n
    print(f"块长为8的典型集编码: R ≈ {R_block8:.4f} bits/symbol")
    
    # 方案5：算术编码（接近熵）
    R_arithmetic = H + 0.01  # 略高于熵
    print(f"算术编码（模拟）: R ≈ {R_arithmetic:.4f} bits/symbol")
    
    print()
    print(f"理论极限（熵）: {H:.4f} bits/symbol")
    print()
    
    # 可视化压缩率随块长的变化
    import matplotlib.pyplot as plt
    
    block_sizes = [1, 2, 4, 8, 16, 32]
    rates = []
    
    for n in block_sizes:
        # 典型集编码的压缩率
        rate = H + 1/n  # 简化模型
        rates.append(rate)
    
    plt.figure(figsize=(10, 6))
    plt.plot(block_sizes, rates, 'bo-', linewidth=2, markersize=8, label='典型集编码')
    plt.axhline(y=H, color='r', linestyle='--', linewidth=2, label=f'熵 H={H:.4f}')
    plt.xlabel('块长 n', fontsize=12)
    plt.ylabel('压缩率 R (bits/symbol)', fontsize=12)
    plt.title('压缩率随块长的变化', fontsize=14)
    plt.legend(fontsize=11)
    plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.savefig('compression_rate_vs_blocksize.png', dpi=150)
    plt.show()

source_coding_theorem_demo()

步骤1: 合并d(0.15)和e(0.15) → de(0.30)
步骤2: 合并c(0.20)和de(0.30) → cde(0.50)  [取最小的两个]
       实际应该是: 合并c(0.20)和某个0.25 → ...

让我们重新计算：
初始: a(0.25), b(0.25), c(0.20), d(0.15), e(0.15)
合并d,e → de(0.30)
剩余: a(0.25), b(0.25), c(0.20), de(0.30)
合并c,a → ca(0.45)  [取最小的两个: c(0.20)和a或b(0.25)]
实际: 合并c(0.20)和a(0.25) → ca(0.45)
剩余: b(0.25), de(0.30), ca(0.45)
合并b,de → bde(0.55)
剩余: ca(0.45), bde(0.55)
合并ca,bde → root(1.0)

码字（从根向下）:
a: 00 (或01, 取决于左右分配)
b: 10
c: 01
d: 110
e: 111

平均码长: 0.25×2 + 0.25×2 + 0.20×2 + 0.15×3 + 0.15×3 = 2.3 bits
熵: -0.25log(0.25)×2 - 0.20log(0.20) - 0.15log(0.15)×2 ≈ 2.28 bits
冗余: 2.3 - 2.28 = 0.02 bits

import heapq
from collections import Counter

class HuffmanCoder:
    """Huffman编码器"""
    
    def __init__(self, frequencies):
        """
        初始化
        
        参数:
            frequencies: 符号频率字典 {symbol: frequency}
        """
        self.frequencies = frequencies
        self.codebook = {}
        self.reverse_codebook = {}
        self._build_tree()
    
    def _build_tree(self):
        """构建Huffman树"""
        # 创建优先队列
        heap = [[freq, [symbol, ""]] for symbol, freq in self.frequencies.items()]
        heapq.heapify(heap)
        
        while len(heap) > 1:
            # 取出最小的两个
            lo = heapq.heappop(heap)
            hi = heapq.heappop(heap)
            
            # 给左子树添加'0'，右子树添加'1'
            for pair in lo[1:]:
                pair[1] = '0' + pair[1]
            for pair in hi[1:]:
                pair[1] = '1' + pair[1]
            
            # 合并
            merged = [lo[0] + hi[0]] + lo[1:] + hi[1:]
            heapq.heappush(heap, merged)
        
        # 提取码字
        remaining = heapq.heappop(heap)[1:]
        self.codebook = dict(remaining)
        self.reverse_codebook = {v: k for k, v in self.codebook.items()}
    
    def encode(self, data):
        """编码数据"""
        return ''.join(self.codebook[symbol] for symbol in data)
    
    def decode(self, encoded):
        """解码数据"""
        result = []
        current_code = ""
        for bit in encoded:
            current_code += bit
            if current_code in self.reverse_codebook:
                result.append(self.reverse_codebook[current_code])
                current_code = ""
        return ''.join(result)
    
    def average_code_length(self):
        """计算平均码长"""
        total_freq = sum(self.frequencies.values())
        avg_len = sum(
            len(code) * freq 
            for symbol, code in self.codebook.items()
            for s, freq in self.frequencies.items()
            if s == symbol
        ) / total_freq
        return avg_len
    
    def entropy(self):
        """计算熵"""
        total = sum(self.frequencies.values())
        probs = [freq / total for freq in self.frequencies.values()]
        return -sum(p * np.log2(p) for p in probs if p > 0)
    
    def efficiency(self):
        """计算编码效率"""
        H = self.entropy()
        L = self.average_code_length()
        return H / L if L > 0 else 0
    
    def display_codebook(self):
        """显示码本"""
        print("Huffman码本:")
        print("-" * 40)
        for symbol, code in sorted(self.codebook.items(), key=lambda x: len(x[1])):
            freq = self.frequencies[symbol]
            print(f"  '{symbol}': {code:10s} (频率: {freq})")
        print()
        print(f"平均码长: {self.average_code_length():.4f} bits")
        print(f"熵: {self.entropy():.4f} bits")
        print(f"效率: {self.efficiency()*100:.2f}%")


# 使用示例
if __name__ == "__main__":
    import numpy as np
    
    # 英文字母频率（简化版）
    english_freq = {
        'e': 127, 't': 91, 'a': 82, 'o': 75, 'i': 70,
        'n': 67, 's': 63, 'h': 61, 'r': 60, 'd': 43,
        'l': 40, 'c': 28, 'u': 28, 'm': 24, 'w': 24
    }
    
    coder = HuffmanCoder(english_freq)
    coder.display_codebook()
    
    # 编码示例
    message = "hello world"
    encoded = coder.encode(message.lower().replace(' ', ''))
    decoded = coder.decode(encoded)
    
    print(f"原始消息: hello world")
    print(f"编码后: {encoded[:30]}...")
    print(f"解码后: {decoded}")

初始区间: [0, 1)

处理'b' (概率范围 [0.5, 0.8)):
  新区间: [0.5, 0.8)

处理'a' (概率范围 [0, 0.5)):
  子区间宽度: 0.8 - 0.5 = 0.3
  'a'占前50%: [0.5, 0.5 + 0.3×0.5) = [0.5, 0.65)

处理'c' (概率范围 [0.8, 1.0)):
  子区间宽度: 0.65 - 0.5 = 0.15
  'c'占最后20%: [0.5 + 0.15×0.8, 0.5 + 0.15×1.0) = [0.62, 0.65)

最终区间: [0.62, 0.65)
输出: 该区间内的一个数，如 0.625 = 0.101₂

class ArithmeticCoder:
    """简化算术编码器（用于教学）"""
    
    def __init__(self, probabilities):
        """
        初始化
        
        参数:
            probabilities: 概率字典 {symbol: probability}
        """
        self.probs = probabilities
        self.symbols = list(probabilities.keys())
        
        # 计算累积概率
        self.cum_probs = {}
        cum = 0
        for sym in self.symbols:
            self.cum_probs[sym] = (cum, cum + probabilities[sym])
            cum += probabilities[sym]
    
    def encode(self, message):
        """
        编码消息
        
        参数:
            message: 符号列表
        
        返回:
            编码后的区间中点
        """
        low, high = 0.0, 1.0
        
        for symbol in message:
            range_width = high - low
            sym_low, sym_high = self.cum_probs[symbol]
            
            high = low + range_width * sym_high
            low = low + range_width * sym_low
        
        # 返回区间中点
        return (low + high) / 2
    
    def decode(self, value, length):
        """
        解码
        
        参数:
            value: 编码值
            length: 原始消息长度
        
        返回:
            解码后的符号列表
        """
        result = []
        low, high = 0.0, 1.0
        
        for _ in range(length):
            range_width = high - low
            
            # 找到对应的符号
            for symbol in self.symbols:
                sym_low, sym_high = self.cum_probs[symbol]
                
                if low + range_width * sym_low <= value < low + range_width * sym_high:
                    result.append(symbol)
                    
                    # 更新区间
                    high = low + range_width * sym_high
                    low = low + range_width * sym_low
                    break
        
        return result


# 使用示例
if __name__ == "__main__":
    probs = {'a': 0.5, 'b': 0.3, 'c': 0.2}
    coder = ArithmeticCoder(probs)
    
    message = ['b', 'a', 'c']
    encoded = coder.encode(message)
    decoded = coder.decode(encoded, len(message))
    
    print("算术编码演示")
    print("=" * 40)
    print(f"原始消息: {message}")
    print(f"编码值: {encoded:.6f}")
    print(f"解码消息: {decoded}")
    print(f"匹配: {message == decoded}")

class LZWCodec:
    """LZW编解码器"""
    
    def __init__(self):
        pass
    
    def encode(self, data):
        """
        LZW编码
        
        参数:
            data: 输入字符串
        
        返回:
            编码后的索引列表
        """
        # 初始化字典（所有单字符）
        dictionary = {chr(i): i for i in range(256)}
        next_code = 256
        
        result = []
        current = ""
        
        for char in data:
            combined = current + char
            if combined in dictionary:
                current = combined
            else:
                # 输出当前串的编码
                result.append(dictionary[current])
                # 将新串加入字典
                dictionary[combined] = next_code
                next_code += 1
                current = char
        
        # 输出最后一个串
        if current:
            result.append(dictionary[current])
        
        return result
    
    def decode(self, codes):
        """
        LZW解码
        
        参数:
            codes: 编码后的索引列表
        
        返回:
            解码后的字符串
        """
        # 初始化字典
        dictionary = {i: chr(i) for i in range(256)}
        next_code = 256
        
        result = []
        prev_string = chr(codes[0])
        result.append(prev_string)
        
        for code in codes[1:]:
            if code in dictionary:
                current_string = dictionary[code]
            elif code == next_code:
                # 特殊情况
                current_string = prev_string + prev_string[0]
            else:
                raise ValueError(f"Invalid code: {code}")
            
            result.append(current_string)
            
            # 更新字典
            dictionary[next_code] = prev_string + current_string[0]
            next_code += 1
            
            prev_string = current_string
        
        return ''.join(result)


# 使用示例
if __name__ == "__main__":
    codec = LZWCodec()
    
    original = "TOBEORNOTTOBEORTOBEORNOT"
    encoded = codec.encode(original)
    decoded = codec.decode(encoded)
    
    print("LZW编码演示")
    print("=" * 40)
    print(f"原始数据: {original}")
    print(f"编码后: {encoded}")
    print(f"解码后: {decoded}")
    print(f"匹配: {original == decoded}")
    print(f"原始长度: {len(original)} 字符")
    print(f"编码长度: {len(encoded)} 索引")

import numpy as np
import matplotlib.pyplot as plt

def binary_entropy(p):
    """二元熵函数"""
    if p == 0 or p == 1:
        return 0
    return -p * np.log2(p) - (1-p) * np.log2(1-p)

def rate_distortion_binary(p, D_values):
    """
    伯努利(p)信源的率失真函数（汉明失真）
    """
    R_values = []
    D_max = min(p, 1-p)
    
    for D in D_values:
        if D <= D_max:
            R = binary_entropy(p) - binary_entropy(D)
        else:
            R = 0
        R_values.append(max(0, R))  # 确保非负
    
    return R_values

# 可视化
p = 0.3
D_values = np.linspace(0, 0.5, 100)
R_values = rate_distortion_binary(p, D_values)

plt.figure(figsize=(10, 6))
plt.plot(D_values, R_values, 'b-', linewidth=2.5)
plt.xlabel('失真 D', fontsize=12)
plt.ylabel('率 R(D) (bits/symbol)', fontsize=12)
plt.title(f'率失真函数 (伯努利({p})信源, 汉明失真)', fontsize=14)
plt.grid(True, alpha=0.3)
plt.axhline(y=binary_entropy(p), color='r', linestyle='--', alpha=0.5, 
            label=f'H(X) = {binary_entropy(p):.4f}')
plt.axvline(x=min(p, 1-p), color='g', linestyle='--', alpha=0.5, 
            label=f'D_max = {min(p, 1-p):.4f}')
plt.legend(fontsize=11)
plt.tight_layout()
plt.savefig('rate_distortion.png', dpi=150)
plt.show()

print(f"伯努利({p})信源的率失真函数")
print(f"H(X) = {binary_entropy(p):.4f}")
print(f"D_max = {min(p, 1-p):.4f}")

import zlib
import bz2
import lzma
import time
import os

class CompressionBenchmark:
    """压缩性能基准测试"""
    
    def __init__(self, data):
        self.data = data if isinstance(data, bytes) else data.encode()
        self.original_size = len(self.data)
    
    def benchmark(self, name, compress_func, decompress_func):
        """测试单个算法"""
        # 压缩
        start = time.time()
        compressed = compress_func(self.data)
        compress_time = time.time() - start
        
        # 解压
        start = time.time()
        decompressed = decompress_func(compressed)
        decompress_time = time.time() - start
        
        # 验证
        assert decompressed == self.data, f"{name}: 解压结果不匹配!"
        
        compressed_size = len(compressed)
        ratio = compressed_size / self.original_size
        
        return {
            'name': name,
            'original_size': self.original_size,
            'compressed_size': compressed_size,
            'ratio': ratio,
            'compress_time': compress_time,
            'decompress_time': decompress_time
        }
    
    def run_all(self):
        """运行所有算法测试"""
        results = []
        
        # zlib (DEFLATE)
        results.append(self.benchmark(
            'zlib (DEFLATE)',
            lambda d: zlib.compress(d),
            lambda d: zlib.decompress(d)
        ))
        
        # bz2
        results.append(self.benchmark(
            'bz2',
            lambda d: bz2.compress(d),
            lambda d: bz2.decompress(d)
        ))
        
        # lzma
        results.append(self.benchmark(
            'lzma',
            lambda d: lzma.compress(d),
            lambda d: lzma.decompress(d)
        ))
        
        # 打印结果
        print("压缩性能比较")
        print("=" * 70)
        print(f"{'算法':<20} {'压缩率':>10} {'压缩时间':>12} {'解压时间':>12}")
        print("-" * 70)
        
        for r in results:
            print(f"{r['name']:<20} {r['ratio']:>10.4f} {r['compress_time']:>12.6f}s {r['decompress_time']:>12.6f}s")
        
        return results


# 使用示例
if __name__ == "__main__":
    # 生成测试数据（英文文本）
    test_text = """
    Information theory is a mathematical framework for quantifying information.
    It was founded by Claude Shannon in 1948. The central concept is entropy,
    which measures the uncertainty or randomness of a random variable.
    Data compression is one of the most successful applications of information theory.
    From ZIP files to JPEG images, from MP3 audio to H.264 video, compression 
    technology is everywhere. The source coding theorem gives the theoretical limit 
    of compression, guiding the development of compression algorithms for over 
    half a century.
    """ * 100  # 重复以增加大小
    
    benchmark = CompressionBenchmark(test_text)
    benchmark.run_all()

import pickle
import struct

class HuffmanFileCompressor:
    """基于Huffman的文件压缩器"""
    
    def __init__(self):
        self.coder = None
    
    def compress(self, input_path, output_path):
        """压缩文件"""
        # 读取文件
        with open(input_path, 'rb') as f:
            data = f.read()
        
        # 统计频率
        freq = {}
        for byte in data:
            freq[byte] = freq.get(byte, 0) + 1
        
        # 构建Huffman编码器
        from collections import Counter
        self.coder = HuffmanCoder(freq)
        
        # 编码
        encoded_bits = self.coder.encode(data)
        
        # 保存：[码本大小][码本][编码数据位数][编码数据]
        codebook_bytes = pickle.dumps(self.coder.codebook)
        encoded_bytes = self._bits_to_bytes(encoded_bits)
        
        with open(output_path, 'wb') as f:
            # 码本大小（4字节）
            f.write(struct.pack('>I', len(codebook_bytes)))
            # 码本
            f.write(codebook_bytes)
            # 编码数据位数（4字节）
            f.write(struct.pack('>I', len(encoded_bits)))
            # 编码数据
            f.write(encoded_bytes)
        
        original_size = len(data)
        compressed_size = os.path.getsize(output_path)
        print(f"压缩: {input_path} -> {output_path}")
        print(f"  原始大小: {original_size} 字节")
        print(f"  压缩大小: {compressed_size} 字节")
        print(f"  压缩率: {compressed_size/original_size*100:.2f}%")
    
    def decompress(self, input_path, output_path):
        """解压文件"""
        with open(input_path, 'rb') as f:
            # 读取码本大小
            codebook_size = struct.unpack('>I', f.read(4))[0]
            # 读取码本
            codebook_bytes = f.read(codebook_size)
            codebook = pickle.loads(codebook_bytes)
            # 读取编码数据位数
            num_bits = struct.unpack('>I', f.read(4))[0]
            # 读取编码数据
            encoded_bytes = f.read()
        
        # 重建编码器
        self.coder = type('obj', (object,), {
            'codebook': codebook,
            'reverse_codebook': {v: k for k, v in codebook.items()}
        })()
        
        # 解码
        encoded_bits = self._bytes_to_bits(encoded_bytes, num_bits)
        decoded = self._decode_bits(encoded_bits)
        
        with open(output_path, 'wb') as f:
            f.write(decoded)
        
        print(f"解压: {input_path} -> {output_path}")
    
    def _bits_to_bytes(self, bits):
        """比特列表转字节"""
        # 填充到8的倍数
        padding = (8 - len(bits) % 8) % 8
        bits = bits + '0' * padding
        
        result = bytearray()
        for i in range(0, len(bits), 8):
            byte = int(bits[i:i+8], 2)
            result.append(byte)
        
        return bytes(result)
    
    def _bytes_to_bits(self, data, num_bits):
        """字节转比特列表"""
        bits = ''
        for byte in data:
            bits += format(byte, '08b')
        return bits[:num_bits]
    
    def _decode_bits(self, bits):
        """解码比特流"""
        result = bytearray()
        current = ''
        for bit in bits:
            current += bit
            if current in self.coder.reverse_codebook:
                result.append(self.coder.reverse_codebook[current])
                current = ''
        return bytes(result)