一起来写一个压缩软件吧

December 5, 2016
AlgorithmData StructureJava

十几年前的时候,电脑的储存容量还很小,最大硬盘空间只有40G都是很常有的事情,Windows
XP安装时候加入了Zip打包功能,还有很早之前就很著名的压缩软件WinRAR,他们都可以将一堆文件打包并且压缩,换取更多的空间,这篇文章将会讲述霍夫曼压缩算法的基本原理,并且使用Java编写一个简单的压缩软件。

我们都知道,文件是使用字节来储存的,一个字节8个bit,普通的文件中,每一个字符就是一个字节,通常使用8个二进制数表示。

假设需要将字符串,MikeTech,编码。下表是组成字符串MikeTech所有的编码:

char ASCII Binary
M 77 0100 1101
i 69 0110 1001
k 107 0110 1011
e 65 0110 0101
t 116 0111 0100
c 99 0110 0011
h 68 0110 1000

所以编码后,MikeTech 8个字被转换为

0100 1101 0110 1001 0110 1011 0110 0101 0111 0100 0110 0101 0110 0011 0110
1000

解码的时候只需要每次读取8位,然后根据ASCII码表反查找然后再转换为字符就行。

在这种标准编码的情况下,不难发现,出现了两次的字母e和只出现了一次的字母M所需要的比特数是一样的,霍夫曼压缩可以优化这一点,这个算法可以使用较少的比特表示出现比较频繁的字符而使用较多的比特来表现偶尔出现的字符来节省空间,这样的话用来储存一个字符串的总比特数就会有所降低。

举个例子,ABBBBCC这个字符串,现在使用最短的比特来代表出现次数多的字符,B为0,C为1,A为01,这样,字符串编码就为 01 0 0 0 0 1
1,只用8位就可以表达出ABBBBCC,使用传统的方法却需要56位才可以,但是新的方法有个缺点,我使用了空格来隔开每一位,用于区分,如果我把空格拿掉的话就会产生歧义,01000011,这样的话,第一位是0,A和B第一位都可能是0,所以应该是A还是B呢?出现这个问题的原因是因为B的编码0是A的编码01前缀,所以,如果所有字符的编码都不会成为其他字符的编码的前缀的话就不在需要使用空格作为分隔符了。现在讲A改为1111,B为0,C改为110,现在再进行编码11110000110110,这样即使没有分隔符,从头开始读取的话,因为不存在前缀的问题所以这个编码解码后只能是ABBBBCC了。这种编码叫做
前缀码 是唯一的,不需要分隔符(空格)也能区分。比如平时所用的ASCII编码,他也是一种前缀码。

  • 单词查找树

可是如何生成前缀码呢,一个直接的方法就是构建一颗单词查找树了,如果在一颗树种,只有子叶代表字符,并且规定从根节点到子叶的路径(左链表示0,右链表示1)表示的比特字符串就可以作为前缀码,因为树中每个节点的路径都具有唯一性。但是怎样才能找到每个字符的最优的前缀码呢?如果在ABBBCC中规定A为1110,B为1111,C为0001,是的,这些的确都是前缀码,因为是唯一的,但是不是最优解,压缩效率并不高,但是有一种算法可以将比特流构造一颗最优的单词查找树。这个最优前缀码的寻找方法是霍夫曼发现的,所以最优前缀码也被成为霍夫曼编码,大量被使用在各种压缩解决方案中,比如JPEG图片。

当然还有一点要注意的,这个单词查找树就像字典一样,可以告诉你A为1111,B为0,C为110,因为这个编码不再是通用的ASCII代码了,所以压缩的时候也要一并写入压缩文件,要不然解压缩的时候程序只能看着11110000110110这么一堆前缀码而无从下手。

所以说压缩一个文件可以分为以下几个步骤了:

  • 读取文件中所有字节并且构建一颗单词查找树
  • 为每一种字符生成最优前缀码
  • 重新读取文件并且使用最优前缀码编码

这里注意下,霍夫曼压缩需要二次读取,因为构建完整的单词查找树需要遍历所有的字符才可以,第二次读取时候根据最优前缀码编码即可得到压缩后的编码。

接下来就可以开始设计程序了:

  • 霍夫曼树节点
  1. public class Node implements Comparable<Node>{
  2. public char ch; //为子节点时有用,储存当前字符
  3. public int freq; //ch出现的频数
  4. public final Node left,right; //左右节点
  5. public Node(char ch, int freq, Node left, Node right) {
  6. this.ch = ch;
  7. this.freq = freq;
  8. this.left = left;
  9. this.right = right;
  10. }
  11. //判断子叶
  12. public boolean isLeaf(){
  13. return left == null && right == null;
  14. }
  15. //比较器
  16. @Override
  17. public int compareTo(Node that) {
  18. return this.freq - that.freq;
  19. }
  20. }

其中ch用来储存字符,就像之前说的一样,只有当前节点是子叶的时候ch在存在,freq是这个字符出现的频数

  • 构建Huffman树

Huffman树,也称为最优二叉树,是一种带权路径长度最短的树,权值较大的节点离根越近,在这个应用中,权值就是Node中的freq,字符出现次数越多权值越大,越靠近根,这样前缀码就越短,压缩起来就更带劲。

首先遍历一遍文件,将所有字符出现的次数统计在一个数组里

  1. private static final int R = 256; //ASCII码表
  2. int[] freq = new int[R]; //频率表
  3. byte[] data = FileUtil.readFileByBytes(filePath);
  4. for (byte b:data){
  5. freq[b+128]++;
  6. }

上面这段代码用了一个比较方便的写法,因为一个字节是8位,8位最多只能表示0-256,所以创建一个256大小的数组来存放频率表,比如A的ASCII代码为65,遍历到A时,数组freq的第65个元素自加1,这样,这个数组的元素就代表频数,而这个元素的下标值就能代表这个元素代表的是哪一个字符。

为这么倒数第二行是b+128呢,因为Java中读取的Byte范围是-128~128,所以为了和256长度大小的数组同步我就加上了128.解压缩的时候再减去128即可。

那么还用ABBBBCC举例子,A出现次数为1,B为4,C为2,那么就可以得到一个数组为[1,4,2]

因为其他253个字符都没有出现所以不要考虑,何必为没有出现的字符构建前缀码呢?

好的,接下来我们来建树,[1,4,2],首先取出最小的两个数,1,2,分别作为左右节点,把权重相加(1+2=3)作为父节点。

然后把父节点3Push回数组中所以为[3,4],然后重复上一步骤,取出3,4作为左右节点,权重为7作为父节点。

是不是很简单,然后就能得到霍夫曼编码了:按照刚才说的,子叶储存字符,然后根据根到子叶的路径,向左为0向右为1。

所以A为00,B为1,C为01。

这就是最优前缀码(霍夫曼编码)了,发现了吧,现在A和C用两bit就能表示,以前要用8bit呢。而且B出现了四次,所以他离根最近,前缀码为1,更加节省空间。这样一来ABBBBCC,就变为了0011110101.

接下来看下代码吧:

  1. /**
  2. * 构建单词查找树
  3. * @param freq
  4. * @return
  5. */
  6. private Node buildTrie(int[] freq){
  7. //优先队列
  8. PriorityQueue<Node> pq = new PriorityQueue<Node>();
  9. for (char c = 0; c<R;c++){//ASCII码表
  10. if (freq>0)
  11. pq.add(new Node(c,freq,null,null));
  12. }
  13. //合并
  14. while (pq.size() > 1){
  15. Node left = pq.poll();//弹出最小元素
  16. Node right = pq.poll();
  17. Node parent = new Node('\0',left.freq+right.freq,left,right);
  18. pq.add(parent);
  19. }
  20. return pq.poll();
  21. }

这个函数传入之前生成的频数表来构建单词查找树,因为那个数组每次要得到最小的元素,所以这里使用了一个优先队列,为什么这个优先队列能比较大小?因为我Node类中实现了Comparable接口。可以看出,每当队列的大小大于1的时候就弹出两个元素,然后生成一个新的Node作为parent
node,然后再压入队列,以此类推。

  • 生成霍夫曼编码表

接下来是霍夫曼编码表的生成代码:

  1. private String[] buildCode(Node root){
  2. String[] st = new String[R]; //字符索引
  3. buildCode(st,root,"");
  4. return st;
  5. }
  6. /**
  7. * 根据单词查找树构建编译表
  8. * @param st
  9. * @param x
  10. * @param str
  11. */
  12. private void buildCode(String[] st,Node x,String str){
  13. if (x == null){
  14. return;
  15. }
  16. if (x.isLeaf()){
  17. st[ x.ch ] = str;
  18. }
  19. buildCode(st, x.left, str + '0');
  20. buildCode(st, x.right, str + '1' );
  21. }

传入刚才建立的树就可以构造霍夫曼编码表,返回一个String[]数组,同样,元素代表霍夫曼编码,数组下标代表字符编号。

好了,现在有了霍夫曼编码表,可以用这个新的“字典”来建立我们的压缩后的编码了:

  1. String compressedStr = ""
  2. //压缩
  3. for (int i=0;i<data.length;i++){
  4. int index = data[i] + 128;
  5. compressedStr += st[index];
  6. }

没啥难的吧,遍历文件中所有的字节,生成压缩后的字符。

  • 霍夫曼树的储存

好了,现在我们学会了建立霍夫曼树,学会了建立霍夫曼码表,学会了根据码表生成压缩后的字符。

但是有个问题,这棵树,怎么储存到文件中呢,解压时候要可是要用到这棵树的?压缩后的字符倒是简单,都是01二进制,用字节写入就行。

写入单词查找树可以使用这个方法:

对树进行一个 前序遍历
,前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。(根左右)

当访问的节点不是子叶节点时,写入比特0,当访问的节点是子叶节点时,写入比特1,之后写入子叶字符中的8位ASCII代码。

代码这么写,是不是很简洁呢:

  1. String treeStr = ""
  2. /**
  3. * 将单词查找树转换为比特
  4. * @param x
  5. */
  6. private void writeTire(Node x){
  7. if (x.isLeaf()){
  8. treeStr += '1';
  9. treeStr += x.ch;
  10. return;
  11. }
  12. treeStr += '0';
  13. writeTire(x.left);
  14. writeTire(x.right);
  15. }

表面上很简洁,但是有两个递归调用。

好了,压缩方面,差不多就结束了,可以把生成的霍夫曼树储存为字节,也可以吧压缩后的bit储存成字节。

总结下步骤:

读取文件

把读取的所有char值出现的频率生成freq频数数组

根据freq[]生成霍夫曼编码树

根据编码树生成霍夫曼码表

使用霍夫曼码表翻译文件中所有字符

将霍夫曼编码树(单词查找树)转换为比特字符串用于写入压缩文件

将翻译后的比特字符串用于写入压缩文件

当然,编码树和比特字符串都是一堆01,要是一同写入文件的话,读取的时候会有困难,因为你不知道那几位是树的比特字符串,那几位是翻译后的比特字符串,这个一会讲解。

  • 解压缩

接下来说解压缩,解压缩的时候读取这两段,重建霍夫曼树(字典查找树),然后根据压缩后的字符还原源文件的字符就行了。

首先就是读取单词查找树,假设我们已经提取出来了单词查找树的比特流,怎么重建呢?

  1. String treeStr = readtreeStr();
  2. /**
  3. * 重建单词查找树
  4. * @return Root Node
  5. */
  6. private Node readTire( ){
  7. char a = treeStr.charAt(0);
  8. treeStr = treeStr.substring(1,treeStr.length());//读取完一位删一位
  9. if (a == '1'){
  10. char b = treeStr.charAt(0);
  11. treeStr = treeStr.substring(1,treeStr.length());
  12. return new Node(b,0,null,null);
  13. }
  14. return new Node('\0',0,readTire(),readTire());
  15. }

和之前一样,代码很简洁,但是也需要用到两个递归。不懂的话可以多打断点调试看看。

然后就是解压缩了:

根据compressedStr的不断读取从根节点乡下移动,如果为0则移动左,如果为1则移动到右子节点。如果遇到叶子节点,则输出该节点的字符然后重新回到根节点,以此类推,直到compressedStr读取完成。最后把读取的所有字符写入新的文件,这个文件就是解压缩后的文件了。

  1. String compressedStr = "01010...." //压缩过的字符串
  2. public void decompress(){
  3. Node root = readTire();
  4. ArrayList<Byte> byteList = new ArrayList<>();
  5. while (compressedStr.length() > 0){
  6. Node x = root;
  7. while ( !x.isLeaf() ){
  8. char a = compressedStr.charAt(0);
  9. //删除读取的那一位
  10. compressedStr = compressedStr.substring(1,compressedStr.length());
  11. if ( a == '1'){
  12. x = x.right;
  13. } else{
  14. x = x.left;
  15. }
  16. }
  17. byteList.add((byte) (x.ch - 128));
  18. }
  19. byte[] arr = new byte[byteList.size()];
  20. for (int i = 0;i< byteList.size();i++){
  21. arr[i] = byteList.get(i);
  22. }
  23. String filePrefix = "decompressed_";
  24. FileUtil.writeFile(absPath+filePrefix+fileName,arr);
  25. }
  • 压缩文件设计

前面我提到了如果将树的字节流和压缩后字符串的字节流一并写入到新的文件中,会不好读取,因为没办法区分位置,为此我设计了一种文件。(本人第一次触碰这个领域,如有不对还请谅解)

这个压缩文件,我使用前64个字节来储存原始的文件名,比如我原始文件叫做1.jpg,解压后肯定要保持原名,程序得到byte数组后,前64字节,就是文件名。

之后的32字节,储存单词查找树字节流的长度,读取了这个之后,程序就可以知道从96字节开始之后几位是用来储存单词查找树了。

压缩字符串占位数,这个我解释下,压缩字符串是一串01字符,我将4个01合并为一个byte(因为Java是byte范围-128~128,我因为太懒所以不想弄8个01合成一个byte),这其中如果01字符不是4的倍数的话,最后一组byte就得使用0来弥补,但是弥补后解压时候得删除掉,不然数据就不一样了,所以这个占位数保存了一个0-4的数字,用于重建压缩字符串后删除掉后面多余的0.

使用这个文件结构,就可以实现压缩和解压了,以下是我的程序运行的样子:

我先新建了一个记事本47kb,里面的字符只有A,B和C,他们在数量上有着差异,其中A最多,B和C要少点。

下面三个文件信息分别是原始文件,压缩后的文件,和解压缩的文件,这样的设计使得解压缩后的文件和原始一样。

这个程序的源代码可以访问我的Github下载:

https://github.com/Yigang0622/HuffmanCompression

我的博客MikeTech app现已登陆iPhone和Android

iPhone版下载
Android版下载

Comments

July 21, 2018 at 10:52 am

There are no comments

keyboard_arrow_up