目錄

關(guān)于編碼的兩個(gè)概念：

1 前綴編碼

1.1 前綴編碼概念

1.2 前綴編碼實(shí)例分析（簡(jiǎn)潔易懂）

1.3 前綴編碼作用 

2 哈夫曼編碼

2.1 哈夫曼編碼概念

2.2 哈夫曼編碼的兩條性質(zhì)

2.3 哈夫曼編碼的兩條性質(zhì)的證明 （摘取自嚴(yán)蔚敏老師的教材）

關(guān)于編碼的兩個(gè)概念：

1 前綴編碼

1.1 前綴編碼概念

前綴編碼：如果在一個(gè)編碼方案中，任何一個(gè)編碼都不是其他任何編碼的前綴（最左子串），則稱該編碼是前綴編碼。

1.2 前綴編碼實(shí)例分析（簡(jiǎn)潔易懂）

舉個(gè)簡(jiǎn)單的例子，給出下面三種編碼方案:

分析：

1. 如上圖，不等長(zhǎng)編碼方案1是前綴編碼；分析如下：在不等長(zhǎng)編碼方案1中，a,b,c,d為四個(gè)字符，其對(duì)應(yīng)編碼0，10，110，111中，任意一個(gè)編碼（四個(gè)里面隨便選）都不是其他任何編碼的前綴，比如選擇a的編碼0進(jìn)行比對(duì)，你會(huì)發(fā)現(xiàn) 10，110，111都不以0為前綴（都不以0開頭）。 
2. 如上圖，不等長(zhǎng)編碼方案2不是前綴編碼，分析如下，四個(gè)編碼中，隨便選一個(gè)，如果選0，會(huì)發(fā)現(xiàn)01，010都是以0為前綴，所以不符合前綴編碼的定義，分析結(jié)束。

不知道大家有沒有隱約有種意識(shí)，等長(zhǎng)編碼一定是前綴編碼！

例如兩位編碼，00，01，10，11就是，同理，三位、四位...n位。

1.3 前綴編碼作用 

前綴編碼可以保證對(duì)壓縮文件進(jìn)行解碼時(shí)不產(chǎn)生二義性，確保正確解碼。

2 哈夫曼編碼

2.1 哈夫曼編碼概念

2、哈夫曼編碼：對(duì)于一顆具有n個(gè)葉子的哈夫曼樹，若對(duì)樹中的每個(gè)左分支賦予0，右分支賦予1，則從根到每個(gè)葉子的路徑上，各分支的賦值分別構(gòu)成一個(gè)二進(jìn)制串，該二進(jìn)制串就成為哈夫曼編碼。

哈夫曼編碼的主要思想：在進(jìn)行數(shù)據(jù)壓縮時(shí)，為了使壓縮后的數(shù)據(jù)文件盡可能短，可以采用不定長(zhǎng)編碼。其基本思想是：

未出現(xiàn)次數(shù)較多的字符編以較短的編碼，為確保對(duì)數(shù)據(jù)文件進(jìn)行有效的壓縮和對(duì)壓縮文件進(jìn)行正確的解碼，可以利用哈夫曼樹來設(shè)計(jì)二進(jìn)制編碼。

2.2 哈夫曼編碼的兩條性質(zhì)

哈夫曼樹滿足兩條性質(zhì)：

• 性質(zhì)1  哈夫曼樹是前綴編碼。
• 性質(zhì)2  哈夫曼樹是最有前綴編碼。 對(duì)于包含n個(gè)數(shù)據(jù)字符的文件，分別以它們出現(xiàn)的次數(shù)為權(quán)值構(gòu)造哈夫曼樹，則利用該樹對(duì)應(yīng)的哈夫曼編碼對(duì)文件進(jìn)行編碼，能使該文件壓縮后對(duì)應(yīng)的二進(jìn)制文件的長(zhǎng)度最短。

2.3 哈夫曼編碼的兩條性質(zhì)的證明 （摘取自嚴(yán)蔚敏老師的教材）

關(guān)于此兩條性質(zhì)的證明如下圖（圖片參考自嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)教材）：