哈夫曼编码原理与Python实现代码（附手动推导过程原稿真迹）

哈夫曼编码依据字符出现概率来构造异字头（任何一个字符的编码都不是其他字符的前缀）的平均长度最短的码字，通过构造二叉树来实现，出现频次越多的字符编码越短，出现频次越少的字符编码越长。为了演示哈夫曼编码原理，我在纸上简单推导了一下，见下图（字有点丑，请忽略这个小问题）：

实现哈夫曼编码过程的Python代码如下：

from heapq import heapify, heappush, heappop

from itertools import count

from collections import Counter

from random import choice

from string import ascii_letters, digits

def huffman(seq, frq):

#这里的count()依次生成0,1,2,3,4,...

#主要用来入堆时保持顺序

num = count()

#对原始列表进行堆化

trees = list(zip(frq, num, seq))

heapify(trees)

while len(trees)>1:

#弹出堆中频次最少的两个元素

#_表示不关心这个值

fa, _, a = heappop(trees)

fb, _, b = heappop(trees)

#合并后生成新节点，重新入堆

heappush(trees, (fa+fb, next(num), [a,b]))

#返回建好的二叉树

return trees[0][-1]

def codes(tree, prefix=''):

if len(tree) == 1:

#注意，这里不能合并成一个return (tree, prefix)语句

yield (tree, prefix)

return

#二叉树左边节点编码为0，右边节点编码为1

for bit, child in zip('01', tree):

#在父节点编码基础上，接上每个节点的编码

for pair in codes(child, prefix + bit):

yield pair

def main(seq):

#统计各字符频次

global temp

temp = Counter(seq)

#这里只是为了让输出结果更直观，但实际上会影响效率

for item in sorted(temp.items(), key=lambda x: x[1], reverse=True):

print(item)

print('='*20)

#根据各字符出现频次，生成哈夫曼树

seq = list(temp.keys())

frq = [temp[t] for t in seq]

tree = huffman(seq, frq)

#根据哈夫曼树，返回各字符编码的生成器对象

return codes(tree)

letters = ascii_letters + digits

avgLength = 0

#生成随机字符串，模拟信源信号

seq = ''.join((choice(letters) for i in range(100)))

print(seq+'\n'+'='*20)

#按编码长度从小到大输出

#这里只是为了让输出结果更直观，但实际上会影响效率

for item in sorted(main(seq), key=lambda x: len(x[1])):

print(item)

avgLength += temp.get(item[0]) * len(item[1])

#计算并输出平均码长

print(avgLength/len(seq))