哈夫曼编码:实现电文编码并保证唯一译码
使用哈夫曼编码可以实现电文编码并使译码唯一。
首先统计每个字符出现的频率,即'W'出现2次,'I'出现2次,'N'出现4次,'E'出现1次,'L'出现1次。将其转化为权值,得到{2,2,4,1,1}。
然后根据这些权值构建哈夫曼树,得到以下树形结构:
10
/ \
4 6
/ \ /
'W' 'I' 'N' 3
/
'L' 'E'
最后对于每个字符,从根节点出发,向左走为0,向右走为1,得到对应的编码:
'W':00 'I':01 'N':1 'E':1010 'L':1011
因此'WINNIE WILL WIN'可以编码为:0001010111111000100010110。对于这个编码,唯一的译码方式是:从前往后扫描编码,遇到0就向左走,遇到1就向右走,当走到叶子节点时,即找到了对应的字符,将其输出,并回到根节点继续扫描。
原文地址: https://www.cveoy.top/t/topic/ocfm 著作权归作者所有。请勿转载和采集!