??英文字母大小寫總共就52個(gè)，一本英文書籍幾十上百萬的英文單詞都是由這52個(gè)字符排列組合而成，不難看出這52個(gè)字符肯定是大量重復(fù)了。
??一本中文小說幾百萬字，也都是由常用的幾千個(gè)漢字組合而成。如果是一本玄幻小說，那么在相近的章節(jié)中一定大量的重復(fù)出現(xiàn)人名，地名，功法境界，以及主角在一段時(shí)間內(nèi)修煉的功法。至于主角名字更是貫穿整本小說一定大量重復(fù)。還有作者的寫作風(fēng)格是保持一致的，因此文章有時(shí)候在描寫一些緊張氛圍或者描寫反面人物可能會(huì)使用相似的句式和詞語來表達(dá)，這些可能會(huì)造成很高的重復(fù)率。
??圖片是由像素點(diǎn)組成的而每個(gè)像素點(diǎn)是由rgb：三元素組成。這些都是由0~255的數(shù)字表示，因此可以將圖片看作一堆數(shù)字。一張小的圖片的像素點(diǎn)至少也有幾千，如果是高清圖片估計(jì)有上百萬個(gè)像素點(diǎn)。每一個(gè)像素點(diǎn)都是三個(gè)0~255的數(shù)字，組成圖片的像素點(diǎn)一定存在大量的重復(fù)數(shù)字；一些圖片有很大范圍的背景色這種情況下，數(shù)字更是會(huì)發(fā)生大量的重復(fù)。
??不管是中文，英文還是圖片的像素點(diǎn)，如果數(shù)據(jù)量很大那么肯定存在大量重復(fù)字符。一個(gè)英文字符是8bit，一個(gè)中文字符使用UTF-8編碼會(huì)占3個(gè)字節(jié)24bit；如果要壓縮數(shù)據(jù)，從字符編碼角度考慮應(yīng)該怎么去壓縮呢？可以思考三秒(PS:就這幾段句子已經(jīng)重復(fù)出現(xiàn)重復(fù)了很多次了)
??現(xiàn)在有一段英文文本AAAAAAAAABBCCCDDCCCBBBAAAAABB,這段文本A出現(xiàn)14次，B出現(xiàn)7次，C出現(xiàn)6次，D出現(xiàn)2次。正常編碼，這個(gè)文本所占bit：（14+7+6+2）* 8 = 232bit。
重慶分公司
重慶分公司
A的編碼是：0100 0001B的編碼是：0100 0010C的編碼是：0100 0011D的編碼是：0100 0100??我們可以思考下，A,B,C,D這四個(gè)字符在這段文本中需要用8bit來表示嗎？是不是可以用更少的字符來表示這幾個(gè)字符？重新給這4個(gè)字符編碼：
A->1B->10C->11D->100??重新編碼之后，這段文本所占bit：14 * 1 + 2 * 7 + 2 * 6 + 2 * 3 = 46bit；重新編碼之后的文本大小只占原文本的20%左右。在這個(gè)例子中，A編碼最短，BC次之，D最長(zhǎng)我們是按照字母順序來編碼的嗎？顯然不是的，在給字符編碼時(shí)，是按照字符使用的頻率來決定該如何編碼。如果使用次數(shù)多也就是頻率高的就盡量用短編碼，使用次數(shù)少頻率低就用長(zhǎng)編碼。這樣才能盡可能的降低壓縮后的字符長(zhǎng)度。Huffman編碼在對(duì)字符重新編碼時(shí)的指導(dǎo)思想就是這樣的。
??我們繼續(xù)上面的例子，將A,B,C,D按照上面的方法編碼并創(chuàng)建一個(gè)對(duì)照表。
| A | B | C | D |
|---|---|---|---|
| 1 | 10 | 11 | 100 |
??根據(jù)重新編碼后的字符，上面英文文本的二進(jìn)制編碼是 ：111111111101011111110010011110111111101010111111010，根據(jù)這段編碼我們?cè)撊绾谓獯a，將壓縮后的二進(jìn)制碼還原成字符？
??根據(jù)上面的編碼我們可以看出，在解壓時(shí)沒法恢復(fù)源文本了。最開始的9個(gè)1，可以有多種解析方式：可以4個(gè)C 一個(gè)A，這種情況下A位置變化都有5種。還可以有3C，3A的組合。。。。等等其他組合根本沒有辦法確定這9個(gè)1該如何編碼。
??那該如何編碼呢？既要按照字符使用頻率來編碼，又要在解壓時(shí)能夠復(fù)原文本。這時(shí)候Huffman樹就隆重出場(chǎng)了Huffman樹的構(gòu)建很簡(jiǎn)單，但是構(gòu)建過程非常巧妙。Huffman樹的構(gòu)建規(guī)則：
??這是我自己總結(jié)的構(gòu)造Huffman樹的規(guī)則，看不懂太正常，在我第一次接觸Huffman樹估計(jì)也是看不懂。下面會(huì)用上面的例子圖解如何構(gòu)建一顆Huffman樹。
??最開始有 A,B,C,D四個(gè)節(jié)點(diǎn)，經(jīng)過排序之后由較小的2個(gè)節(jié)點(diǎn)生成新的節(jié)點(diǎn)。因此選擇C,D來生成新節(jié)點(diǎn)：8；生成新節(jié)點(diǎn)之后C,D節(jié)點(diǎn)不再參與后續(xù)的過程。
??參與第二次構(gòu)建Huffman樹的新節(jié)點(diǎn)：8，B(7)，A(14),這3個(gè)節(jié)點(diǎn)再比較使用次數(shù)： 7< 8< 14 ；因此使用 B（7），8節(jié)點(diǎn)來構(gòu)建新節(jié)點(diǎn)：15；
??第三次參與構(gòu)建新節(jié)點(diǎn)的的節(jié)點(diǎn)： 15，A（14）；直接用這2個(gè)節(jié)點(diǎn)生成root節(jié)點(diǎn)；Huffman樹構(gòu)建結(jié)束。
??可以看出來，使用頻率最高的A，從根節(jié)點(diǎn)到A的路徑是最短的，而使用頻率最小的D，從根節(jié)點(diǎn)到D的距離是最長(zhǎng)的。這路勁長(zhǎng)短正好對(duì)應(yīng)了使用頻率的高低。如果一個(gè)節(jié)點(diǎn)鏈接left節(jié)點(diǎn)用 0 表示；鏈接 right 節(jié)點(diǎn)用 1表示；（反過來也可以）那么從root節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑就可以用01字符串來表示了；
??A,B,C,D構(gòu)建的Huffman樹形成了新的編碼:
| A | B | C | D |
|---|---|---|---|
| 1 | 01 | 001 | 000 |
??英文：AAAAAAAAABBCCCDDCCCBBBAAAAABB經(jīng)過構(gòu)建Huffman樹重新編碼之后的壓縮文本是：1111111110101001001001000000001001001010101111110101一共52字符；只有原文的52/232 = 22%左右大?。?/font>
??回到關(guān)鍵問題，如何解壓呢？
??也很簡(jiǎn)單，在解壓時(shí)只需要對(duì)照Huffman樹來解壓就行。從root節(jié)點(diǎn)往下找，找到葉子節(jié)點(diǎn)就找到了對(duì)應(yīng)的字符。用這種方式順序讀取二進(jìn)制碼對(duì)照Huffman樹就可以解析文本了。
代碼部分//Huffman樹節(jié)點(diǎn)
class HMNode{int val;
HMNode left;
HMNode right;
boolean leaf;//是否葉子節(jié)點(diǎn)
char str;
public HMNode(int val){this.val = val;
}
public HMNode(int val,char str){this.val = val;
leaf = true;
this.str = str;
}
@Override
public String toString() {return "val="+val+";char="+(str=='\0' ? '_':str);
}
}
//統(tǒng)計(jì)文本各個(gè)字符使用頻率
public Mapcount(String text){Mapmap = new HashMap<>();
for (int i = 0; ichar t = text.charAt(i);
if(map.containsKey(t)){map.compute(t,(key,val)->val+1);
}else{map.computeIfAbsent(t,key->1);
}
}
return map;
}
//構(gòu)建Huffman樹
public HMNode buildHuffManTree(String text){Mapmap = count(text);
Listnodes = new ArrayList<>(map.size()<<1);
map.forEach((key,val)->nodes.add(new HMNode(val,key)));
nodes.sort((n1, n2)->n1.val-n2.val);
int start = 0;
while(nodes.size()-2>=start){HMNode root = new HMNode(nodes.get(start).val+nodes.get(start+1).val);
root.left = nodes.get(start);
root.right = nodes.get(start+1);
nodes.add(root);
nodes.sort((n1, n2)->n1.val-n2.val);
start+=2;
}
return nodes.get(start);
} @Test
public void test(){String text = "aaabbbbbccccccddddee";
HMNode root =buildHuffManTree(text);
List nodes = new ArrayList();
nodes.add(root);
print(nodes);
}
public void print(Listnodes){Listc = new ArrayList<>();
System.out.println("\n");
for (HMNode hmNode : nodes){if(hmNode.left != null)c.add(hmNode.left);
if(hmNode.right != null)c.add(hmNode.right);
System.out.print(hmNode+ "\t");
}
System.out.println("\n");
if(!c.isEmpty())print(c);
}
=========================================res=================================================
//結(jié)果:char=_ ===>表示新生成的節(jié)點(diǎn)
val=20;char=_
val=9;char=_ val=11;char=_
val=4;char=d val=5;char=b val=5;char=_ val=6;char=c
val=2;char=e val=3;char=a
//左分支 + 0 ； 右分支 + 1
public void huffmanCode(HMNode root,MaphuffmanCode,String code){if(root.leaf){huffmanCode.put(code,root.str);
return;
}
if(root.left != null){huffmanCode(root.left,huffmanCode,code+"0");
}
if(root.right != null){huffmanCode(root.right,huffmanCode,code+"1");
}
}
@Test
public void test(){String text = "aaabbbbbccccccddddee";
Mapcount = count(text);
HMNode root =buildHuffManTree(text);
Mapcode = new HashMap<>();
huffmanCode(root,code,"");
code.forEach((key,val)->System.out.println(val+" ->"+key));
}
=========================================res=================================================
d ->00
c ->11
b ->01
e ->100
a ->101
后續(xù)：Huffman 二進(jìn)制碼以及文本壓縮與解壓
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
