哈夫曼加密文件
编程技术 / houtizong 发布于 3年前 71
在上一篇介绍过哈夫曼编码的基础知识,下面就直接介绍使用哈夫曼编码怎么来做文件加密或者压缩与解压的软件,对于新手来是有点难度的,主要还是要理清楚步骤;
加密步骤:
1,统计文件中字节出现的次数,作为权值
2,创建节点和哈夫曼树
3,得到每个子节点01串
4,使用哈夫曼编码表示每个字节
5,将哈夫曼编码每8位转成一个byte
6,定义写出文件的格式, 码表+字节数据
解压:
1,读取文件中的码表与字节数据
2,将字节还原成01串
3,根据01串还原字节
4,将原始文件写入新文件,该文件就是解压之后的新文件
上述解压与加密里面的难点可能就是字节的拼接与拆分
代码已经打包
创建压缩与解压的公共类
package huffman;/** * 二叉树的节点类 * * @author kowloon * */public class TreeNode {int obj;// 子节的次数(权值)Byte b = null;// 子节int flag = -1;// 节点是左节点还是右节点 0 左 1右 -1根TreeNode parent;// 父节点TreeNode leftChild;// 左子节点TreeNode rightChild;// 右子节点public TreeNode(int obj, Byte b) {this.obj = obj;this.b = b;}public String toString() {return obj + "";}}
压缩类:
package huffman;import java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.ObjectOutputStream;import java.util.Comparator;import java.util.HashMap;import java.util.PriorityQueue;import java.util.Set;public class HuffmanTree {public static void main(String[] args) {HuffmanTree tree = new HuffmanTree();// byte b = tree.string2Byte("10000011");// System.out.println(b);// 1.统计文件的子节个数HashMap<Byte, Integer> map = tree.countBytes("F:\\abc\\bb.txt");// 遍历MapSet<Byte> keys = map.keySet();for (byte b : keys) {// 根据key得到Valueint value = map.get(b);System.out.println(b + "次数：" + value);}// 2.得到哈夫曼树TreeNode root = tree.createHuffman(map);// 3.得到哈夫曼编码HashMap<Byte, String> mapCode = tree.hfmTree2HfmCode(root);// 4.得到01串String str = tree.byte2HfmCode(mapCode, "F:\\abc\\bb.txt"); System.out.println(str);// 5.将01串每8位转成字节byte[] bs = tree.hfmCode2ByteArray(str);for (int i = 0; i < bs.length; i++) {System.out.println(bs[i]);}String path = "F:\\abc\\bb.txtRar";// 写出压缩文件tree.writeHfmFile(mapCode, bs, path);}/** * 统计指定文件中每个子节出现的次数 * * @param path要统计的文件 * @return 返回HashMap<Byte, Integer> <子节，次数> */public HashMap<Byte, Integer> countBytes(String path) {HashMap<Byte, Integer> map = new HashMap<Byte, Integer>();try {// 输入流FileInputStream fis = new FileInputStream(path);// 包装成缓冲流BufferedInputStream bis = new BufferedInputStream(fis);// 读取一个子节int t = bis.read();while (t != -1) {byte b = (byte) t;// 判断该子节是否出现过if (map.containsKey(b)) {// 如果统计过，就取出以前的次数，+1int count = map.get(b);count++;map.put(b, count);} else {// 第一次碰到该子节，就存放在map中，次数为1map.put(b, 1);}// 读取下一个子节t = bis.read();}bis.close();fis.close();} catch (Exception ef) {ef.printStackTrace();}return map;}/** * 将数组中的元素作为权值构建哈夫曼树 * * @param array * @return */public TreeNode createHuffman(HashMap<Byte, Integer> map) {// 1.构建节点队列PriorityQueue<TreeNode> nodeList = createNodeQueue(map);// 2.建树TreeNode root = createTreeByQueue(nodeList);return root;}/** * 根据数组构造节点排序队列 * * @param array * 要构造节点的权值数组 return 返回装有节点的排序队列 */private PriorityQueue<TreeNode> createNodeQueue(HashMap<Byte, Integer> map) {// 自动排序队列PriorityQueue<TreeNode> nodeList = new PriorityQueue<TreeNode>(11,new MyComparable());// 1.将HashMap<Byte,Integer>的key作为权值，构造节点Set<Byte> keys = map.keySet();for (byte key : keys) {int value = map.get(key);// 定义该节点对应的次数和子节TreeNode node = new TreeNode(value, key);nodeList.add(node);}return nodeList;}// 自定义比较器class MyComparable implements Comparator<TreeNode> {@Overridepublic int compare(TreeNode o1, TreeNode o2) {return o1.obj - o2.obj;}}// **********************************************************///** * 2.根据排序队列构造哈弗曼树 * * @param nodeList * 排序队列 * @return 返回构造发哈夫曼树的根节点 */public TreeNode createTreeByQueue(PriorityQueue<TreeNode> nodeList) {while (nodeList.size() > 1) {// 取出权值最小的两个节点TreeNode n1 = nodeList.poll();TreeNode n2 = nodeList.poll();// 将两个节点构造成一棵树，使用两个节点的权值和作为根节点的权值TreeNode n3 = new TreeNode(n1.obj + n2.obj, null);n3.leftChild = n1;n3.rightChild = n2;n1.flag = 0;// 左0n2.flag = 1; // 右1n1.parent = n3;n2.parent = n3;// 将新的树放入队列nodeList.add(n3);}// 如果到这里证明队列中只有一个节点或者没有节点TreeNode root = nodeList.poll();return root;}/** * 根据哈夫曼树得到该树上每个叶子节点的哈夫曼编码, 、 每个叶子节点对应一个子节 可以认为是得到了每个子节对应的哈夫曼编码 * * @param root * 哈夫曼树 * @return HashMap<Byte,String> K：叶子节点对应的子节 V：该节点的哈夫曼编码 */public HashMap<Byte, String> hfmTree2HfmCode(TreeNode root) {HashMap<Byte, String> map = new HashMap<Byte, String>();getTreeCode(root, null, map, "");// getTreeCode2(root, null, map);return map;}/** * 获得哈夫曼树上的叶子节点的哈夫曼编码 * * @param root * :当前要遍历的节点 parent:当前遍历的节点的父节点 map:存储哈夫曼编码的映射 s:记录当前节点哈夫曼编码的字符串 * */private void getTreeCode(TreeNode root, TreeNode panent ,HashMap<Byte, String> map, String s) {if (root != null) {if (root.flag != -1) {// 输出跟节点s += root.flag;}// 获取左子节点TreeNode left = root.leftChild;// 如果有，getTreeCode(left, root, map, s);// 获得右字节点TreeNode right = root.rightChild;getTreeCode(right, root, map, s);} else {map.put(panent.b, s);}}/** * 根据哈夫曼编码，将文件中的子节按照文件内容的顺序使用哈夫曼编码表示，得到一个01字符串 * * @param map * ：码表 return 使用哈夫曼编码表示的01串 */public String byte2HfmCode(HashMap<Byte, String> map, String path) {String str = "";try {// 输入流FileInputStream fis = new FileInputStream(path);// 包装成缓冲流BufferedInputStream bis = new BufferedInputStream(fis);int t = bis.read();while (t != -1) {byte b = (byte) t;// 得到该子节对应的编码,并拼接到一起成一个01串String code = map.get(b);str = str + code;t = bis.read();}} catch (Exception ef) {ef.printStackTrace();}return str;}/** * 将01字符串每8位作为一个子节的8个bit转成 一个子节 如果字符串总长度%8=num,则num为01串补0的个数 000 return * 数组的最后一个子节表示倒数第二个子节是补了几个0的 * */public byte[] hfmCode2ByteArray(String str) {int len = 0;// 子节数组的长度int length = str.length();if (length % 8 == 0) {// 如果能够被整除len = length / 8 + 1;} else {// 如果不能被整除len = length / 8 + 1 + 1;}// 定义数组来存放转化来的子节byte[] bs = new byte[len];int index = 0;while (str.length() >= 8) {// 截取下来的8个01String newStr =str.substring(0, 8);// 除去已经被截取的前8位str = str.substring(8);// 将8个01转成子节byte b = string2Byte(newStr);bs[index] = b;index++;}if (str.length() > 0) {// 循环完之后，str的长度肯定是<8的。通过补0的方式凑成8位int num = 8 - str.length();// 计算补0的个数for (int i = 0; i < num; i++) {str += "0";}// 将补0的8个位转成子节byte b = string2Byte(str);bs[index] = b;// 将补0的个数存放在子节数组的最后一个位置bs[bs.length - 1] = (byte) num;} else {// 如果没有补0，就在最后一个下标位置存一个0bs[bs.length - 1] = 0;}return bs;}/** * 将8位01串转成子节 00000011 */private byte string2Byte(String str) {short b = Short.valueOf(str, 2);return (byte) b;}/** * 将码表和子节数据写到文件，即为压缩之后的文件 * * @param codeMap * :码表 data 子节数据 path:要存的压缩文件路径 * */public void writeHfmFile(HashMap<Byte, String> codeMap, byte[] data,String path) {try {// 根据文件路径建立文件输出流FileOutputStream fos = new FileOutputStream(path);// 包装成对象输出流ObjectOutputStream oos = new ObjectOutputStream(fos);// // 写HashMap对象// oos.writeObject(codeMap);oos.writeInt(codeMap.size());System.out.println("码表长度：" + codeMap.size());Set<Byte> keys = codeMap.keySet();for (byte key : keys) {String value = codeMap.get(key);oos.writeByte(key);oos.writeObject(value);}// 写数据长度oos.writeInt(data.length);// 写数据oos.write(data);oos.flush();oos.close();fos.close();} catch (Exception ef) {ef.printStackTrace();}}// ***************获得哈夫曼编码的方法二***********************************//private void getTreeCode2(TreeNode root, TreeNode parent,HashMap<Byte, String> map) {if (root != null) {// 获取左子节点TreeNode left = root.leftChild;// 如果有，getTreeCode2(left, root, map);// 获得右字节点TreeNode right = root.rightChild;getTreeCode2(right, root, map);} else {// 如果执行else,则parent肯定是叶子节点String s = "" + parent.flag;TreeNode node = parent.parent;while (node != null && node.flag != -1) {s = node.flag + s;node = node.parent;}map.put(parent.b, s);}}// **************************************************///** * 遍历树 * * @param root * 树的根节点 */public void printTree(TreeNode root) {if (root != null) {// 输出跟节点System.out.println(root);// 获取左子节点TreeNode left = root.leftChild;// 如果有，printTree(left);// 获得右字节点TreeNode right = root.rightChild;printTree(right);}}}
解压类:
package huffman;import java.io.BufferedOutputStream;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.ObjectInputStream;import java.util.ArrayList;import java.util.HashMap;/** * 解压缩 * * * */public class UnHufman {public static void main(String args[]) {//byte[] bss = new byte[3000000000];// 第一步：读取文件，得到码表和子节数组UnHufman uf = new UnHufman();byte[] bs = uf.readFile("F:\\abc\\bb.txtRar");// for (byte b : bs) {// System.out.println(">>" + b);// }// 将子节数组转成二进制，得到01串String str = uf.byte2String(bs);System.out.println(str);// 根据01串和码表，还原编码对应的子节，该子节即为压缩之前的原始子节ArrayList<Byte> list = uf.string2SrcBytes(str);for (byte b : list) {System.out.println(b);}// 将原始子节写到文件uf.write2File(list, "F:\\abc\\bb_解压.txt");}// 存放读取到的码表数据HashMap<String, Byte> mapCode = new HashMap<String, Byte>();/** * 读取压缩文件，得到码表和子节数据 * * @param path * 压缩的文件地址 * @return 返回读取到的子节数据 */public byte[] readFile(String path) {try {// 根据文件路径建立文件输出流FileInputStream fos = new FileInputStream(path);// 包装成对象输出流ObjectInputStream oos = new ObjectInputStream(fos);// 码表的长度int len = oos.readInt();for (int i = 0; i < len; i++) {// 读取子节byte b = oos.readByte();String str = (String) oos.readObject();// 将子节对应的编码放入HashMapmapCode.put(str, b);}// 读取数据int byteArrayLength = oos.readInt();// 根据长度定义子节数组byte[] bs = new byte[byteArrayLength];// 将流中的剩余子节度如数组oos.read(bs);return bs;} catch (Exception ef) {ef.printStackTrace();}return null;}/** * 将子节数组中的子节按照十进制-->二进制,得到一个01串 * * @param bs * 子节数组 * @return 返回生成的01串 */public String byte2String(byte[] bs) {String s = "";// 获取最后一个子节，为补0的个数int num = bs[bs.length - 1];// 由于最后一个子节是保存的倒数第二个子节补0的个数// 不需要转成二进制for (int j = 0; j < bs.length - 1; j++) {byte b = bs[j];String str = Integer.toBinaryString(b);if (b < 0) {str = str.substring(24);} else {// 当子节为正数的时候，转成的01串长度可能小于8，应该补0补成8位int len = 8 - str.length();for (int i = 0; i < len; i++) {str = "0" + str;}}s += str;}// 截取掉最后补的0s = s.substring(0, s.length() - num);return s;}/** * 根据码表将01串还原成原始子节 * * @param str * 01串 * @return 返回装有原始子节的数组 */public ArrayList<Byte> string2SrcBytes(String str) {// 由于不知道根据01串会转成多少个子节，就采用动态数组或者链表ArrayList<Byte> list = new ArrayList<Byte>();// 要和码表匹配的字符串，是从str上获取来的String s = "";// 遍历字符串，取得一个字符for (int i = 0; i < str.length(); i++) {s += str.charAt(i);// 如果包含这个keyif (mapCode.containsKey(s)) {// 得到该编码对应的子节byte b = mapCode.get(s);// 将子节保存起来list.add(b);s = "";}}return list;}/** * 将子节数组写到文件，即为解压后的文件 * * @param list * 解压出的原始子节数组 * @param path * 解压后的文件 */public void write2File(ArrayList<Byte> list, String path) {try {FileOutputStream fos = new FileOutputStream(path);BufferedOutputStream bos = new BufferedOutputStream(fos);for (byte b : list) {bos.write(b);}bos.flush();bos.close();fos.close();} catch (Exception ef) {ef.printStackTrace();}}}
上一篇：String类的基本用法
请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
技术博客集 - 网站简介：
前后端技术：
后端基于Hyperf2.1框架开发,前端使用Bootstrap可视化布局系统生成
网站主要作用：
1.编程技术分享及讨论交流，内置聊天系统;
2.测试交流框架问题，比如：Hyperf、Laravel、TP、beego;
3.本站数据是基于大数据采集等爬虫技术为基础助力分享知识，如有侵权请发邮件到站长邮箱，站长会尽快处理;
4.站长邮箱：[email protected];
文章归档
文章标签
友情链接
