快速求解霍夫曼编码树的带权路径长度

布满荆棘的人生 2021-11-17 13:06 284阅读 0赞

## 一、简介 ##

霍夫曼编码被广泛的用在文本压缩编码中，但在求解霍夫曼树的WPL长度时其实不必真的构造出一棵霍夫曼树再去实际求解，在实际oj和测试时时间也不允许，求解WPL可以基于如下定义快速求解：  
**WPL = 所有叶子节点的带权路径长度之和 = 霍夫曼树中所有非叶节点的权值之和**  
证明如图：  
图片转载自https://blog.csdn.net/hchild1/article/details/50933972  
![转载自][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70]  
如果是用第一个等式去做的化需要先构造出一棵霍夫曼树，再去求解所有叶子节点的带权路径，很麻烦！但是第二个等式就很容易了。

## 二、思路 ##

将所有权重存入一个一个小顶堆中（可以直接使用Java中定义好的优先级队列），然后从队列中每次取出两个元素，将其和累加到初始化为0的WPL上，并再存入队列中，当队列中只有一个元素时退出循环！

## 三、Java实现 ##

以[POJ1521][]为例！

import java.util.*;
    
    public class Main2 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str;
            while (!(str = sc.next()).equals("END")) {
                int n = str.length();
                int asciiLen = n * 8;
                Map<Character, Integer> memo = new HashMap<Character, Integer>();
                for (char ch : str.toCharArray()) {
                    if (memo.containsKey(ch)) {
                        memo.put(ch, memo.get(ch) + 1);
                    } else {
                        memo.put(ch, 1);
                    }
                }
                Queue<Integer> pqueue = new PriorityQueue<Integer>();
                pqueue.addAll(memo.values());
                int prefixLen = 0;
                if (pqueue.size() == 1) {
    	            //只有一个节点，WPL = 1 * 该节点权重
                    prefixLen = pqueue.poll();
                } else {
                    while (pqueue.size() > 1) {
                        int sum = pqueue.poll() + pqueue.poll();
                        prefixLen += sum;
                        pqueue.add(sum);
                    }
                }
                System.out.printf("%d %d %.1f\n", asciiLen, prefixLen, 1.0 * asciiLen / prefixLen);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70]: /images/20211116/1d5f9f15959142a5b63f23f1063994b2.png
[POJ1521]: http://poj.org/problem?id=1521