分享

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

 ly88 2024-04-26 发布于山西
发布于 2018-04-16 15:12:39
2.3K0
举报
文章被收录于专栏: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))

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多