这篇文章将为大家详细讲解有关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]++;/
免责声明:本站发布的内容(图片、视频和文字)以原创、来自互联网转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系QQ:712375056 进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
Copyright © 2009-2021 56dr.com. All Rights Reserved. 特网科技 特网云 版权所有 珠海市特网科技有限公司 粤ICP备16109289号
域名注册服务机构:阿里云计算有限公司(万网) 域名服务机构:烟台帝思普网络科技有限公司(DNSPod) CDN服务:阿里云计算有限公司 中国互联网举报中心 增值电信业务经营许可证B2
建议您使用Chrome、Firefox、Edge、IE10及以上版本和360等主流浏览器浏览本网站