编程实现Shannon编码，Huffman编码 输入为信源概率分布，输出为Shannon码和Huffman码，平均码长和编码效率

好的，我可以为您提供一个Python实现。首先，让我们来了解一下Shannon编码和Huffman编码的基本思想：

Shannon编码：根据信源概率分布来构造一种无失真压缩编码方式，使得编码后的平均码长最小。

Huffman编码：根据信源概率分布来构造一棵二叉树，将每个符号对应的编码表示为从根节点到该符号所在叶子节点的路径上的0和1，使得编码后的平均码长最小。

接下来，让我们来看一下Python代码实现：

import heapq
from collections import Counter

def shannon_fano_encoding(probs, symbols):
    if len(probs) != len(symbols):
        raise ValueError("Length of probabilities and symbols should be the same")

    # Sort symbols based on probabilities
    sorted_symbols = sorted(zip(symbols, probs), key=lambda x: x[1], reverse=True)

    # Calculate cumulative probabilities
    cum_probs = [sorted_symbols[0][1]]
    for i in range(1, len(sorted_symbols)):
        cum_probs.append(cum_probs[-1] + sorted_symbols[i][1])

    # Initialize codewords
    codewords = {sorted_symbols[0][0]: '0'}

    # Get codewords for each symbol
    for i in range(1, len(sorted_symbols)):
        lower_bound = cum_probs[i-1]
        upper_bound = cum_probs[i]
        codeword = ''
        for j in range(len(codewords[sorted_symbols[i-1][0]])):
            if codewords[sorted_symbols[i-1][0]][j] == '0':
                codeword += '0'
            else:
                codeword += '1'
        for k in range(lower_bound, upper_bound):
            codewords[sorted_symbols[i][0]] = codeword + codewords[sorted_symbols[i][0]]

    # Calculate average code length and efficiency
    avg_code_length = sum([len(codewords[s]) * p for s, p in zip(symbols, probs)])
    efficiency = sum([p * (1 - p) for p in probs])

    return codewords, avg_code_length, efficiency

def huffman_encoding(probs, symbols):
    if len(probs) != len(symbols):
        raise ValueError("Length of probabilities and symbols should be the same")

    # Initialize heap
    heap = []
    for i in range(len(probs)):
        heapq.heappush(heap, (probs[i], symbols[i], None, None))

    # Build Huffman tree
    while len(heap) > 1:
        p1, s1, left1, right1 = heapq.heappop(heap)
        p2, s2, left2, right2 = heapq.heappop(heap)
        heapq.heappush(heap, (p1 + p2, None, (p1, s1, left1, right1), (p2, s2, left2, right2)))

    # Traverse Huffman tree to get codewords
    codewords = {}

    def traverse_tree(node, codeword):
        if node[1] is not None:
            codewords[node[1]] = codeword
        else:
            traverse_tree(node[2], codeword + '0')
            traverse_tree(node[3], codeword + '1')

    traverse_tree(heap[0], '')

    # Calculate average code length and efficiency
    avg_code_length = sum([len(codewords[s]) * p for s, p in zip(symbols, probs)])
    efficiency = sum([p * (1 - p) for p in probs])

    return codewords, avg_code_length, efficiency

# Example usage
probs = [0.2, 0.3, 0.1, 0.15, 0.25]
symbols = ['A', 'B', 'C', 'D', 'E']

shannon_codewords, shannon_avg_code_length, shannon_efficiency = shannon_fano_encoding(probs, symbols)
huffman_codewords, huffman_avg_code_length, huffman_efficiency = huffman_encoding(probs, symbols)

print("Symbols: ", symbols)
print("Probabilities: ", probs)
print("Shannon codewords: ", shannon_codewords)
print("Shannon average code length: ", shannon_avg_code_length)
print("Shannon efficiency: ", shannon_efficiency)
print("Huffman codewords: ", huffman_codewords)
print("Huffman average code length: ", huffman_avg_code_length)
print("Huffman efficiency: ", huffman_efficiency)

这个实现中，我们使用Python的heapq模块来实现堆排序，获取概率最小的两个符号。对于Shannon编码，我们使用Shannon-Fano算法来计算每个符号的编码。对于Huffman编码，我们使用最小堆来构建Huffman树，并遍历树来获取每个符号的编码。最后，我们计算平均码长和编码效率。

希望这个实现可以对您有所帮助！