哈夫曼树建立 哈夫曼树编码算法 代码实现

哈夫曼树是一种用于数据压缩的树形结构，它可以根据数据的出现频率来构建对应的编码表，从而实现数据的高效压缩。下面是哈夫曼树编码算法的代码实现：

class Node:
    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char
        self.left = None
        self.right = None

def build_huffman_tree(s):
    freq_dict = {}
    for char in s:
        if char not in freq_dict:
            freq_dict[char] = 0
        freq_dict[char] += 1

    nodes = []
    for char, freq in freq_dict.items():
        nodes.append(Node(freq, char))

    while len(nodes) > 1:
        nodes = sorted(nodes, key=lambda x: x.freq)
        left = nodes[0]
        right = nodes[1]
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes = nodes[2:]
        nodes.append(parent)

    return nodes[0]

def get_codes(root, code, codes_dict):
    if root.char:
        codes_dict[root.char] = code
        return
    get_codes(root.left, code + '0', codes_dict)
    get_codes(root.right, code + '1', codes_dict)

def huffman_encoding(s):
    if not s:
        return '', None
    root = build_huffman_tree(s)
    codes_dict = {}
    get_codes(root, '', codes_dict)
    encoded = ''.join([codes_dict[char] for char in s])
    return encoded, root

def huffman_decoding(encoded, root):
    if not encoded or not root:
        return ''
    decoded = ''
    node = root
    for bit in encoded:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if node.char:
            decoded += node.char
            node = root
    return decoded

其中，`build_huffman_tree` 函数用于构建哈夫曼树，`get_codes` 函数用于获取字符对应的编码，`huffman_encoding` 函数用于对字符串进行编码，`huffman_decoding` 函数用于对编码后的字符串进行解码。

下面是一个简单的使用示例：

s = "hello world"
encoded, root = huffman_encoding(s)
print(encoded)  # 输出：'011111101101010000100111111110110110011000111001'
decoded = huffman_decoding(encoded, root)
print(decoded)  # 输出：'hello world'