美文网首页
深度透析哈夫曼树(Huffman)

深度透析哈夫曼树(Huffman)

作者: jqboooo | 来源:发表于2018-12-17 14:34 被阅读0次

在我们接近高科技的时代,离不开高效率的算法,比如:微信做的图片压缩技术、RAR、ZIP,就是利用哈夫曼树算法来处理。

1、首先理解几个概念

1.哈夫曼树概念:带权路径长度(WPL)最小的树称做为哈夫曼树。

2.路径长度:从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支树目称做路径长度

看图:

1.png 2.png 3.png

2、哈夫曼树是如何构成的(集合必须是有序,每次相加之前都要进行排序,采用左小右大原则),先看一下步骤:

4.png 5.png
注意:每次把数字放上去之前,都要先排序,左小右大原则,然后在进行2组数字相加,得到父结点。
6.png

3、Huffman编码(集合必须是有序的)

哈夫曼研究这种最优的树目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。

比如:“BADCADFEED” 要网络传输给别人,显然用二进制的数字(0或1)来表示是很自然的想法,那我们用这六个字母ABCDEF二进制来表示

7.png 8.png

结点上的数字,表示代表出现的次数。比如:A 上的27,表示出现了27次,也就是路径出现27次。

4、代码实现哈夫曼树

import android.support.annotation.NonNull;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

/**
 * author: bobo
 * create time: 2018/12/14 9:34 PM
 */
public class HuffmanTree<T> {

    TreeNode<T> root;

    /**
     * 构建哈夫曼树
     *
     * @param list
     */
    public void createHuffmanTree(ArrayList<TreeNode<T>> list) {
        if (list == null || list.isEmpty()) {
            return;
        }
        while (list.size() > 1) {
            Collections.sort(list);
            TreeNode left = list.get(list.size() - 1);
            TreeNode right = list.get(list.size() - 2);
            TreeNode parent = new TreeNode("P", left.weight + right.weight);
            parent.leftChild = left;
            left.parent = parent;
            parent.rightChild = right;
            right.parent = parent;
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        root = list.get(0);
    }

    /**
     * 一层一层取出数据,通过队列入队的方式存储形式
     *
     * @param root
     */
    public void showHuffman(TreeNode root) {
        LinkedList<TreeNode> list = new LinkedList<>();
        //入队
        list.offer(root);
        while (!list.isEmpty()) {
            //出对
            TreeNode node = list.pop();
            if (!node.data.equals("P")) { //如果是创建的结点P,就不打印了
                System.out.println(node.weight + " = " + node.data);
            }
            //左子树不为空,则入队
            if (node.leftChild != null) {
                list.offer(node.leftChild);
            }
            //右子树不为空,则入队
            if (node.rightChild != null) {
                list.offer(node.rightChild);
            }
        }
    }

    /**
     * 获取哈夫曼编码
     *
     * @param node
     */
    public String getHuffmanCode(TreeNode node) {
        TreeNode tNode = node;
        //定义一个栈来排序用
        Stack<String> stack = new Stack<>();
        while (tNode != null && tNode.parent != null) {
            //left 0  right 1
            if (tNode.parent.leftChild == tNode) {
                stack.push("0");
            } else if (tNode.parent.rightChild == tNode) {
                stack.push("1");
            }
            tNode = tNode.parent;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    /**
     * 结点,和二叉树一样
     *
     * @param <T>
     */
    public static class TreeNode<T> implements Comparable<TreeNode<T>> {
        T data;
        TreeNode<T> leftChild;
        TreeNode<T> rightChild;
        TreeNode<T> parent;
        //权重
        int weight;

        public TreeNode(T data, int weight) {
            this.data = data;
            this.weight = weight;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }

        @Override
        public int compareTo(@NonNull TreeNode<T> o) {
            if (this.weight > o.weight) {
                return -1;
            } else if (this.weight < o.weight) {
                return 1;
            }
            return 0;
        }
    }

}

5、测试

@Test
public void testHuffmanTree(){
    //添加结点数据
    ArrayList<HuffmanTree.TreeNode> list = new ArrayList<>();
    HuffmanTree.TreeNode<String> node = new HuffmanTree.TreeNode("good", 50);
    list.add(node);
    list.add(new HuffmanTree.TreeNode("morning", 10));

    HuffmanTree.TreeNode<String> node2 =new HuffmanTree.TreeNode("afternoon", 20);
    list.add(node2);
    list.add(new HuffmanTree.TreeNode("hello", 110));
    list.add(new HuffmanTree.TreeNode("hi", 200));

    HuffmanTree tree = new HuffmanTree();
    tree.createHuffmanTree(list);
    tree.showHuffman(tree.root);
    System.out.println("tree.getHuffmanCode(node); = " + tree.getHuffmanCode(node));
    System.out.println("tree.getHuffmanCode(node2) = " + tree.getHuffmanCode(node2));;
}

6、测试结果

200 = hi
110 = hello
50 = good
10 = morning
20 = afternoon
tree.getHuffmanCode(node); = 001
tree.getHuffmanCode(node2) = 0001

7、结束

以上对Huffman树的理解。

相关文章

  • 深度透析哈夫曼树(Huffman)

    在我们接近高科技的时代,离不开高效率的算法,比如:微信做的图片压缩技术、RAR、ZIP,就是利用哈夫曼树算法来处理...

  • 《恋上数据结构与算法一》笔记(十八)哈夫曼树

    目录 哈夫曼编码(Huffman Coding) 哈夫曼树 构建哈夫曼树 构建哈夫曼编码 一 哈夫曼编码(Huff...

  • 《数据结构与算法》总结(七)哈夫曼树

    目录 哈夫曼编码(Huffman Coding) 哈夫曼树 构建哈夫曼树 构建哈夫曼编码 一 哈夫曼编码(Huff...

  • Huffman树及Huffman编码

    Huffman树及Huffman编码 一.实验目的 掌握哈夫曼树的构造算法、哈夫曼编码原理。 二.实验要求与内容 ...

  • 算法解析:哈夫曼(huffman)压缩算法

    前言 本篇将介绍哈夫曼压缩算法(Huffman compression) 哈夫曼压缩算法(Huffman comp...

  • 哈夫曼树&哈夫曼编码

    引入 哈夫曼、赫夫曼、霍夫曼都说的是——Huffman哈夫曼树和哈夫曼编码到底解决啥问题呢?先看两个常经常用来解释...

  • 哈夫曼树(huffman)

    学完了huffman树,讲一下自己对它的理解 先上效果图: 怎么样 是不是感觉蛮有意思的。 huffman树遵循二...

  • 构造哈夫曼树

    构造huffman树的算法: 算法思想:哈夫曼算法采用自底向上逐步合并的方法,构造哈夫曼树:步骤1)构造n颗单叶结...

  • 哈夫曼树(Huffman Code)

    定义 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,则称之为最优二叉树,也就是哈夫曼...

  • Huffman Coding(哈夫曼树)

    哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。给出现频率高的字符较短的编码...

网友评论

      本文标题:深度透析哈夫曼树(Huffman)

      本文链接:https://www.haomeiwen.com/subject/naaqkqtx.html