温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java如何实现哈夫曼压缩与解压缩功能

发布时间:2021-09-26 18:03:03 来源:亿速云 阅读:131 作者:小新 栏目:编程语言

这篇文章将为大家详细讲解有关java如何实现哈夫曼压缩与解压缩功能,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

一哈夫曼树以及文件压缩原理:

1.哈夫曼树 :

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近(频率越高的结点离根越进)。

以 下数组为例,构建哈夫曼树

int a[] = {0,1,2,3,4,5,6,7,8}

我们可以发现以下规律

1:9个数构成的哈夫曼树一共有17个结点,也就是可以n个数可以生产2*n-1个结点

2:数字越大的数离根节点越近,越小的数离根节点越近。

2.如何利用haffman编码实现文件压缩:

比如abc.txt文件中有以下字符aaaabbbccde,

1.进行字符统计

aaaabbbccde a : 4次b : 3次c : 2次d : 1次e : 1次

2.用统计结果构建哈夫曼树

3.用哈夫曼树生成哈夫曼编码(从根结点开始,路径左边记为0,右边记为1):

a的编码:1b的编码:01c的编码:000d的编码:0011e的编码:0010

4.哈夫曼编码代替字符,进行压缩。

源文件内容为:aaaabbbccde将源文件用对应的哈夫曼编码(haffman code)替换,则有:11110101 01000000 00110010 (总共3个字节)

由此可见,源文件一共有11个字符,占11字节的内存,但是经过用haffman code替换之后,只占3个字节,这样就能达到压缩的目的

二主要技术点:

1.哈夫曼树算法(哈夫曼压缩的基本算法)

2.哈希算法(字符统计时候会用到,也可以直接用HashMap统计)

3.位运算(涉及到将指定位,置0或置1)

4.java文件操作,以及缓冲操作。

5.存储模式(大端存储,小端存储,能看懂文件16进制的形式)

7.设置压缩密码,解压输入密码解压(小编自己加的内容)

三实现过程:

以上述aaaabbbccde为例

1.字符统计:

public class FreqHuf {public static int BUFFER_SIZE = 1 << 18;int freq[] = new int[256];File file;int count;List<HuffmanFreq> list;FreqHuf(String pathname) throws Exception {list = new ArrayList<>();this.file = new File(pathname);if(!file.exists()){throw new Exception("文件不存在");}System.out.println("进行字符统计中");CensusChar();System.out.println("字符统计完毕");}public void CensusChar() throws IOException{int intchar;FileInputStream fis = new FileInputStream(file);System.out.println("统计中"); //这种统计处理方案,速度极慢,不建议使用,以下采用缓存读数据。//while((intchar = fis.read()) != -1){//freq[intchar]++;//} //这里采用缓存机制,一次读1 << 18个字节,大大提高效率。byte[] bytes = new byte[BUFFER_SIZE];while((intchar = fis.read(bytes))!= -1){for(int i = 0; i < intchar;i++){int temp = bytes[i]& 0xff;freq[temp]++;}}fis.close();for(int i = 0; i < 256; i++){if(freq[i] != 0){this.count++;}}int index = 0;for(int i = 0; i < 256; i++){if(freq[i] != 0){HuffmanFreq huffman = new HuffmanFreq();huffman.character = (char)i;huffman.freq = freq[i];list.add(index, huffman);}}}}

//统计每个字符和其频率的类public class HuffmanFreq {char character;int freq;HuffmanFreq() {}HuffmanFreq(int character,int freq) {this.character = (char)character;this.freq = freq;} char getCharacter() {return character;} void setCharacter(int character) {this.character = (char)character;} int getFreq() {return freq;} void setFreq(int freq) {this.freq = freq;}byte[] infoToByte(){byte[] bt = new byte[6];byte[] b1 = ByteAnd8Types.charToByte(character);for(int i= 0; i < b1.length;i++){bt[i] = b1[i];}byte[] b2 = ByteAnd8Types.intToBytes2(freq);int index = 2;for(int i= 0; i < b2.length;i++){bt[index++] = b2[i];}return bt;} @Overridepublic String toString() {return "Huffman [character=" + character + ", freq=" + freq + "]";}}

2.用统计结果构建哈夫曼树:

//treeSize为总节点数private void creatTree(int treeSize){int temp;treeList = new ArrayList<HuffTreeNode>();for(int i = 0; i < treeSize; i++){HuffTreeNode node = new HuffTreeNode();treeList.add(i, node);}for(int i = 0; i < charCount; i++){HuffTreeNode node = treeList.get(i);node.freq.freq = charList.get(i).getFreq();node.freq.character = charList.get(i).getCharacter();node.left = -1;node.right = -1;node.use = 0;}for(int i = charCount; i < treeSize; i++){int index = i;HuffTreeNode node = treeList.get(i);node.use = 0;node.freq.character = '#';node.right = searchmin(index);node.left = searchmin(index);node.freq.freq = treeList.get(node.right).freq.freq + treeList.get(node.left).freq.freq;temp = searchmin(++index);if(temp == -1){break;}treeList.get(temp).use = 0;}}private int searchmin(int count){int minindex = -1;for(int i = 0; i < count; i++){if(treeList.get(i).use == 0){minindex = i;break;}}if(minindex == -1){return -1;}for(int i = 0; i < count; i++){if((treeList.get(i).freq.freq <= treeList.get(minindex).freq.freq) && treeList.get(i).use == 0){minindex = i;}}treeList.get(minindex).use = 1;return minindex;}

3.用哈夫曼树生成哈夫曼编码(从根结点开始,路径左边记为0,右边记为1):

private void bulidhuftreecode(int root, String str){if(treeList.get(root).getLeft() != -1 && treeList.get(root).getRight() != -1){bulidhuftreecode(treeList.get(root).getLeft(), str+"0");bulidhuftreecode(treeList.get(root).getRight(), str + "1");}else{treeList.get(root).code = str;}}

4.哈夫曼编码代替字符,进行压缩,压缩前首先要将文件头(文件标志,字符数量,最后一个字节有效位,密码)字符和其频率的那张表格写入文件,以便于解压缩

public void creatCodeFile(String path) throws Exception{byte value = 0;int index = 0;int arr[] = new int[256];int intchar;for(int i = 0; i < charCount; i++){arr[treeList.get(i).freq.character] = i;}File file = new File(path);    if(!file.exists()){       if(!file.createNewFile()){       throw new Exception("创建文件失败");       }    }int count = charList.size();HuffmanHead head = new HuffmanHead(count, howlongchar(count), password);        //将文件头信息写入文件this.write = new RandomAccessFile(file, "rw");write.write(head.InfoToByte());        //将字符及其频率的表写入文件for(HuffmanFreq freq : charList){byte[] bt = freq.infoToByte();write.write(bt);}//将字符用哈夫曼编码进行压缩,这里读写都是采用缓存机制byte[] readBuffer = new byte[BUFFER_SIZE];while((intchar = read.read(readBuffer))!= -1){ProgressBar.SetCurrent(read.getFilePointer());for(int i = 0; i < intchar;i++){int temp = readBuffer[i]& 0xff; String code = treeList.get(arr[temp]).code;char[] chars = code.toCharArray();for(int j = 0; j < chars.length; j++){if(chars[j] == '0'){value = CLR_BYTE(value, index);}if(chars[j] == '1'){value = SET_BYTE(value, index);}if(++index >= 8){index = 0;writeInBuffer(value);}}}}//此方法速度较慢//while((intchar = is.read()) != -1){//String code = treeList.get(arr[intchar]).code;//char[] chars = code.toCharArray();////for(int i = 0; i < chars.length; i++){//if(chars[i] == '0'){//value = CLR_BYTE(value, index);//}//if(chars[i] == '1'){//value = SET_BYTE(value, index);//}//if(++index >= 8){//index = 0;//oos.write(value);//}//}//}if(index != 0){writeInBuffer(value);}  byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);  write.write(Data);  write.close();read.close();}    //指定位,置1    byte SET_BYTE(byte value, int index){return (value) |= (1 << ((index) ^ 7));}    //指定位,置0byte CLR_BYTE(byte value, int index){ return (value) &= (~(1 << ((index) ^ 7)));}    //判断指定位是否为0,0为false,1为trueboolean GET_BYTE(byte value, int index){ return ((value) & (1 << ((index) ^ 7))) != 0;}

如果一个字节一个字节往文件里写,速度会极慢,为了提高效率,写也采用缓存,先写到缓存区,缓存区满了后写入文件,

private void writeInBuffer(byte value) throws Exception {if(writeBufferSize < BUFFER_SIZE){writeBuffer[writeBufferSize] = value;if(++writeBufferSize >= BUFFER_SIZE){write.write(writeBuffer);writeBufferSize = 0;}} else{throw new Exception("写入文件出错");}}

到这里压缩就完成了,以下为解压缩方法

1.从写入文件中的字符统计的表读出放入list里

public void init() throws Exception{char isHUf = read.readChar();        //验证文件头信息if(isHUf != '哈'){throw new Exception("该文件不是HUFFMAN压缩文件");}this.charCount = read.readChar();this.treeSize = 2*charCount -1;this.lastIndex = read.readChar();int password = read.readInt();if(password != this.password.hashCode()){System.out.println("密码错误");} else{System.out.println("密码正确,正在解压");}        //从文件中将字符统计的表读出byte[] buffer = new byte[charCount * 6];read.seek(10);read.read(buffer, 0, charCount * 6);ProgressBar.SetCurrent(read.getFilePointer());for(int i = 0; i < buffer.length; i+=6){byte[] buff = Arrays.copyOfRange(buffer, i, i+2);ByteBuffer bb = ByteBuffer.allocate (buff.length);  bb.put (buff);  bb.flip ();  CharBuffer cb = cs.decode (bb);  byte[] buff1 = Arrays.copyOfRange(buffer, i+2, i+6);  int size = ByteAnd8Types.bytesToInt2(buff1, 0);  HuffmanFreq freq = new HuffmanFreq(cb.array()[0], size);  charList.add(freq);}}

2.用统计结果构建哈夫曼树(和以上代码一样)

3.用哈夫曼树生成哈夫曼编码(从根结点开始,路径左边记为0,右边记为1)(和以上代码一样)

4.遍历文件每个字节,根据哈夫曼编码找到对应的字符,将字符写入新文件

public void creatsourcefile(String pathname) throws Exception{int root = treeList.size() - 1;int fininsh = 1;long len;File file = new File(pathname);if(!file.exists()){ if(!file.createNewFile()){ throw new Exception("创建文件失败");     }}write = new RandomAccessFile(file, "rw");int intchar;byte[] bytes = new byte[1<<18];int index = 0;while((intchar = read.read(bytes))!= -1){len = read.getFilePointer();ProgressBar.SetCurrent(len);for(int i = 0; i < intchar;i++){for(;index < 8 && fininsh != 0;){if(GET_BYTE(bytes[i], index)){root = treeList.get(root).right;} else{root = treeList.get(root).left;}if(treeList.get(root).right== -1 && treeList.get(root).left == -1){byte temp = (byte)treeList.get(root).freq.character;writeInBuffer(temp);root = treeList.size() - 1;}index++;if(len == this.goalfilelenth && i == intchar-1){if(index >= this.lastIndex){fininsh = 0;}}}index = 0;}}byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);write.write(Data);write.close();write.close();read.close();}

关于“java如何实现哈夫曼压缩与解压缩功能”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI