Huffman Implementation with Python

码表

Token	Frequency
a	10
e	15
i	12
s	3
t	4
space	13
n	1

生成 Huffman 编码

根据上面的码表，先生成 Huffman 树，然后生成 Huffman 编码。代码如下：

def binary_tree(val=None):

    return [val, [], []]

def insert_left(root, branch):

    root[1] = branch

def insert_right(root, branch):

    root[2] = branch

def get_root_val(root):

    return root[0]

def set_root_val(root, val):

    root[0] = val

def get_left_child(root):

    return root[1]

def get_right_child(root):

    return root[2]

def is_leaf(root):

    if len(get_left_child(root)) == 0 and len(get_right_child(root)) == 0:

        return True

    return False

def huffman(data):

    while len(data) > 1:

        data = sorted(data, key=lambda e: e[1])

        root = binary_tree()

        left = data.pop(0)

        right = data.pop(0)

        insert_left(root, left[0])

        insert_right(root, right[0])

        data.append((root, left[1] + right[1]))

    return data[0][0]

def tree2code(root, code, plan):

    if is_leaf(root):

        plan[get_root_val(root)] = code

    else:

        tree2code(get_left_child(root), code+'0', plan)

        tree2code(get_right_child(root), code+'1', plan)

def build_data(d):

    l = list()

    for pair in d.items():

        root = binary_tree(pair[0])

        l.append((root, pair[1]))

    return l

if __name__ == '__main__':

    d = {'a':10, 'e':15, 'i':12, 's':3, 't':4, 'space':13, 'n':1}

    l = build_data(d)

    tree = huffman(l)

    plan = dict()

    tree2code(tree, str(), plan)

    print(plan)

运行结果得到

{'i': '00', 'space': '01', 'e': '10', 't': '1100', 'n': '11010', 's': '11011', 'a': '111'}

结果分析

根据文献[1]，可以知道当前的解是最好结果。

Bibliography

[1] 《数据结构与算法分析——C语言描述》 机械工业出版社