哈夫曼编码

您所在的位置：网站首页 › 哈夫曼编码压缩率会是负的吗 › 哈夫曼编码

哈夫曼编码

2024-07-04 14:57| 来源: 网络整理| 查看: 265

哈夫曼编码哈夫曼编码基本介绍实现思路特点总结最佳实践数据压缩及解压文件的压缩与解压哈夫曼编码压缩文件注意事项基本介绍

（1）哈夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，属于一种程序算法。

（2）哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一。

（3）哈夫曼编码广泛地用于数据文件压缩，其压缩率通常在20%~90%之间。

（4）哈夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码。

实现思路

（1）统计字符串各个字符出现的次数。

（2）按照上面字符出现的次数构建一棵哈夫曼树，次数作为权值。

（3）根据哈夫曼树，给各个字符规定编码（前缀编码），向左的路径为0，向右的路径为1。这样，每个字符都有独一无二的编码，而且出现次数越多的字符，编码越短。

特点总结

（1）此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性。

（2）生成的哈夫曼树根据排序方法不同，也可能不太一样，这样对应的哈夫曼编码也不完全一样，但是wpl是一样的，都是最小的。

最佳实践数据压缩及解压

（1）构建结点类

class Node implements Comparable { Byte data; // 存放字符本身的 ASCII 码 int weight; // 存放权值（字符出现的次数） Node left; Node right; public Node(Byte data， int weight) { this.data = data; this.weight = weight; } // 前序遍历 public void perOrder() { System.out.println(this); if (this.left != null) { this.left.perOrder(); } if (this.right != null) { this.right.perOrder(); } } @Override public int compareTo(Node o) { return this.weight - o.weight; } @Override public String toString() { return "Node{" + "data=" + this.data + "， weight=" + this.weight + "}"; } }

（2）构建HuffmanCode类，里面有个主方法

public class HuffmanCode { public static void main(String[] args) { //主方法 } }

（3）在主方法中将字符串转为byte数组

String content = "yorick yur bei yu Android java Hello World yorick你好"; byte[] contentBytes = content.getBytes();

（4）将byte数组的每个元素转化为二叉树结点，可以统计字符串各个字符出现的次数，作为权重。

构建将byte数组的每个元素转化为二叉树结点的方法

private static List str2Node(byte[] bytes) { // 存储结点的数据和权值 Map count = new HashMap(); for (Byte b : bytes) { // 当 key 存在时。value+1，key不存在时新建key，并另value=1 counrge(b， 1， Integer::sum); } List nodes = new ArrayList(); for (Map.Entry entry : count.entrySet()) { nodes.add(new Node(entry.getKey()， entry.getValue())); } return nodes; }

主方法调用

List nodes = str2Node(contentBytes);

（5）生成哈夫曼树

根据结点生成哈夫曼树的方法

private static Node buildHuffmanTree(List nodes) { while (nodes.size() > 1) { Collections.sort(nodes); Node left = nodes.get(0); Node right = nodes.get(1); nodes.remove(0); nodes.remove(0); Node pare = new Node(null， left.weight + right.weight); pare.left = left; pare.right = right; nodes.add(pare); } return nodes.get(0); }

主方法调用

Node root = buildHuffmanTree(nodes);

（6）根据哈夫曼树生成哈夫曼编码表

在主方法中声明两个静态属性

// 供递归入口使用，存储过程值 static StringBuilder stringBuilder = new StringBuilder(); // 存储递归结果 static Map huffmanCode = new HashMap();

通过递归获取哈夫曼树中非叶子结点对应的路径字符串

/** 递归获得哈夫曼编码 * @param node 结点 * @param str 三种情况：”“、”0“、”1“ * @param stringBuilder 可变字符串，记录路径 */ private static void getCodes(Node node， String str， StringBuilder stringBuilder) { if (node == null) return; StringBuilder sb = new StringBuilder(stringBuilder); sb.append(str); // 判断node是否为叶子结点 if (node.data == null) { // 向左递归 getCodes(node.left， "0"， sb); // 向右递归 getCodes(node.right， "1"， sb); } else { huffmanCode.put(node.data， String.valueOf(sb)); } }

为了主方法调用方便，重载方法

private static Map tree2code(Node root) { getCodes(root， ""， stringBuilder); return huffmanCode; }

在主方法中调用

Map huffmanCode = tree2code(root); // 哈夫曼编码表：32->01 97->100 100->11000 117->11001 101->1110 118->11011 105->101 121->11010 106->0010 107->1111 108->000 111->0011

（7）根据编码表对字符进行压缩

压缩方法private static byte[] zip(byte[] bytes， Map huffmanCode) { StringBuilder codes = new StringBuilder(); for (Byte b : bytes) { codes.append(huffmanCode.get(b)); } int length; if (codes.length() % 8 == 0) { length = codes.length() / 8; } else { length = codes.length() / 8 + 1; } byte[] huffmanCodeBytes = new byte[length]; int index = 0; for (int i = 0; i < codes.length(); i += 8) { String huffmanCodeStr; if (i + 8 < codes.length()) { huffmanCodeStr = codes.substring(i， i + 8); } else { huffmanCodeStr = codes.substring(i); } huffmanCodeBytes[index] = (byte) Integer.parseInt(huffmanCodeStr， 2); index++; } return huffmanCodeBytes; } 为了便于调用，将压缩方法封装 public static byte[] huffmanZip(byte[] contentBytes) { // 将字符串的每个字符转化为二叉树结点 List nodes = str2Node(contentBytes); // 生成哈夫曼树 Node root = buildHuffmanTree(nodes); //perOder(buildHuffmanTree(nodes)); // 根据哈夫曼树生成哈夫曼编码表 Map huffmanCode = tree2code(root); System.out.print("哈夫曼编码表："); for (Map.Entry entry : huffmanCode.entrySet()) { System.out.print(entry.getKey() + "->" + entry.getValue() + " "); } System.out.println(); return zip(contentBytes， huffmanCode); } 在主方法中调用 byte[] huffmanCodeBytes = huffmanZip(contentBytes);

输出压缩后内容

System.out.println("压缩后内容：" + Arrays.toString(huffmanCodeBytes)); // 压缩后内容：[-88， -65， -56， -65， -56， -65， -55， 77， -57， 6， -24， -14， -117， -4， -60， -90， 28]

（8）解压内容

将单个byte转二进制字符串

/** 单个byte转二进制字符串 * @param b 单个byte * @param flag 是否需要补高位 * @return 对应的二进制补码的字符串 */ private static String byte2BitString(byte b， boolean flag) { int temp = b; if (flag) { // 两个位都为0时，结果才为0 256 -> 10000000 temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } }

解压

public static byte[] decode(Map huffmanCode， byte[] huffmanCodeBytes) { StringBuilder bitString = new StringBuilder(); for (int i = 0; i < huffmanCodeBytes.length; i++) { // 判断是否位最后一个字节 boolean flag = i == (huffmanCodeBytes.length - 1); bitString.append(byte2BitString(huffmanCodeBytes[i]， !flag)); } //System.out.println(bitString); Map map = new HashMap(); // 反转map for (Map.Entry entry : huffmanCode.entrySet()) { map.put(entry.getValue()， entry.getKey()); } List list = new ArrayList(); for (int i = 0; i < bitString.length(); ) { Byte b = null; int count = 1; boolean flag = true; while (flag) { b = map.get(bitString.substring(i， i + count)); if (b == null) { count++; } else { flag = false; } } list.add(b); i += count; } byte[] bytes = new byte[list.size()]; for (int j = 0; j < list.size(); j++) { bytes[j] = list.get(j); } return bytes; } 在主方法中调用byte[] resBytes = decode(huffmanCode， huffmanCodeBytes); 输出解压后内容 System.out.println("解压后内容：" + new String(resBytes)); 文件的压缩与解压文件压缩方法// 文件压缩 public static void zipFile(String src， String dst) throws IOException { // 输入 FileInputStream is = new FileInputStream(src); byte[] b = new byte[is.available()]; is.read(b); byte[] huffmanBytes = huffmanZip(b); // 输出 OutputStream os = new FileOutputStream(dst); ObjectOutputStream oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); oos.writeObject(huffmanCodes); // 关闭IO is.close(); oos.close(); os.close(); } 文件解压方法 // 文件解压 public static void unZipFile(String src， String dst) throws IOException， ClassNotFoundException { // 输入 FileInputStream is = new FileInputStream(src); ObjectInputStream ois = new ObjectInputStream(is); byte[] huffmanBytes = (byte[]) ois.readObject(); Map huffmanCodes = (Map) ois.readObject(); byte[] bytes = decode(huffmanCodes， huffmanBytes); // 输出 OutputStream os = new FileOutputStream(dst); os.write(bytes); os.close(); ois.close(); is.close(); } 主方法要添加异常签名public static void main(String[] args) throws IOException， ClassNotFoundException { zipFile("E://yy.bmp"， "E://yy.bmp.huf"); System.out.println("压缩完成"); unZipFile("E://yy.bmp.huf"，"E://yy_1.bmp"); System.out.println("解压完成"); } 哈夫曼编码压缩文件注意事项

（1）如果文件本身就是经过压缩处理的，那么使用哈夫曼编码再压缩效率不会有明显变化，比如视频，ppt等等文件

（2）哈夫曼编码是按字节来处理的，因此可以处理所有的文件（二进制文件、文本文件）

（3）如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显。

【本文地址】

哈夫曼编码

哈夫曼编码

今日新闻

推荐新闻