哈弗曼树

2017年9月30日 9点热度 0条评论 来源: xiao__oaix

给定一篇文章,求它的哈夫曼编码。

  • 首先,统计词频(一般用HashMap来做);
  • 随后,创建一个优先队列,将TreeNode按词频由小到大出队;
    • 入队方法用offer(),出队方法用poll();
    • 他们与add/remove不同,队满或队空时不会抛异常而是返回false。
    • TreeNode,应包含词频、Char、左右儿子四个信息;
  • 从优先队列中出队两个元素,创建一个新的TreeNode对象,词频(权重)为两个儿子节点的和,char置为null,并offer到队列中;
  • 重复,直到队只有一个元素,将这个元素出队,他就是树根;

  • 遍历这棵树,就可以求出哈夫曼编码:
  • 树形结构需要递归求解,因此问题变更为求以node为根的子树的哈夫曼编码;

    
    node==null,return 0;

    
    node.char==null 求左右儿子即可,否则求左右儿子+当前深度*当前权重。


参考代码,转自牛客网:

package August;

import java.util.*;
public class Huffman {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String s = input.nextLine();
            int result = hafuman(s);
            System.out.println(result);
        }
        input.close();
    }
 
    public static int hafuman(String s) {
        char[] chars = s.toCharArray();
        //hash表存放每个字符和出现的次数
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (hash.containsKey(chars[i])) {
                hash.put(chars[i], hash.get(chars[i]) + 1);
            } else {
                hash.put(chars[i], 1);
            }
        }
        //优先队列(最小推),每次能得到weigh最小的node
        Queue<TreeNode> q = new PriorityQueue<>(hash.size(), new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return Integer.compare(o1.weight, o2.weight);
            }
        });
        for (Map.Entry<Character, Integer> entry : hash.entrySet()) {
            q.offer(new TreeNode(entry.getValue(), entry.getKey()));
        }
        while (q.size() > 1) {
            //弹出两个最小的,合并为一个node
            TreeNode left = q.poll();
            TreeNode right = q.poll();
            TreeNode father = new TreeNode(left.weight + right.weight);
            father.left = left;
            father.right = right;
            q.offer(father);
        }
        TreeNode root = q.poll();
        //计算长度     
        return valLength(root, 0);
    }
 
    public static int valLength(TreeNode node, int depth) {
        if (node == null) return 0;//仅计算ch有值的
        return (node.ch == null ? 0 : node.weight) * depth + valLength(node.left, depth + 1) + valLength(node.right, depth + 1);
    }
 
    static class TreeNode {
        int weight;//权重,出现次数
        Character ch;//如果是初始字符,则ch为字符,如果是合并的,则为null
        TreeNode left;
        TreeNode right;
 
        public TreeNode(int weight) {
            this.weight = weight;
        }
 
        public TreeNode(int weight, Character ch) {
            this.weight = weight;
            this.ch = ch;
        }
    }
}

    原文作者:xiao__oaix
    原文地址: https://blog.csdn.net/xiao__oaix/article/details/78143685
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。