赫夫曼编码

大家好，欢迎来到IT知识分享网。

1、基本介绍

1. 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
2. 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
3. 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间
4. 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

2、原理剖析

2.1、通信领域中信息的处理方式1-定长编码

2.1、通信领域中信息的处理方式2-变长编码

i like like like java do you like a java // 共40个字符(包括空格)

2.3、通信领域中信息的处理方式3-赫夫曼编码

i like like like java do you like a java // 共40个字符(包括空格)

//根据赫夫曼树，给各个字符 //规定编码 ， 向左的路径为0 //向右的路径为1 ， 编码如下:

000000001110

长度为 ： 133 说明: 原来长度是 359 , 压缩了 (359-133) / 359 = 62.9% 此编码满足前缀编码,
即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性

注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的, 比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:

3、最佳实践-数据压缩(创建赫夫曼树)

 public static Node HefumanTree(List<Node> nodes){ 
    while (nodes.size()>1){ 
    /* 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树 取出根节点权值最小的两颗二叉树 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树*/ Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node node=new Node(null,leftNode.weight+rightNode.weight); node.left=leftNode; node.right=rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(node); } Node result=nodes.get(0); return result; } 

class Node implements Comparable<Node>{ 
    public Byte data; public int weight; public Node left; public Node right; public Node(Byte data, int weight) { 
    this.data = data; this.weight = weight; } public void preOrder(){ 
    System.out.println(this); if (this.left!=null){ 
    this.left.preOrder(); } if (this.right!=null){ 
    this.right.preOrder(); } } @Override public String toString() { 
    return "Node{" + "data=" + data + ", weight=" + weight + '}'; } @Override public int compareTo(Node o) { 
    return this.weight-o.weight; } } 

我们已经生成了 赫夫曼树, 下面我们继续完成任务

1. 生成赫夫曼树对应的赫夫曼编码 , 如下表:=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
2. 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将”i like like like java do you like a java” 字符串生成对应的编码数据, 形式如下.000000011100

 / * 压缩字符码编码 * @param str * @return */ private static byte[] zipCode(byte[] bytes) { 
    Map<Byte,Integer> map=new HashMap<>(); for (byte aByte : bytes) { 
    Integer count = map.get(aByte); if (count==null){ 
    map.put(aByte,1); }else{ 
    map.put(aByte,count+1); } } List<Node> nodes=new ArrayList<>(); for (Byte aByte : map.keySet()) { 
    Node node=new Node(aByte,map.get(aByte)); nodes.add(node); } Node node = HefumanTree(nodes); preOrder(node); getCodes(node); System.out.println("map："+huffMap.toString()); StringBuilder sb=new StringBuilder(); for (byte aByte : bytes) { 
    String s = huffMap.get(aByte); sb.append(s); } System.out.println(sb.toString()); byte[] huffByte=zip(sb.toString()); System.out.println(Arrays.toString(huffByte)); return huffByte; } 

4、最佳实践-数据解压(使用赫夫曼编码解码)

 / * 解压字符 * @param bytes * @return */ private static byte[] deHuffMancode(byte[] bytes,Map<Byte,String> huffMap) { 
    //map转换，key为编码，value为 Map<String,Byte> map=new HashMap<>(); Set<Map.Entry<Byte, String>> entries = huffMap.entrySet(); for (Map.Entry<Byte, String> entry : entries) { 
    map.put(entry.getValue(),entry.getKey()); } //byte按位补码256 int temp=0; StringBuilder stringBuilder=new StringBuilder(); int index=0; for (byte aByte : bytes) { 
    temp=aByte; if (index!=bytes.length-1){ 
    temp=temp|256; String sb = Integer.toBinaryString(temp); stringBuilder.append(sb.substring(sb.length()-8)); }else{ 
    temp=temp; String sb = Integer.toBinaryString(temp); stringBuilder.append(sb); } index++; } byte[] decode = decode(stringBuilder.toString(), map); return decode; } 

 private static byte[] decode(String decode,Map<String,Byte> map) { 
    List<Byte> list = new ArrayList<>(); StringBuilder stringBuilder=new StringBuilder(); for (int i=0;i<decode.length();){ 
    int count=1; while (true){ 
    String str=decode.substring(i,i+count); if (map.get(str)!=null){ 
    byte b=map.get(str); list.add(b); stringBuilder.append((char)b); break; } count++; } i=count+i; count=1; } System.out.println(stringBuilder.toString()); byte[] b = new byte[list.size()]; for (int i = 0; i < b.length; i++) { 
    b[i] = list.get(i); } return b; } 

5、最佳实践-文件压缩

 public static void zipFile(String srcFile,String dstFile) { 
    //输出流写入数据 OutputStream os = null; ObjectOutputStream oos = null; try { 
    //输入流读入文件数据 InputStream is = new FileInputStream(srcFile); //读取文件 byte[] b = new byte[is.available()]; //读 is.read(b); is.close(); //获取压缩后的字节 byte[] huffmanBytes = zipCode(b); //写入目标目录 os = new FileOutputStream(dstFile); //写出文件 oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); //写入输出流 oos.writeObject(huffMap); } catch (Exception e) { 
    e.printStackTrace(); } finally { 
    try { 
    oos.close(); os.close(); } catch (IOException e) { 
    e.printStackTrace(); } } } 

6、最佳实践-文件压缩

 @SuppressWarnings("unchecked") public static void unZipFile(String zipFile,String dstFile) { 
    //输入流读取文件 InputStream is = null; //对象输入流读取并生成对象 ObjectInputStream ois = null; //文件输出流 OutputStream os = null; try { 
    is = new FileInputStream(zipFile); ois = new ObjectInputStream(is); //字符码 byte[] b = (byte[]) ois.readObject(); //编码规则 Map<Byte, String> codes = (Map<Byte, String>) ois.readObject(); //解压 byte[] bytes = deHuffMancode(b,codes); os = new FileOutputStream(dstFile); //输出 os.write(bytes); } catch (Exception e) { 
    e.printStackTrace(); } finally { 
    try { 
    ois.close(); is.close(); os.close(); } catch (IOException e) { 
    // TODO Auto-generated catch block e.printStackTrace(); } } } 

7、赫夫曼编码压缩文件注意事项

8、代码整合

package com.qf.hefumancode; import java.io.*; import java.util.*; import java.util.zip.ZipInputStream; public class HefumanCodeDemo { 
    static Map<Byte,String> huffMap=new HashMap<>(); static StringBuilder stringBuilder=new StringBuilder(); public static void main(String[] args) { 
    String str="i like like like java do you like a java"; byte[] by = str.getBytes(); byte[] bytes = zipCode(by); deHuffMancode(bytes,huffMap); String src="d:/808a2991_E_7269db77.png"; String src1="d:/aa.png"; String dst="d:/dst.zip"; // zipFile(src,dst); unZipFile(dst,src1); } public static void zipFile(String srcFile,String dstFile) { 
    //输出流写入数据 OutputStream os = null; ObjectOutputStream oos = null; try { 
    //输入流读入文件数据 InputStream is = new FileInputStream(srcFile); //读取文件 byte[] b = new byte[is.available()]; //读 is.read(b); is.close(); //获取压缩后的字节 byte[] huffmanBytes = zipCode(b); //写入目标目录 os = new FileOutputStream(dstFile); //写出文件 oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); //写入输出流 oos.writeObject(huffMap); } catch (Exception e) { 
    e.printStackTrace(); } finally { 
    try { 
    oos.close(); os.close(); } catch (IOException e) { 
    e.printStackTrace(); } } } @SuppressWarnings("unchecked") public static void unZipFile(String zipFile,String dstFile) { 
    //输入流读取文件 InputStream is = null; //对象输入流读取并生成对象 ObjectInputStream ois = null; //文件输出流 OutputStream os = null; try { 
    is = new FileInputStream(zipFile); ois = new ObjectInputStream(is); //字符码 byte[] b = (byte[]) ois.readObject(); //编码规则 Map<Byte, String> codes = (Map<Byte, String>) ois.readObject(); //解压 byte[] bytes = deHuffMancode(b,codes); os = new FileOutputStream(dstFile); //输出 os.write(bytes); } catch (Exception e) { 
    e.printStackTrace(); } finally { 
    try { 
    ois.close(); is.close(); os.close(); } catch (IOException e) { 
    // TODO Auto-generated catch block e.printStackTrace(); } } } private static byte[] decode(String decode,Map<String,Byte> map) { 
    List<Byte> list = new ArrayList<>(); StringBuilder stringBuilder=new StringBuilder(); for (int i=0;i<decode.length();){ 
    int count=1; while (true){ 
    String str=decode.substring(i,i+count); if (map.get(str)!=null){ 
    byte b=map.get(str); list.add(b); stringBuilder.append((char)b); break; } count++; } i=count+i; count=1; } System.out.println(stringBuilder.toString()); byte[] b = new byte[list.size()]; for (int i = 0; i < b.length; i++) { 
    b[i] = list.get(i); } return b; } / * 压缩字符码编码 * @param str * @return */ private static byte[] zipCode(byte[] bytes) { 
    Map<Byte,Integer> map=new HashMap<>(); for (byte aByte : bytes) { 
    Integer count = map.get(aByte); if (count==null){ 
    map.put(aByte,1); }else{ 
    map.put(aByte,count+1); } } List<Node> nodes=new ArrayList<>(); for (Byte aByte : map.keySet()) { 
    Node node=new Node(aByte,map.get(aByte)); nodes.add(node); } Node node = HefumanTree(nodes); preOrder(node); getCodes(node); System.out.println("map："+huffMap.toString()); StringBuilder sb=new StringBuilder(); for (byte aByte : bytes) { 
    String s = huffMap.get(aByte); sb.append(s); } System.out.println(sb.toString()); byte[] huffByte=zip(sb.toString()); System.out.println(Arrays.toString(huffByte)); return huffByte; } / * 解压字符 * @param bytes * @return */ private static byte[] deHuffMancode(byte[] bytes,Map<Byte,String> huffMap) { 
    //map转换，key为编码，value为 Map<String,Byte> map=new HashMap<>(); Set<Map.Entry<Byte, String>> entries = huffMap.entrySet(); for (Map.Entry<Byte, String> entry : entries) { 
    map.put(entry.getValue(),entry.getKey()); } //byte按位补码256 int temp=0; StringBuilder stringBuilder=new StringBuilder(); int index=0; for (byte aByte : bytes) { 
    temp=aByte; if (index!=bytes.length-1){ 
    temp=temp|256; String sb = Integer.toBinaryString(temp); stringBuilder.append(sb.substring(sb.length()-8)); }else{ 
    temp=temp; String sb = Integer.toBinaryString(temp); stringBuilder.append(sb); } index++; } byte[] decode = decode(stringBuilder.toString(), map); return decode; } private static byte[] zip(String str) { 
    //判断字符的长度 int length = str.length(); //按照8位截取 int size=0; if (length%8==0){ 
    size=length/8; }else { 
    size=length/8+1; } byte[] byteArray=new byte[size]; int index=0; for (int i = 0; i <length; i=i+8) { 
    //lemgth 3 length 13 byte code=0; if (i+8<length){ 
    code=(byte)Integer.parseInt(str.substring(i,i+8),2); }else{ 
    code=(byte)Integer.parseInt(str.substring(i),2); } byteArray[index]=code; index++; } return byteArray; } public static void getCodes(Node node){ 
    getCodes(node,"",stringBuilder); } public static void getCodes(Node node,String code,StringBuilder stringBuilder){ 
    StringBuilder stringBuilder2=new StringBuilder(stringBuilder); stringBuilder2.append(code); if (node!=null){ 
    if (node.data==null){ 
    //向左递归 getCodes(node.left,"0",stringBuilder2); //向右递归 getCodes(node.right,"1",stringBuilder2); }else{ 
    huffMap.put(node.data,stringBuilder2.toString()); } } } public static Node HefumanTree(List<Node> nodes){ 
    while (nodes.size()>1){ 
    /* 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树 取出根节点权值最小的两颗二叉树 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树*/ Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node node=new Node(null,leftNode.weight+rightNode.weight); node.left=leftNode; node.right=rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(node); } Node result=nodes.get(0); return result; } public static void preOrder(Node root){ 
    root.preOrder(); } } class Node implements Comparable<Node>{ 
    public Byte data; public int weight; public Node left; public Node right; public Node(Byte data, int weight) { 
    this.data = data; this.weight = weight; } public void preOrder(){ 
    System.out.println(this); if (this.left!=null){ 
    this.left.preOrder(); } if (this.right!=null){ 
    this.right.preOrder(); } } @Override public String toString() { 
    return "Node{" + "data=" + data + ", weight=" + weight + '}'; } @Override public int compareTo(Node o) { 
    return this.weight-o.weight; } }