赫夫曼编码
- 赫夫曼编码在数据压缩领域有着广泛的应用，压缩率在20%-90%，是一种重要的算法
算法思想（以字符串压缩为例）：
- 统计字符串各字符出现的次数包括空格
- 按照上面字符出现的次数构建一个赫夫曼树，次数作为权值。赫夫曼树构建如下：
1.对权值进行升序排序，将每个数据都可以看做一个节点
2.取出最小的两个节点
3.构造新的节点，新节点作为这两个节点的根节点，其权值是取出节点权值之和，并在原来的排序集合中删除刚取出的两个节点
4.再将新的根节点加入到原来的排序集合中按根节点权值的大小进行排序，重复1234步将简历一颗赫夫曼树。
-对赫夫曼树节点的位置按方向进行编码，向左为0，向右为1
例子如下：
image.png
image.png
image.png
算法过程会遇到的一个统计对应的字符(已转换成字节数组)出现的次数的方法总结如下：
image.png
网友评论