什么是哈夫曼树
给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
简介
在计算机数据处理中,哈夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。
例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1L1+W2L2+W3L3+...+WnLn),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
基本术语
1. 路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
2. 结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
**3. ** 树的带权路径长度'
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。
构造
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
实现代码:
import java.util.*;
public class Huffman {
public static void main(String[] args) {
int[] arr = {10, 5, 1, 2, 9, 15, 6, 3, 4};
long start = System.currentTimeMillis();
System.out.println("没优化前:");
TreeNode root = CreateHuffman(arr);
System.out.println("前序遍历结果:");
PreTraver(root);
long end = System.currentTimeMillis();
System.out.println("共耗时:" + (end - start) + "ms");
System.out.println("----------------------------------");
start = System.currentTimeMillis();
System.out.println("优化后:");
TreeNode rootByPQ = creatHuffmanByPriorityQueue(arr);
System.out.println("前序遍历结果:");
PreTraver(rootByPQ);
end = System.currentTimeMillis();
System.out.println("共耗时:" + (end - start) + "ms");
}
/**
* 未经过优化
* @param arr
* @return
*/
public static TreeNode CreateHuffman(int[] arr) {
List<TreeNode> treeNodes = new ArrayList<TreeNode>();
for (int i = 0; i < arr.length; i++) {
treeNodes.add(new TreeNode(arr[i], null, null));
}
//如果treenodes长度为1,则哈夫曼树创建好了,只剩下根结点
while (treeNodes.size() > 1) {
//使用Collections集合对treenodes进行排序
Collections.sort(treeNodes, new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.getNo() - o2.getNo();
}
});
//排序之后,取出头两个进行创建结点
TreeNode left = treeNodes.get(0);
TreeNode right = treeNodes.get(1);
TreeNode parent = new TreeNode(left.getNo() + right.getNo(), null, null);
//根结点创建好之后,将左右结点接上去,并将根结点加入集合
parent.setLeft(left);
parent.setRight(right);
treeNodes.add(parent);
//之后将头两个节点删除
treeNodes.remove(left);
treeNodes.remove(right);
}
return treeNodes.get(0);
}
/**
* 经过优先队列优化
* @param arr
* @return
*/
public static TreeNode creatHuffmanByPriorityQueue(int[] arr) {
//构造结点依次加入优先队列
Queue<TreeNode> pq = new PriorityQueue<TreeNode>(new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.getNo() - o2.getNo();
}
});
for (int i = 0; i < arr.length; i++) {
pq.offer(new TreeNode(arr[i], null, null));
}
//当队列中只剩一个元素时,Huffman树就创建完成了
while(pq.size() > 1){
//从优先队列中取出值最小的两个结点
TreeNode left = pq.poll();
TreeNode right = pq.poll();
//创建父结点
TreeNode parent = new TreeNode(left.getNo() + right.getNo(),null,null);
//为父结点添加左右孩子
parent.setLeft(left);
parent.setRight(right);
//加入优先队列
pq.offer(parent);
}
return pq.poll();
}
public static void PreTraver(TreeNode root) {
if (root != null) {
System.out.print(root.getNo() + " ");
PreTraver(root.getLeft());
PreTraver(root.getRight());
}
}
}
/**
* Huffman树的结点
*/
class TreeNode {
private int no; //编号
private TreeNode left; //左结点
private TreeNode right; //右节点
public TreeNode(int no, TreeNode left, TreeNode right) {
this.no = no;
this.left = left;
this.right = right;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
评论区