Huffman树的建立
基本介绍
- 给定n个权值作为n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)
- 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
赫夫曼树几个重要概念
- 路径和路径长度:在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
- 结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值.则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
- 树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树
- WPL最小的就是赫夫曼树
赫夫曼树创建思路
给你一个数列{13,7,8,3,29,6,1}，要求转成一颗赫夫曼树.构成赫夫曼树的步骤:
- 从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小再次排序．不断重复1-2-3-4 的步骤，直到数列中，所有的数据都被处理,就得到一颗赫夫曼树
public class HuffmanTree {
public static void main(String[] args) {
int[] arr={13,7,8,3,29,6,1};
Node huffmanTree=createHuffmanTree(arr);
preOrder(huffmanTree);
}
//前序遍历
public static void preOrder(Node root){
if(root!=null)
root.preOrder();
else
System.out.println("空树，不能遍历");
}
public static Node createHuffmanTree(int[] arr){
List<Node> nodes=new ArrayList<>();
for(int value:arr)
nodes.add(new Node(value));
while(nodes.size()>1)
{
Collections.sort(nodes);
Node leftNode=nodes.get(0);
Node rightNode=nodes.get(1);
Node parentNode=new Node(leftNode.value+rightNode.value);
parentNode.left=leftNode;
parentNode.right=rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
}
return nodes.get(0);
}
}
class Node implements Comparable<Node>{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//前序遍历
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{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node node) {
return this.value-node.value;
}
}
赫夫曼编解码
public class HuffmanCode {
static Map<Byte,String> huffmanCodes=new HashMap<>();
static StringBuilder stringBuilder=new StringBuilder();
public static void main(String[] args) {
String content="asdds astkk nhb sgacsw aevsbd";
byte[] contentBytes=content.getBytes();
byte[] huffmanCodeBytes=huffmanZip(contentBytes);
System.out.println(Arrays.toString(huffmanCodeBytes));
byte[] sourceBytes=decode(huffmanCodes,huffmanCodeBytes);
System.out.println(new String(sourceBytes));
}
/**
* 将一个byte转化为一个二进制的字符串
* @param flag 表示是否需要补高位，如果是true表示需要补高位，如果是false表示不补，如果是最后一个字节无需补高位
* @param b
* @return
*/
public static String byteToBitString(boolean flag,byte b){
int temp=b;
if(flag)
temp|=256;
String str=Integer.toBinaryString(temp);
if(flag)
return str.substring(str.length()-8);
else
return str;
}
/**
* 解码
* @param huffmanCodes
* @param huffmanBytes
* @return
*/
public static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
StringBuilder stringBuilder=new StringBuilder();
for(int i=0;i<huffmanBytes.length;i++){
byte b=huffmanBytes[i];
boolean flag=(i==huffmanBytes.length-1);
stringBuilder.append(byteToBitString(!flag,b));
}
Map<String,Byte> map=new HashMap<>();
for(Map.Entry<Byte,String>entry:huffmanCodes.entrySet()){
map.put(entry.getValue(),entry.getKey());
}
List<Byte> list=new ArrayList<>();
for(int i=0;i<stringBuilder.length();){
int count=1;
boolean flag=true;
Byte b=null;
while(flag){
String key=stringBuilder.substring(i,i+count);
b=map.get(key);
if(b==null)
count++;
else
flag=false;
}
list.add(b);
i+=count;
}
byte[] b=new byte[list.size()];
for(int i=0;i<b.length;i++)
b[i]=list.get(i);
return b;
}
//封装流程
private static byte[] huffmanZip(byte[] bytes){
List<Node> nodes=getNodes(bytes);
Node huffmanTreeRoot=createHuffmanTree(nodes);
Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
/**
* 一、将传入的字节数组转为List<Node>集合
* @param bytes 传入的字节数组
* @return List<Node>集合
*/
private static List<Node> getNodes(byte[] bytes){
ArrayList<Node> nodes=new ArrayList<>();
Map<Byte,Integer> counts=new HashMap<>();
for(byte b:bytes) {
Integer count=counts.get(b);
if(count==null)
counts.put(b,1);
else
counts.put(b,count+1);
}
for(Byte b:counts.keySet()){
Node node=new Node(b,counts.get(b));
nodes.add(node);
}
return nodes;
}
/**
* 二、构建Huffman树
* @param nodes Node集合
* @return 根节点
*/
public static Node createHuffmanTree(List<Node> nodes){
while(nodes.size()>1)
{
Collections.sort(nodes);
Node leftNode=nodes.get(0);
Node rightNode=nodes.get(1);
Node parentNode=new Node(null,leftNode.weight+rightNode.weight);
parentNode.left=leftNode;
parentNode.right=rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
}
return nodes.get(0);
}
//重载
public static Map<Byte,String> getCodes(Node root){
if(root==null)
return null;
else{
getCodes(root.left,"0",stringBuilder);
getCodes(root.right,"1",stringBuilder);
}
return huffmanCodes;
}
/**
* 三、获取Huffman编码表
* @param node 节点
* @param code 路径：左子节点为0，右子节点为1
* @param 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
huffmanCodes.put(node.data,stringBuilder2.toString());
}
}
/**
* 四、将原始数组转化为压缩后的字节数组
* @param bytes 原始字节数组
* @param huffmanCodes 编码表
* @return 压缩后的字节数组
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
StringBuilder stringBuilder=new StringBuilder();
for(byte b:bytes){
stringBuilder.append(huffmanCodes.get(b));
}
int len=(stringBuilder.length()+7)/8;
byte[] huffmanCodeBytes=new byte[len];
int index=0;
for(int i=0;i<stringBuilder.length();i+=8){
String strByte;
if(i+8>stringBuilder.length())
strByte=stringBuilder.substring(i);
else
strByte=stringBuilder.substring(i,i+8);
huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
index++;
}
return huffmanCodeBytes;
}
}
