贪心算法 - 哈夫曼编码 Huffman
轉載地址 ?: ? http://blog.csdn.net/xuefeng0707/article/details/7844834
哈夫曼編碼：
一種字符編碼方式，常用于數據文件壓縮。壓縮率通常在20%~90%。
主要思想：
采取可變長編碼方式，對文件中出現次數多的字符采取比較短的編碼，對于出現次數少的字符采取比較長的編碼，可以有效地減小總的編碼長度。
例如，在英文中，e的出現頻率最高，z的出現頻率最低，所以可以用最短的編碼來表示e，用最長的編碼表示z。
例子：
一個文件包含100 000個字符，且僅含有a,b,c,d,e,f六個字符，那么可以用3位bit來編碼這六個字符，稱之為定長碼。
那么采取定長碼共需要的位數為 3* 100 000 = 600 000位。
這六個字符出現的頻率如圖所示，a最多，f最少。因此如果采取圖中所示的變長碼，所需要的位數為：
(45*1 + 13*3 + 12 * 3 + 16*3 + 9*4 + 5*4) * 1000 = 224 000。
可以看出壓縮了25%，a的編碼長度最短，為一位，f的編碼長度最長，為4位。
前綴碼：
當讀取文件時，對于定長碼文件，已經知道了每個字符的編碼長度，所以只需按部就班的一個一個的讀取字符即可；
對于變長碼文件，各個字符的編碼長度不一，因此需要小心設計各個字符的編碼，一面混淆。
比如，如果a的編碼為0，b的編碼為01，c的編碼為1，那么解碼的時候如果遇到‘001’，則既可以解碼成‘aac’，也可以解碼成‘ab’。
因為b的編碼中包含了a的編碼，也就是a的編碼是b的編碼的前綴。
所以，變長碼編碼的設計，每個字符的編碼都不能是其他字符編碼的前綴，這種方式稱之為前綴碼。
可以用二叉樹來表示每個字符的編碼，以左為0，以右為1，這樣每個葉子節點的路徑均不同，也都不會稱為其他葉子節點的前綴。
這樣每個葉子節點的路徑，就是每個字符的編碼。
圖中形成的編碼與表格中的有些差異，但是各個字符編碼的長度都相同，這是左子樹和右子樹的區別，但是對編碼長度沒有影響。
貪心算法代碼實現：
/*** Huffman code* @author xuefeng**/ public class Huffman {/*** ignore exception* @param cs : characters* @param freqs : frequency of each character*/public static void huffman(char[] cs, double[] freqs) {int n = cs.length;MinHeap<Code> heap = new MinHeap<Code>(cs.length);Code[] codes = new Code[n];for (int i = 0; i < n; i++) {Code c = new Code(cs[i], freqs[i]);heap.add(c); // 以最小堆來每次取出頻率最小的兩個codes[i] = c; // 保存所有的葉子節點}Code c, c1, c2;while (heap.size() > 1) {c1 = heap.removeMin();c2 = heap.removeMin();// 取出兩個最小的c = new Code('\0', c1.freq + c2.freq);c.left = c1;c.right = c2;c1.parent = c;c2.parent = c;heap.add(c); // 組合成一個新的節點，并放入堆中，繼續比較System.out.println(c1.val + "+" + c2.val + " : " + c1.freq + "+" + c2.freq + " = " + c.freq);}c = heap.removeMin(); // 二叉樹根節點StringBuffer sb;for (int i = 0; i < n; i++) {c = codes[i]; // 從每個葉子節點，向上追溯，直到根節點，確定每個字符的編碼sb = new StringBuffer();while (c != null) {if (c.parent != null) {if (c == c.parent.left) {sb.insert(0, 0); // 如果是左邊的，編碼取1} else {sb.insert(0, 1); // 如果是右邊的，編碼取1}}c = c.parent;}System.out.println(codes[i].val + " : " + sb.toString());}}public static void main(String[] args) {char[] cs = { 'a', 'b', 'c', 'd', 'e', 'f' };double[] freqs = { 45, 13, 12, 16, 9, 5 };// %huffman(cs, freqs);// http://zh.wikipedia.org/wiki/%E5%AD%97%E6%AF%8D%E9%A2%91%E7%8E%87char[] cs2 = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k','l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w','x', 'y', 'z' };double[] freqs2 = { 8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015,6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929,0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974,0.074 };huffman(cs2, freqs2);} }class Code implements Comparable<Code> {public char val;public double freq;public Code left, right, parent;public Code(char val, double freq) {this.val = val;this.freq = freq;}@Overridepublic int compareTo(Code c) {double d = freq - c.freq;return d > 0 ? 1 : (d == 0 ? 0 : -1);} }
總結
以上是生活随笔為你收集整理的贪心算法 - 哈夫曼编码 Huffman的全部內容，希望文章能夠幫你解決所遇到的問題。
