霍夫曼编码和游程编码

### 霍夫曼编码

霍夫曼编码是一种前缀码，能够根据频率分配不同长度的编码给不同的元素。对于高频率出现的字符，会赋予较短的位串作为其编码；而对于低频字符，则采用较长的位串表示[^1]。

import heapq
from collections import defaultdict, Counter

def build_huffman_tree(frequencies):
    heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
            
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]

        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
        
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

data = "this is an example for huffman encoding"
frequency = Counter(data)

huff_code = build_huffman_tree(frequency)
print("Symbol".ljust(10) + "Frequency".ljust(10) + "Huffman Code")
for p in huff_code:
    print(f"{p[0]}".ljust(10), end="")
    print(f"{frequency[p[0]]}".ljust(10), end="")
    print(p[1])

此代码展示了如何构建霍夫曼树并生成相应的霍夫曼编码表。通过这种方式可以实现高效的数据压缩。

### 游程编码

游程编码（Run-Length Encoding,RLE）属于简单的重复模式替换技术，在连续相同数据项序列被单个数据值及其计数所取代的情况下特别有效。例如字符串`AAABBBCCDAA`会被转换成`(A,3)(B,3)(C,2)(D,1)(A,2)`的形式存储，从而减少所需空间量。

#include <iostream>
#include <string>

std::string encode(const std::string& input){
    int count=1;
    char prev=input[0];
    std::string result="";

    for(size_t i=1;i<input.length();++i){
        if(input[i]==prev){
            ++count;
        }else{
            result+=std::to_string(count)+prev;
            prev=input[i];
            count=1;
        }
    }

    // Add last sequence
    result += std::to_string(count) + prev;

    return result;
}

int main(){
    std::string original="WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB";
    std::cout << "Original string:\n" << original << "\nEncoded string:\n" << encode(original);
}

这段 C++ 程序实现了基本的 RLE 编码功能，它遍历输入字符串并将相邻相同的字符数量与其对应的字符组合起来形成新的紧凑表达形式。