哈夫曼树

哈夫曼树

Scroll Down

什么是哈夫曼树

给定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;
    }
}

示例结果:

捕获.PNG

支付宝 微信