一、最优二叉树（哈夫曼树）
（1）定义：带权路径长度WPL最小的二叉树，又称为最优树，也称哈夫曼树 （2）构造哈夫曼树的过程 1）将给定的n个权值{w1,w2,w3...wn}作为n个根结点的权值构造一个具有n棵二叉树的森林，其中每棵二叉树只有 一个根结点; 2）在森林中选取两颗根结点权值最小的二叉树作为左右子树构造一颗新的二叉树，并且新的二叉树的根节点权值 等于这两课树根节点的权值和; 3）在森林中，将上面选择的这两颗根权值最小的的二叉树从森林中删除，并将刚刚新构建的二叉树加入到森林中; 4）重复上面的(2)和(3)步骤，知道森林中只有一颗二叉树为止，则此时森林中剩余的这可二叉树就是哈夫曼树(最 优二叉树)
二、哈夫曼编码
1、建立哈夫曼树 2、对边进行编号 3、得出叶子结点路径 4、得到字符编码
三、哈夫曼压缩实现
1.读取压缩文件，并统计每个字节出现次数 2.构建哈夫曼结点 3.构建哈夫曼树 4.统计哈夫曼编码，并把哈夫曼编码存储到对应数组位置中 5.写入每个编码长度 6.写入哈夫曼编码 7.再次读入文件的哈夫曼编码，并写入压缩文件(保存数据顺序，用于解压)
哈夫曼压缩具体实现：
1.例如源文件：abcdabcaba
2.构造码表
1）统计每个字节出现的次数（避免让没有出现过的字节生成编码），次数即每个字节的权，以权为叶子结点构造哈夫曼树，每个字节必然在0-255之间
2）把有出现次数的位置拿出来，用次数来构造节点，并生成哈夫曼树
97:4, 98:3, 99:2, 100:1
根据次数构造节点，生成树：4,3,2,1，哈夫曼树为（红色为权值节点）：
权值编码为：
97 - 4 : 0
98 - 3 :10
100-1 :110
99 - 2 :111
码表（密码本）
1.生成编码
源文件abcdabcaba 生成的编码为：
0111011000111010110
2.写入码表
码表中的编码串起来：
3.写入编码内容（即写入码表，便于解压时对照码表解压）
A)写入每个位置的编码长度占用256个字节
B)写入编码内容：011101100 2个字节
此自定义哈夫曼压缩代码的缺陷：
1、无法对空文件进行压缩
2、占用内存很大，效率比较低
3、能压缩的文件类型很少
4、系统的解压文件无法解压该压缩文件
哈夫曼压缩代码实现： package com.test.yasuo; import java.io.FileInputStream; import java.io.FileOutputStream; import java.util.LinkedList; /** * * @author lhz * */ public class FileYasuo { public static void main(String[] args) { FileYasuo fy = new FileYasuo(); int[] src = fy.countTimes("C:\\Users\\lhx\\Desktop\\data.txt"); HffumNode root = fy.createHffumTree(src); String[] string = fy.getCode(root, ""); fy.readFile("C:\\Users\\lhx\\Desktop\\data.txt", "result.zip", string); } /** * 统计文件中出现的字符次数 * * @param path文件路径 * * @return 返回索引为0-255的值为次数的数组 */ public int[] countTimes(String path) { int[] times = new int[256];// byte一个字节0-255共256个索引 try { FileInputStream fis = new FileInputStream(path); int value = fis.read(); while (value != -1) { times[value]++;// 索引为value位置加1 value = fis.read(); } fis.close(); } catch (Exception e) { e.printStackTrace(); } return times; } /** * 构造哈夫曼树 * * @param src * 传入的次数数组 * @return 返回根结点 */ public HffumNode createHffumTree(int[] src) { LinkedList<HffumNode> list = new LinkedList<HffumNode>(); // 将数组构造成结点 for (int i = 0; i < src.length; i++) { if (src[i] != 0) {// 去掉值为0的位置 HffumNode node = new HffumNode(); node.setData(src[i]); node.setIndex(i);// 记录存值的位置 // 排序放入 list.add(getIndex(node, list), node); } } // 构造哈夫曼树 while (list.size() > 1) { HffumNode node1 = list.removeFirst(); HffumNode node2 = list.removeFirst(); HffumNode newNode = new HffumNode(); newNode.setData(node1.getData() + node2.getData()); newNode.setLeft(node1); newNode.setRight(node2); list.add(getIndex(newNode, list), newNode); } return list.getFirst(); } /** * 遍历树得到编码 * * @param root根结点 * @param str编码 * @param codes编码数组索引0 * -255 */ public void searchCode(HffumNode root, String str, String[] codes) { if (root.getLeft() != null) { searchCode(root.getLeft(), str + "0", codes); } if (root.getRight() != null) { searchCode(root.getRight(), str + "1", codes); } if (root.getLeft() == null && root.getRight() == null) {// 打印叶子结点 codes[root.getIndex()] = str;// 如何输出编码数组?索引0-255 } } /** * 获取哈夫曼编码数组 * * @param root根结点 * @param str编码初始为空字符串 * @return */ public String[] getCode(HffumNode root, String str) { String[] codes = new String[256]; for (int i = 0; i < codes.length; i++) {// 给每个索引位置赋空字符串，不然为null codes[i] = ""; } searchCode(root, str, codes);// 指定索引位置赋值 return codes; } /** * 压缩文件 * * @param src源文件 * @param path目的文件 * @param codesMap编码表 */ public void readFile(String src, String path, String[] codesMap) { try { FileInputStream fis = new FileInputStream(src); FileOutputStream fos = new FileOutputStream(path); // 将码表写入文件 // 先写256个字节表示每个位置存储的长度 String codeStr = ""; for (int i = 0; i < codesMap.length; i++) { int codeLength = codesMap[i].length(); codeStr = codeStr + codesMap[i];// 将码表每个位置的数值连成字符串 fos.write(codeLength);// 将二进制转为十进制 fos.flush(); } // 将codeStr写入文件 TwoWriteFile(fos, codeStr); /************** 存储文件数据 ***********/ String code = ""; int value = fis.read(); while (value != -1) { code += codesMap[value];// 匹配文件 value = fis.read(); } fis.close(); // 按字节写 int length = TwoWriteFile(fos, code); // 存储补零的个数 fos.write(length); fos.flush(); fos.close(); } catch (Exception e) { e.printStackTrace(); } } /** * 获取放入list容器的索引 * * @param root新放入list的结点对象 * @param list放HffumNode的容器 * @return 返回要放入的索引位置 */ public int getIndex(HffumNode root, LinkedList<HffumNode> list) { for (int i = 0; i < list.size(); i++) { HffumNode node = list.get(i); if (root.getData() < node.getData()) { return i; } } return list.size(); } /** * 将8个字符串转为int * * @param code文件匹配所得编码字符串 * @return返回 */ public int StringToInteger(String code) { int result = 0; for (int i = 0; i < 8; i++) { result += (int) (code.charAt(i) - 48) * Math.pow(2, 7 - i); } return result; } /** * 将01写入文件 * * @param fos输出流 * @param code字符串 * @return返回补零个数 */ public int TwoWriteFile(FileOutputStream fos, String code) { try { // 按字节写 while (code.length() >= 8) {// 循环 String codeO = code.substring(0, 8); int myCode = StringToInteger(codeO); // 将写入到文件的字符删掉 code = code.substring(8); fos.write(myCode); } int length = 8 - code.length(); for (int i = 0; i < length; i++) { code += "0"; } int myCode = StringToInteger(code); fos.write(myCode); return length; } catch (Exception e) { } return 0; } } package com.test.yasuo; /** * 哈夫曼树结点类 * * @author lhz * */ public class HffumNode { private int data; private HffumNode left; private HffumNode right; private int index; public HffumNode() { } public int getData() { return data; } public void setData(int data) { this.data = data; } public HffumNode getLeft() { return left; } public void setLeft(HffumNode left) { this.left = left; } public HffumNode getRight() { return right; } public void setRight(HffumNode right) { this.right = right; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } } 四、 哈夫曼解压1.读取压缩文件
2.先从文件中读取码表
先读取256个字节，这256个字节为码表每个位置编码长度
a)再从文件读取 011101100 ，依照上面的长度数组将读取的哈夫曼编码还原到指定索引位置，即还原码表
4.数据根据码表，进行数据解密，并获取源数据
5.写入解压文件
自定义哈夫曼解压的缺陷：
只能解压上面自定义压缩后的文件
哈夫曼解压代码package com.test.jieya; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; /** * 文件解压功能的实现 * * @author lhz * */ public class JieYaMain { public static void main(String[] args) { JieYaMain jym = new JieYaMain(); // 共同享用一个输入流 try { FileInputStream fis = new FileInputStream( "D:\\Java\\adt-bundle-windows-x86_64-19_javaee_maven\\workspace\\Exercise\\result.zip"); // 读取压缩文件的前面256个字节 int[] codelength = jym.readLength(fis); // 读取接下来的几个字节，还原码表 String[] codemap = jym.readMabiao(fis, codelength); // 还原文件 jym.readData(fis, codemap, "test.txt"); } catch (Exception e) { e.printStackTrace(); } } /** * 还原每个位置存储的长度数组 * * @param fis * @return返回数组 */ public int[] readLength(FileInputStream fis) { // 数组存储每个位置的长度 int[] codelength = new int[256]; for (int i = 0; i < 256; i++) { try { codelength[i] = fis.read();// 读取一个字节 } catch (IOException e) { e.printStackTrace(); } } return codelength; } /** * 还原码表 * * @param fis输入流 * @param codelength长度数组 * @return码表 */ public String[] readMabiao(FileInputStream fis, int[] codelength) { int length = 0;// 01的长度 int lengthcode = 0;// 字节数 // 计算一共存储了多少个长度的01 for (int i = 0; i < codelength.length; i++) { length = length + codelength[i]; } // 计算需要读取多少的字节 // 奇数->length/8+1 if (length % 8 == 0) {// 偶数 lengthcode = length / 8; } else { lengthcode = length / 8 + 1; } // 读取lengthcode个字节 String code = ""; for (int i = 0; i < lengthcode; i++) { try { // 将读取的十进制转化为二进制 code = code + erToTen(fis.read()); } catch (IOException e) { e.printStackTrace(); } } // 还原码表 String[] codemap = new String[256];// 码表 for (int i = 0; i < codemap.length; i++) { codemap[i] = code.substring(0, codelength[i]); code = code.substring(codelength[i]); } return codemap; } /** * 读取文件中真正的数据 * * @param fis * @param codemap * @param path */ public void readData(FileInputStream fis, String[] codemap, String path) { // 最后一个字节是补零的个数 try { FileOutputStream fos = new FileOutputStream(path);// 输出流 String data = "";// 存储数据01串 while (fis.available() > 1) { // 原本读取的是整数 data = data + erToTen(fis.read()); } data = data.substring(0, data.length() - fis.read());// 减去补零的个数 // 匹配码表 int index = 1; while (data.length() > 0) { String first = data.substring(0, index);// 先取一个0或1 int a = pipei(first, codemap); if (a != -1) {// 匹配好了 fos.write(a); fos.flush(); data = data.substring(index);// 先截取，再改变index index = 1; } else {// 没有匹配 index++; // continue; } } fis.close(); fos.close(); } catch (Exception e) { e.printStackTrace(); } } /** * 将十进制转化为二进制 * * @param value要转为二进制的十进制整数 * @return 01字符串 */ public String erToTen(int value) { // 除二取余,最多除8次 String code = ""; for (int i = 0; i < 8; i++) { // 从下往上：低->高 code = value % 2 + code;// code初始就是""，已经将value % 8转化为字符串了 value = value / 2; } return code; } /** * 将读取的01串与码表匹配，匹配上了返回码表的索引，否则返回-1 * * @param data要对比的01字符串 * @param codemap码表 * @return码表的索引 */ public int pipei(String data, String[] codemap) { for (int i = 0; i < codemap.length; i++) { if (data.equals(codemap[i])) { return i; } } return -1; } }
