范式Huffman树在文件压缩项目中的应用
范式huffman树
- 范式huffman树是在huffman树的基础之上,进行了一些强制性的约定,即:对于同一层节点中,所有的叶子节点都调整到左边,然后,对于同一层的叶子节点按照符号顺序从小到大调整 ,最后按照左0右1的方式分配编码。
- 只要知道一个符号的编码位长就可以知道它在范式树上的位置。即:码表中只要保存每个符号的编码长度(即节点在树中的高度)即可,其远远要比符号频度小
- 相同位长的编码之间都相差1
- 第n层的编码可以根据上层算出来:code = (code + count[n-1])<<1
范式huffman树不用创建,可以利用huffman树推到出来:
- 对huffman树中的每个叶子节点求层数,得出huffman码表
- 对huffman码表按照:码长(节点在树中的高度)为第一关键字、符号为第二关键字进行排序
- 通过以上两步就可以得出范式huffman树的码表,然后按照上面的公式既可以计算出范式huffman码表
基于范式huffman树的压缩与解压缩
压缩
- 通过huffman码表推算出每个字符的范式huffman编码
- 读取源文件,将源文件中的每个字节按照对应的范式huffman编码进行改写
压缩文件的格式
- 先保存各个字节对应的码字长度(huffman压缩中保存的是符号及符号出现的频率)
- 保存压缩数据
解压缩
从压缩数据中获取符号的编码位长,构建符号位长表
根据编码位长建立解码表
编码:可以位长算出来,此处保存成数字
符号数量:通过map或者unordered_map来进行统计
符号索引:在符号位长表中的首次出现下标
解码
- 注意:范式huffman编码有一个很重要的特性即长度为i的码字的前j位的数值大于长度为j的码字的数值,其中i > j。
- 循环进行一下操作,直到所有的比特流解析完成:设i=0
- 从解码表的第i行开始,根据编码位长从压缩数据比特流中获取相应长度的比特位。
- 将读取的数据与首编码相减,假设结果为num
- 如果num>=符号数量,i++,继续1,如果num小于符号数量,进行4
- 将符号索引加上num,用该结果从符号位长表对应位置解析出该符号
例如,输入数据“11110”。令i = 0,此时编码位长为2。读取2位的数据“11”与首编码相减等于3。3大于等于符号数量,于是i = i + 1等于1。此时编码位长为3。读取3位的数据“111”与首编码相减等于1。 1大于等于符号数量,于是i = i + 1等于2。此时编码位长为5。读取5位的数据“11110”与首编码相减等于2。2小于符号数量,2加符号索引4等于6。从表2.3中可以查到序号为6的符号是“E”。从而解码出符号“E”。跳过当前已经解码的5位数据,可以重新开始解码下一个符号。