太原制作网站的公司市场推广方案模板

哈夫曼编码

        哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

哈夫曼编码，主要目的是根据使用频率来最大化节省字符（编码）的存储空间。

哈夫曼编码和解码代码实现

package com.gykalc.huffmancode;
import java.io.*;
import java.util.*;
import java.util.function.Function;/*** 哈夫曼编码：* 首先，编码分为定长编码和不定长编码* 定长编码：例如我们要发送 “i like like like java do you like a java” 这个字符串时* 我们不对其进行处理，每个字符都是一个字节，那么就需要40个字节来传输该数据* 不定长编码：我们还是传输上述字符串，我们给每一个字符定义一个固定的编码* 例如：i: 10、空格: 0、l: 101、a：1* 那么我们要传输的数据为：10010110...，但是这种方式虽然可以减少传输的数据长度，但是也有问题* 问题在于，我们解码时，这种不定长前缀导致我们不知道10代表的是“i”还是代表“a空格”，会出现多义* 这个时候就可以使用哈夫曼编码，它是不定长的前缀编码，它不会出现上面的多义问题。* 哈夫曼编码步骤：*  1、统计出要传输的字符串每个字符出现的次数，将其作为节点的权重值*  2、构建哈夫曼树，节点中存储着每个字符的Byte数据和权重值*  3、计算出每个字符的节点路径，向左为0，向右为1，就可以得到不会重复的前缀编码*  4、根据计算的节点路径，就可以将字符串进行编码，获取到编码后的数据** 哈夫曼解码步骤：*  1、首先将编码后的字节数组，转换成二进制字符串*  2、根据哈夫曼编码表，逆向一个解码表*  3、根据解码表对二进制字符串进行解码，生成原始字符串*/
public class HuffmanCode {// 哈夫曼树的节点private static Node huffmanTreeRoot;// 哈夫曼编码后的二进制字节字符串private static String huffmanBytesString;// 哈夫曼编码mapprivate static Map<Byte, String> huffmanCodesMap = new HashMap<>();// 压缩后的byte字节数组private static byte[] huffmanCodeByte;// 哈夫曼解码表private static Map<String, Byte> huffmanDecodeMap = new HashMap<>();// 哈夫曼的压缩率private static double compressRatio;public static void main(String[] args) {String filePath = "C:\\Users\\24792\\Desktop\\虚拟机服务器.txt";String zipPath = filePath.substring(0, filePath.lastIndexOf(".")) + ".zip";zipFile(filePath, zipPath);unZipFile(zipPath, "C:\\Users\\24792\\Desktop\\虚拟机服务器1.txt");}/*** 压缩文件* @param filePath* @param zipPath*/private static void zipFile(String filePath, String zipPath) {// 读取一个文件try(FileInputStream fis = new FileInputStream(new File(filePath));BufferedInputStream bis = new BufferedInputStream(fis);FileOutputStream fos = new FileOutputStream(new File(zipPath));BufferedOutputStream bos = new BufferedOutputStream(fos);) {// 返回文件的大小int length = bis.available();byte[] bytes = new byte[length];// 读取文件数据到bytes中int readLen = bis.read(bytes);if (length != readLen) {throw new Exception("文件读取有问题！");}else {zip(bytes);System.out.println("压缩率为：%" + compressRatio * 100);// 将压缩后的字节写入文件中bos.write(huffmanCodeByte);}}catch (Exception e) {e.printStackTrace();}}private static void unZipFile(String zipPath, String unZipPath) {// 读取一个文件try(FileInputStream fis = new FileInputStream(new File(zipPath));BufferedInputStream bis = new BufferedInputStream(fis);FileOutputStream fos = new FileOutputStream(new File(unZipPath));BufferedOutputStream bos = new BufferedOutputStream(fos);) {// 返回文件的大小int length = bis.available();byte[] bytes = new byte[length];// 读取文件数据到bytes中int readLen = bis.read(bytes);if (length != readLen) {throw new Exception("文件读取有问题！");}else {byte[] unZipBytes = unZip(bytes);fos.write(unZipBytes);}}catch (Exception e) {e.printStackTrace();}}private static Node buildHaffmanTree(byte[] bytes) {Map<Byte, Integer> countMap = new HashMap<>();// 统计出每个字符出现的次数，存入countMap中for (Byte b : bytes) {Integer count = countMap.get(b);if (count == null) {countMap.put(b, 1);} else {countMap.put(b, count + 1);}}// 遍历countMap，构建Node的ListList<Node> nodeList = new ArrayList<>();for (Map.Entry<Byte, Integer> entry : countMap.entrySet()) {nodeList.add(new Node(entry.getKey(), entry.getValue()));}// 开始构建哈夫曼树while (nodeList.size() > 1) {// 首先进行排序Collections.sort(nodeList);// 拿到两个最小的节点，当作左右子节点，来构建一个新的二叉树Node leftNode = nodeList.get(0);Node rightNode = nodeList.get(1);Node parentNode = new Node(null, leftNode.getWeight() + rightNode.getWeight());parentNode.setLeftNode(leftNode);parentNode.setRightNode(rightNode);nodeList.remove(leftNode);nodeList.remove(rightNode);nodeList.add(parentNode);}huffmanTreeRoot = nodeList.get(0);return nodeList.get(0);}/*** 根据哈夫曼树，生成哈夫曼编码表*/private static void getCodesByHuffmanTree(Node root, String path, StringBuilder stringBuilder) {StringBuilder sb = new StringBuilder(stringBuilder);sb.append(path);if (root != null) {if (root.getData() == null) { // 说明当前节点不是叶子节点getCodesByHuffmanTree(root.getLeftNode(), "0", sb);getCodesByHuffmanTree(root.getRightNode(), "1", sb);} else { // 说明当前节点是叶子节点，就可以加入map中huffmanCodesMap.put(root.getData(), sb.toString());}}}private static void getCodesByHuffmanTree(Node root) {getCodesByHuffmanTree(root, "", new StringBuilder());}/*** 将原byte数组根据哈夫曼编码表进行压缩，返回的是压缩后的byte数组* @param oldBytes* @param huffmanCodesMap* @return*/private static byte[] zip(byte[] oldBytes, Map<Byte, String> huffmanCodesMap) {StringBuilder sb = new StringBuilder();// 生成哈夫曼编码的字符串for (byte b : oldBytes) {String strCode = huffmanCodesMap.get(b);sb.append(strCode);}huffmanBytesString = sb.toString();// 计算出要转换的字节数组大小int sbLength = sb.length();int byteLength = (sbLength + 7) / 8 + 1;byte[] zipByte = new byte[byteLength];int byteIndex = 0;// 将该字符串转换成字节数组，该字节数组最后一位存储最后一个字符串的长度for (int i = 0; i < sbLength; i += 8) {if (i + 8 >= sbLength) { // 不足8个字符了zipByte[byteIndex] = (byte)Integer.parseInt(sb.substring(i), 2);// 最后一个byte记录前一个的长度，为之后解码使用zipByte[byteIndex + 1] = (byte)sb.substring(i).length();}else {zipByte[byteIndex] = (byte)Integer.parseInt(sb.substring(i, i + 8), 2);}byteIndex++;}// zipByte就是压缩后的byte数组huffmanCodeByte = zipByte;// 这里我们可以统计一下压缩率：(原数组长度-压缩后的长度) / 原长度compressRatio = (double)(oldBytes.length - zipByte.length) / oldBytes.length;return zipByte;}/*** 为了调用方便，封装一下* @param oldBytes* @return*/private static byte[] zip(byte[] oldBytes) {// 构建哈夫曼树buildHaffmanTree(oldBytes);// 根据哈夫曼树，生成哈夫曼编码getCodesByHuffmanTree(huffmanTreeRoot);// 最后根据哈夫曼编码生成压缩后的字节数组return zip(oldBytes, huffmanCodesMap);}/*** 根据哈夫曼编码表，对数据进行解压* @param zipBytes* @param huffmanCodesMap* @return*/private static byte[] unZip(byte[] zipBytes, Map<Byte, String> huffmanCodesMap) {// 第一步：将压缩的字节数组，转换成二进制字符串String binaryString = bytesToString(zipBytes);// 第二步：将哈夫曼编码表，转换成哈夫曼解码表for (Map.Entry<Byte, String> entry: huffmanCodesMap.entrySet()) {huffmanDecodeMap.put(entry.getValue(), entry.getKey());}List<Byte> byteList = new ArrayList<>();// 第三步：遍历二进制字符串，每个字符串进行匹配StringBuilder pipeiSb = new StringBuilder();for (int i = 0; i < binaryString.length(); i++) {pipeiSb.append(binaryString.charAt(i));Byte pipeiByte = huffmanDecodeMap.get(pipeiSb.toString());if (pipeiByte != null) { // 说明匹配到了// 将匹配字符串置空pipeiSb = new StringBuilder();byteList.add(pipeiByte);}}byte[] bytes = new byte[byteList.size()];for (int i = 0; i < byteList.size(); i++) {bytes[i] = byteList.get(i);}return bytes;}private static byte[] unZip(byte[] zipBytes) {return unZip(zipBytes, huffmanCodesMap);}/*** 将哈夫曼字节数组转换二进制字符串* @param bytes* @return*/private static String bytesToString(byte[] bytes) {StringBuilder sb = new StringBuilder();int bytesLength = bytes.length;for (int i = 0; i < bytesLength - 1; i++) {// 将bite转换成intint charInt = (int)bytes[i];// 当b是负数时，这里不变，当是正数时，这里用来补足正数的位数charInt |= 256;String binaryString = Integer.toBinaryString(charInt);if (i == bytesLength - 2) { // 就是最后一个压缩的字节，因为bytes的最后一个字节我们存储的是最后一个压缩字节的长度sb.append(binaryString.substring(binaryString.length() - bytes[bytesLength - 1]));}else {sb.append(binaryString.substring(binaryString.length() - 8));}}return sb.toString();}/*** 前序遍历** @param root*/private static void preNode(Node root) {if (root != null) {root.preOrder();} else {System.out.println("该树为空，不能遍历");}}
}class Node implements Comparable<Node> {// 每个字节的数据private Byte data;// 每个字节出现的次数，也就是权重值private int weight;// 左子节点private Node leftNode;// 右子节点private Node rightNode;/*** 前序遍历*/public void preOrder() {System.out.println(this);if (this.leftNode != null) {this.leftNode.preOrder();}if (this.rightNode != null) {this.rightNode.preOrder();}}public Byte getData() {return data;}public void setData(Byte data) {this.data = data;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}public Node getLeftNode() {return leftNode;}public void setLeftNode(Node leftNode) {this.leftNode = leftNode;}public Node getRightNode() {return rightNode;}public void setRightNode(Node rightNode) {this.rightNode = rightNode;}public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {return this.weight - o.weight;}@Overridepublic String toString() {return "Node{" +"data=" + data +", weight=" + weight +'}';}
}