Huffman编码是一种压缩算法,一种通过字符出现的频率和二叉树来进行的压缩算法,下面通过一个简单的例子看看如何构建它:

假设现在要压缩的字符串为:abbcccdddd。

统计字符出现频率

第一步我们就是要遍历这个字符串,然后统计出每个字符出现的频率,可以得到如下Map:

background Layer 1 a b c d 字符 出现次数 1 2 3 4

排序,组装二叉树

1.先将数组排序,将数组中前两个元素(出现频率最低的两个)放在一个新建节点的左右两侧,同时删除那两个元素,并将新建的节点放入数组进行下一轮排序。(新建节点的频率等于最低两个元素之和)

2.重复上面的操作,直到所有的节点都被放入树中。

3.遍历树,树的左边赋值0,树的右边赋值1,就可以得到所有字符被编码是多少了。上面的文字过程如下图所示:

background Layer 1 a b c d 1 2 3 4 c d a b 3 4 3 d a b 6 c 4 4 a b c d 0 1 0 1 0 1

Huffman编码的计算过程是不断排序,构建树,因此它的结果不唯一,因为可能有的字符频率一样,那么树的结果就不一定相同。

得到结果

经过上面的计算,我们可以得到每个字符的编码,如下:

background Layer 1 a b c d 100 101 11 0 字符 编码

因此,原来的abbcccdddd就可以表示成1001011011111110000。

最后,上代码:

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字