Admin基本原理
Huffman编码是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。Huffman算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长度)的和最小。
1.Huffman树
Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子:
比如有以下数据, ABFACGCAHGBBAACECDFGFAAEABBB 先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面的是统计次数生成Huffman树:每次取最小的那两个节点(node)合并成一个节点(node),并且将累计数值相加作为新的接点的累计数值,最顶层的是根节点(root) 注:列表中最小节点的是指包括合并了的节点在内的所有节点,已经合并的节点不在列表中编码和解码
编码:将ABCDEFGH用Huffman树产生的编码对应着写到文件中,并且保留原始的Huffman树,主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树,每个Huffman树都必须有以下的结构: code,char,left,right,probability(出现次数),通常情况是利用一个数组结构。因为在解码的时候只需要用到code,所以只需要记录每个元素的编码就可以了。
解码:利用文件中保存的Huffman编码,一一对应,解读编码,把可变长编码转换为定长编码。
发展
由于Huffman编码需要扫描两次,第一次是统计数字,第二次是编码写文件,大大影响了速度,因此有人发明了enhanced Huffman aglorithm。这种算法只扫描一遍文件,动态产生Huffman树,即每读n个字节就重新编码一次Huffman树,以达到提高速度的目的。在解码的过程中使用动态还原技术。
免责声明：本站文字信息和图片素材来源于互联网，仅用于学习参考，如内容侵权与违规，请联系我们进行删除，我们将在三个工作日内处理。联系邮箱：chuangshanghai#qq.com（把#换成@）