压缩算法，对霍夫曼编码的改进

本文主要是介绍压缩算法，对霍夫曼编码的改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背景

霍夫曼编码是理论上的最优编码，但是，它依赖于“分割点”。例如，在源代码里，有大量的"if"，把多个字母合并成一个符号，似乎更好。
霍夫曼编码的极端情况，以1比特为单位进行编码。只有两个符号，用1比特表示这两个符号，用0表示0，用1表示1。结果是，并没有被压缩。

算法

压缩前的串为A，压缩后的串为B。
首先，对A进行统计。
按1字节统计，得到256个概率值；
按2字节统计，得到256²个概率值；
按n字节统计，得到256ⁿ个概率值；
256+256²+…+256ⁿ=M
删除概率为0的，得到N
处理N。对于多字节的符号，如"for"的概率是15，还要乘以它的长度，15×3=45
对N个符号运用霍夫曼编码，得到编码C
然后处理C
如果"if"的编码是11011
“i”=001，“f”=110
“i”+“f”=001.110，占6比特，比"if"的5比特更长，则保留"if"
如果"for"， “f”+“o”+“r”， “f”+“or”， “fo”+"r"中， "for"的编码不是最短的，则删除它
处理后的C’即为所求

问题

公式中，n不能太大，否则N会很大，以至于内存里装不下。

这篇关于压缩算法，对霍夫曼编码的改进的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---