Inflate动态Huffman解压缩

2024-05-05 19:04

本文主要是介绍Inflate动态Huffman解压缩,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

上个已经实现GZIP压缩文件格式的Inflate静态Huffman解压,这个实现Inflate的无压缩输出和动态Huffman解压。

Java语言实现,Eclipse下编写。

范式Huffman解码实现,输入huffman编码,输出原始数据

    // 范式huffman解码static class CanonicalCode {Vector<Node> table = new Vector<>();public CanonicalCode(int[] len) {for (int i=0; i<len.length; i++)if (len[i] != 0) // 过滤0-即不使用的节点table.add( new Node(i, len[i]) ); // value, bits Length (值, 待编码的编码长度)// 按编码长度+值排序Collections.sort(table, new Comparator<>() {@Overridepublic int compare(Node o1, Node o2) {return o1.bitLen!=o2.bitLen ? o1.bitLen-o2.bitLen : o1.value - o2.value;}});// 初始化第一个节点,实现规则1table.get(0).code = 1 << table.get(0).bitLen;// 计算每一个值得huffman编码for (int i=1; i<table.size(); i++) {Node node = table.get(i);Node prev = table.get(i-1);if (node.bitLen == prev.bitLen)  // 如果位长相等+1,实现规则2node.code = prev.code + 1;else if (node.bitLen > prev.bitLen)	// 位长不等,实现规则3node.code = ( prev.code + 1) << (node.bitLen - prev.bitLen);  // 左移'位长差'}}// 打印符号和huffman码的对应关系void debug() {for (int i=0; i<table.size(); i++) {Node n = table.get(i);System.out.println( n);}}// 根据传入的huffman编码,得到原始数值Integer findValue(int code) {for (Node node : table)if (node.code == code)return node.value;return null;}}

无压缩数据解码:

	bis.alignByte(); // 对齐字节边界int len = bis.ReadBits(16);int nlen = bis.ReadBits(16);assert len + nlen == 65535;for (int i=0; i<len; i++) {baos.Write(bis.ReadBits(8));}

动态huffman解码:

	else if (bType == 2) { // dynamic huffman// length有29个int hlit = bis.ReadBits(5);  // CL1数量 - 字/长度 码个数, LIT(literal/length)// distance码有30个int hdist = bis.ReadBits(5); // CL2数量 - 距离 码个数, DIST(distance)int hclen = bis.ReadBits(4); // c_len:code lengths for the code lengthint cl1_num = hlit + 257;  // CL1(Code Length 1): 'literal/length' length (literal[0..255]+压缩块结束[256] = 257)int cl2_num = hdist + 1;   // CL2(Code Length 2): 'distance code' lengthint ccl_num = hclen + 4;   // int[] cl1 = new int[cl1_num];int[] cl2 = new int[cl2_num];int[] ccl = new int[19]; // ccl bits// 读取CCLArrays.fill(ccl, 0);int[] PermutationtTable = new int[] {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };for (int i=0; i<ccl_num; i++) { // 读取CCL, 每个3bitint p = PermutationtTable[i];ccl[p] = bis.ReadBits(3);}// 通过CCL构建范式huffman编码CanonicalCode codes = new CanonicalCode(ccl);//读取CL1和CL2,'literal/length' Sequence 码流 + dist流IntBuffer sq = IntBuffer.allocate(cl1_num + cl2_num);int prevValue = -1, cl_decode_num = 0;while (cl_decode_num < cl1_num + cl2_num) {Integer value = null;int code = 1;// 范式huffman解码int bits = 1;while (value == null) {code = (code << 1 ) | bis.ReadBit();  // huffman编码value = codes.findValue( code); // 查找对应的符号if ( (bits++) > 15 )throw new java.lang.IllegalArgumentException();}// 处理value, 实现 0-15,16,17,18 这套规则int[] bs;if (value == 17) { // 标识长度int len = bis.ReadBits(3) + 3;bs = new int[len];Arrays.fill(bs, (byte)0);}else if (value == 18) {int len = bis.ReadBits(7) + 11;bs = new int[len];Arrays.fill(bs, (byte)0);}else if (value == 16) {int len = bis.ReadBits(2) + 3;bs = new int[len];Arrays.fill(bs, (byte) prevValue);}else if (value >=0 && value <= 15){bs = new int[] {  value };prevValue = value;}else throw new java.lang.IllegalArgumentException(value + "");sq.put(bs); // 写入符号cl_decode_num += bs.length; // 增加已得到的码流长度}int[] bs = sq.array();// 分别得到CL1和CL2 System.arraycopy(bs, 0, cl1, 0, cl1.length);System.arraycopy(bs, cl1.length, cl2, 0, cl2.length);CanonicalCode code1 = new CanonicalCode(cl1); // literal/length解码器CanonicalCode code2 = new CanonicalCode(cl2); // distance解码器// 解码Integer value = null;do {// 解literal/length码int code = 1;do {code = (code << 1) | bis.ReadBit(); // 读取Huffman codevalue = code1.findValue(code);} while (value == null);// 判断if (value >= 0 && value <= 255)// literalbaos.Write(value);else if (value == 256) // 结束标志break ;else if (value >= 257 && value <= 285) { // length// 处理长度int length = LengthExtraCodeLengthsTable.get(value);int bits = LengthExtraCodeBitsTable.get(value); // 扩展bit长if (bits != 0) {int ext =  ReadExtCode(bis, bits);length = length + ext;}// 读取huffman编码code = 1;do {code = (code << 1) | bis.ReadBit(); // 读取Huffman codevalue = code2.findValue(code);} while (value == null);// 处理距离int distance = DistanceExtraCodeLengthsTable.get(value);bits = DistanceExtraCodeBitsTable.get(value); // 距离扩展if (bits != 0) {int ext =ReadExtCode(bis , bits);distance = distance + ext;}// LZ77滑动窗口计算获取量int[] arr = baos.GetInts();int d = arr.length - distance;if (d < 0) {d = 0;length = length + distance - arr.length;}// 读取滑动窗口,写入到结果for (int i=0; i<length; i++) {int m = arr[ d + i];baos.Write(m);arr = baos.GetInts();}}} while (value != 256);}

输出结果:

对待压缩文件sample-5.svg 计算md5值,得到:84018a59da62b5af9de4c0843ce5d0b6

使用gzip对文件压缩

使用Java程序对压缩后的文件sample-5.svg.gz解压缩,得到sample.svg

对解压后的文件计算md5值,得到84018a59da62b5af9de4c0843ce5d0b6

解压前文件的md5值==解压后的文件的md5值。

这篇关于Inflate动态Huffman解压缩的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/962434

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b

Windows下php扩展开发c++动态库

PHP扩展开发,从零了解到初步完成一个小项目,经过三天的仔细研究,现整理如下 一、需求介绍 PHP扩展开发,调用自己之前的c++动态库,完成功能 二、项目之前 系统:windows xp  开发工具:vs 2008 web环境:apache2.4  PHP5.3.29-VC9-ts-x86 aphach和PHP 环境之前已经搭建完成 PHP源码:去官网http://www.php.n

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

vue2实践:第一个非正规的自定义组件-动态表单对话框

前言 vue一个很重要的概念就是组件,作为一个没有经历过前几代前端开发的我来说,不太能理解它所带来的“进步”,但是,将它与后端c++、java类比,我感觉,组件就像是这些语言中的类和对象的概念,通过封装好的组件(类),可以通过挂载的方式,非常方便的调用其提供的功能,而不必重新写一遍实现逻辑。 我们常用的element UI就是由饿了么所提供的组件库,但是在项目开发中,我们可能还需要额外地定义一