基于哈夫曼树对txt文件的解压与压缩 |
您所在的位置：网站首页 › 文件压缩算法是什么 › 基于哈夫曼树对txt文件的解压与压缩 |
基于哈夫曼树对txt文件的解压与压缩
|
目录 一、什么是哈夫曼树 二、构造哈夫曼树 1.新建Node类 2.创建结点 3.对结点进行从小到大排序 4.构造树 三、哈夫曼编码 四、压缩 1.读取文本信息 2.用HashMap统计每个字符出现的频率,创建对应的节点 3.把字符串数据替换成对应的编码 4.把字符编码每8个一组转成byte写入文件 五、解压 1.读文件数据并转成二进制 2.将编码转成字符串 3.将字符串写入到文件中 一、什么是哈夫曼树我们知道，从树根到某个结点的路径是从根结点开始沿着某个分支到达该结点的一个结点序列，路径所含的分支数(结点个数减1)称为此路径的长度。而一棵树的路径长度是指从树根到其余各结点的路径长度之和。结点的带权路径长度是指从根结点到该结点之间的路径长度与该结点上所带权值的乘积。设一棵树有 n个叶结点，每个叶结点带有权值Wₖ,从根结点到每个叶结点的长度lₖ,则每个叶结点的带权路径长度之和就是这棵树的带权路径长度（WPL），它可以被表 哈夫曼树就是WPL值最小的二叉树，它的特点是权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
使用二分法，根据结点的权值对结点从小到大排序。 public void sort(List list,int start,int end) { int left = start; int right = end; TreeNode key1 = list.get(start); int key = key1.data; while(right > left) { while(list.get(right).data>=key && right > left) { right--; } while(list.get(left).data left) { left++; } if(list.get(left).data > list.get(right).data) { TreeNode temp = list.get(left); list.set(left, list.get(right)); list.set(right, temp); } } list.set(start, list.get(left)); list.set(left, key1); if(start < left) { sort(list,start,left-1); } if(right < end) { sort(list,left+1,end); } } 4.构造树 public TreeNode creatTree() { TreeNode leftNode; TreeNode rightNode; TreeNode node; while(list.size() > 1) { //当队列中没有元素时结束循环 leftNode = list.remove(0); //取出队列的第一个结点 rightNode = list.remove(0); //取出的是权值最小的两个结点 node = new TreeNode(leftNode.data + rightNode.data); //创建权值为最小两个数和的结点 node.left = leftNode; node.right = rightNode; list.add(node); //将新结点存入队列中 sort(list,0, list.size()-1); //对结点从小到大排序 if(list.size()==1) { //当队列中只有一个结点时，该结点就是哈夫曼树的根结点 node = list.remove(0); node.left = leftNode; node.right = rightNode; return node; } } return null; } 三、哈夫曼编码每个结点的左分支被记为0，右分支被记为1。某一字符的编码可通过组合从根结点到该字符结点(叶结点)的路径上所标注的0、1得到。注意前缀编码树的特点是每个字符必是叶结点，且树中没有度为1的结点。一个字符的编码长度即是该字符结点在其哈夫曼树中的深度d-1。哈夫曼编码的特点使得出现频率高的字符编码短些，出现频率低的字符编码长些，这样可以达到更好的压缩效果。 在前面新建的Node类中，加入code的元素。 //用递归方法给树的叶子编码 public void setCode(TreeNode node) { if(node.left != null) { node.left.code = node.code + "0"; setCode(node.left); } if(node.right != null) { node.right.code = node.code + "1"; setCode(node.right); } } 四、压缩1.根据给定的字符串内容（读取文本文件），统计每个字符出现的频率,创建对应的节点 2.根据节点的权值创建哈夫曼树，统计字符编码 3.把字符数据替换成对应的编码 4.把字符编码每8个一组转成byte写入文件：最后一个字节不足要补0，将它补满8位 5.把码表写入文件 1.读取文本信息 public String readFile(String path) { File file = new File(path); FileReader fr; String str = ""; //存放文本信息 try { fr = new FileReader(file); BufferedReader br = new BufferedReader(fr); //可以对文件进行行输入 String s = ""; while((s = br.readLine()) != null) { //br.readLine()行输入 str += s; } } catch (Exception e) { e.printStackTrace(); } return str; } 2.用HashMap统计每个字符出现的频率,创建对应的节点 public void number(String m) { //s为文本信息 hm = new HashMap(); for(int i = 0;i < m.length();i++) { if(!(hm.containsKey(m.charAt(i)+""))) { //与hm比较，若没有该字符 hm.put(m.charAt(i)+"",1); //m.charAt(i)是char类型，+""自动转为String }else { hm.put(m.charAt(i)+"", hm.get(m.charAt(i)+"")+1);//若有该字符，则+1； } } for(String s : hm.keySet()) { System.out.print(s + ":" + hm.get(s) + " "); StrTreeNode node = new StrTreeNode(hm.get(s),s); //创建结点 list.add(node); } }接下来就是用得到的结点，根据结点权值，也就是字符出现的频率进行从小到大排序，然后再构造树并生成哈夫曼编码，并将哈夫曼编码存入码表hmcode 3.把字符串数据替换成对应的编码 //将哈夫曼编码存入码表 HashMap hmcode = new HashMap(); //存放字符和对应的编码，码表 public void inorder(StrTreeNode node,String m) { if(node.left == null && node.right == null) { hmcode.put(node.s, node.code); //存入码表 } if(node.left != null) { inorder(node.left,m); } if(node.right != null) { inorder(node.right,m); } } //把字符串数据替换成对应的编码 public String setCode(String m) { StringBuilder stringb = new StringBuilder(); for(int i = 0;i < m.length();i++) { stringb.append(hmcode.get(m.charAt(i)+"")); } return stringb.toString(); } 4.把字符编码每8个一组转成byte写入文件 //把字符编码没每8个一组转成byte写入文件：最后一个字节不足要补全 public void change(String n) throws Exception { FileOutputStream fos = new FileOutputStream(fName); ObjectOutputStream oos = new ObjectOutputStream(fos); int c = 8 - n.length() %8; int x = 8 - c; int data; if(c!=0) { //不足8为补0 for(int i = 1;i |
例如队列：3，7，5，1，8 。对这一组数字进行从小到大的规则排序，排序后为1，3，5，7，8。在这些数字中选择两个最小的数字：1，3 用类似树杈的“树枝”连接两个最小的数，在顶点处计算出这两个数字的和4，将这两数字和加入队列中，并比较剩下的数字和这个和的大小，再取出两个最小的数字进行排序。重复上述操作，构成的哈夫曼树如右图所示【本文地址】