哈夫曼編碼
根據(jù)數(shù)據(jù)出現(xiàn)的頻率對數(shù)據(jù)進行編碼，從而壓縮原始數(shù)據(jù)。

例如對于一個文本文件，其中各種字符出現(xiàn)的次數(shù)如下：

a : 10
b : 20
c : 40
d : 80
可以將每種字符轉(zhuǎn)換成二進制編碼，例如將 a 轉(zhuǎn)換為 00，b 轉(zhuǎn)換為 01，c 轉(zhuǎn)換為 10，d 轉(zhuǎn)換為 11。這是最簡單的一種編碼方式，沒有考慮各個字符的權(quán)值（出現(xiàn)頻率）。而哈夫曼編碼采用了貪心策略，使出現(xiàn)頻率最高的字符的編碼最短，從而保證整體的編碼長度最短。

首先生成一顆哈夫曼樹，每次生成過程中選取頻率最少的兩個節(jié)點，生成一個新節(jié)點作為它們的父節(jié)點，并且新節(jié)點的頻率為兩個節(jié)點的和。選取頻率最少的原因是，生成過程使得先選取的節(jié)點位于樹的更低層，那么需要的編碼長度更長，頻率更少可以使得總編碼長度更少。

import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue;public class hufman { private class Node implements Comparable<Node>{char ch;int frequency;boolean isleaf;Node left;Node right;public Node(char a,int f) {ch=a;frequency=f;isleaf=true;}public Node(Node left,Node right,int frequency) {this.left=left;this.right=right;this.frequency=frequency;}@Overridepublic int compareTo(Node o) {// TODO Auto-generated method stubreturn this.frequency-o.frequency;} }public Map<Character,String> encode(Map<Character,Integer> frquencyChar){PriorityQueue<Node> p=new PriorityQueue();for(char c:frquencyChar.keySet()) {p.add(new Node(c,frquencyChar.get(c)));}while(p.size()!=1) {Node n1= p.poll();Node n2= p.poll();p.add(new Node(n1,n2,n1.frequency+n2.frequency));}return Encode(p.poll());}public Map<Character,String> Encode(Node root){Map<Character,String> m=new HashMap();Encode(root,"",m);return m;}public void Encode(Node node,String a,Map<Character,String> m) {while(node.isleaf) {m.put(node.ch, a);return;}Encode(node.left,a+"0",m);Encode(node.right,a+"1",m);}} man.java import java.util.HashMap; import java.util.Map;public class Teat {public static void main(String[] args) {// TODO Auto-generated method stubMap <Character,Integer> frquencyChar=new HashMap();frquencyChar.put('a', 1);frquencyChar.put('c', 19);frquencyChar.put('2', 13);frquencyChar.put('5', 14);hufman a=new hufman();Map<Character,String> b=a.encode(frquencyChar);for(char m:b.keySet()) {System.out.println(m+b.get(m));}}}

這是一個大根堆，所以重寫了Node 對象中的compareTo 函數(shù)， 繼承 Comparable 接口，
首先將字符與權(quán)重加入一個map中，我理解的是構(gòu)建小根堆，這樣每次都是最小的現(xiàn)出來。相加構(gòu)成節(jié)點這個樣子。
重寫了函數(shù)之后，compare這個函數(shù)我覺得是》0 就要交換，<0 不交換，this.fre-o.fre>0 說明后來者小，進行交換。

PriorityQueue <Integer> maxHeap = new PriorityQueue<Integer>( new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {// TODO Auto-generated method stubreturn o2.compareTo(o1);}});

還可以 通過這個樣子重寫進行大根堆 小根堆變換。
https://blog.csdn.net/liou825/article/details/21322403
https://blog.csdn.net/zcf1784266476/article/details/68961473

總結(jié)

以上是生活随笔為你收集整理的哈夫曼编码之大根堆小根堆揭西县的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。