無損壓縮的定義

　　所謂無損壓縮格式，顧名思義，就是毫無損失地將聲音信號進行壓縮的音頻格式。常見的像MP3、WMA等格式都是有損壓縮格式，相比于作為源的WAV文件，它們都有相當(dāng)大程度的信號丟失，這也是它們能達到10%的壓縮率的根本原因。而無損壓縮格式，就好比用Zip或RAR這樣的壓縮軟件去壓縮音頻信號，得到的壓縮格式還原成WAV文件，和作為源的WAV文件是一模一樣的！但是如果用Zip或RAR來壓縮WAV文件的話，必須將壓縮包解壓后才能播放。而無損壓縮格式則能直接通過播放軟件實現(xiàn)實時播放，使用起來和MP3等有損格式一模一樣。總而言之，無損壓縮格式就是能在不犧牲任何音頻信號的前提下，減少WAV文件體積的格式。

　　經(jīng)常使用的無損壓縮算法有 Shannon-Fano 編碼，Huffman 編碼，行程（Run-length）編碼，LZW（Lempel-Ziv-Welch）編碼和算術(shù)編碼等。

　　Huffman 編碼

　　該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼。它是統(tǒng)計獨立信源能達到最小平均碼長的編碼方法。編碼效率高 。

　　基本原理：

　　依據(jù)信源字符出現(xiàn)的概率大小來構(gòu)造代碼，對出現(xiàn)概率較大的信源字符，給予較短碼長，而對于出現(xiàn)概率較小的信源字符，給予較長的碼長，最后使得編碼的平均碼字最短。

　　編碼步驟：

　　（1）初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序。

　　（2）把概率最小的兩個符號組成一個節(jié)點。

　　（3）重復(fù)步驟2。

　　（4）從根節(jié)點開始到相應(yīng)于每個符號的“樹葉”，從上到下標(biāo)上“0”（上枝）或者“1”（下枝）至于哪個為“1”哪個為“0”則無關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長度是相同的。

　　（5）從根節(jié)點開始順著樹枝到每個葉子分別寫出每個符號的代碼。

　　Huffman編碼的注意點：

　　Huffman編碼沒有錯誤保護功能，如果碼中有錯誤，則可能引起接下來的一連串譯碼錯誤。

　　Huffman編碼是可變長編碼，因此很難隨意查找或調(diào)用中的文件內(nèi)容。

　　Huffman依賴于信源的統(tǒng)計特性。 Huffman編碼的每個碼字都是整數(shù)：因此實際上平均碼長很難達到信息熵的大小。

　　Huffman編碼解碼必須要有碼表，如果消息數(shù)目很多，那么所需要存儲的碼表也很大，這將影響系統(tǒng)的存儲量及編、譯碼速度。

　　算數(shù)編碼

　　算術(shù)編碼把一個信源集合表示為實數(shù)線上的0到1之間的一個區(qū)間。這個集合中的每個元素都要用來縮短這個區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要一些更多的數(shù)位來表示這個區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個信源的概率模型，然后用這些概率來縮小表示信源集的區(qū)間。

　　算術(shù)編碼用到兩個基本的參數(shù)：

　　符號的概率和它的編碼間隔

　　信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間 。

　　在算術(shù)編碼中需要注意的幾個問題：

　　1、由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。

　　2、算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔［0，1）中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。

　　3、算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。

　　行程（Run-length）編碼

　　RLE（ Run - Length Encoding）是一個針對包含有順序排列的多次重復(fù)的數(shù)據(jù)的壓縮方案。其原理就是把一系列的重復(fù)值用一個單獨的值再加上一個計數(shù)值來取代，行程長度就是連續(xù)且重復(fù)的單元數(shù)目。如果想得到原始數(shù)據(jù)，只需展開這個編碼就可以了。

　　對比RLE編碼前后的代碼數(shù)可以發(fā)現(xiàn)，在編碼前要用73個代碼表示這一行的數(shù)據(jù)，而編碼后只要用10個代碼表示代表原來的73個代碼，壓縮前后的數(shù)據(jù)量之比約為771，即壓縮比為7:1。這說明RLE確實是一種壓縮技術(shù)，而且編碼技術(shù)實用。

　　RLE的性能好壞主要取決于圖像本身的特點。RLE壓縮編碼尤其適用于計算機生成的圖像，對減少圖像文件的存儲空間非常有效。然而，由于顏色豐富的自然圖像在同一行上具有相同顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少，如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大 。

　　譯碼時按照與編碼時采用的相同規(guī)則進行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。

　　因此，RLE屬于無損壓縮技術(shù)它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于傳真機。

　　LZW編碼

　　LZW通過建立一個字符串表，用較短的代碼來表示較長的字符串來實現(xiàn)壓縮。字符串和編碼的對應(yīng)關(guān)系是在壓縮過程中動態(tài)生成的，并且隱含在壓縮數(shù)據(jù)中，解壓的時候根據(jù)表來進行恢復(fù)，是一種無損壓縮，全稱 Lempel-ziy- Welch encoding，簡稱LZW的壓縮算法 。

　　基本原理

　　提取原始文本文件數(shù)據(jù)中的不同字符，基于這些字符創(chuàng)建一個編譯表，然后用編譯表中的字符的索引來替代原始文本文件數(shù)據(jù)中的相應(yīng)字符，減少原始數(shù)據(jù)大小?？雌饋砗驼{(diào)色板圖象的實現(xiàn)原理差不多，但是應(yīng)該注意到的是，我們這里的編譯表不是事先創(chuàng)建好的，而是根據(jù)原始文件數(shù)據(jù)動態(tài)創(chuàng)建的，解碼時還要從已編碼的數(shù)據(jù)中還原出原來的編譯表 。

　　LZW編碼算法的具體執(zhí)行步驟如下步驟：

　　1、開始時的詞典包含所有可能的根（Root），而當(dāng)前前綴P是空的;

　　2、當(dāng)前字符（C）：=字符流中的下一個字符;

　　3、判斷級-符串P+C是否在詞典中

　?。?）如果“是”：P：=P+C//（用C擴展P）

　　（2）如果“否

　　①把代表當(dāng)前前綴P的碼字輸出到碼字流

　?、诎丫Y-符串P+C添加到詞典;

　?、哿頟：=C/（現(xiàn)在的P僅包含一個子符C）

　　4、判斷碼字流中是否還有碼字要譯

　?。?）如果“是”，就返回到步驟2

　　（2）如如果“否”

　?、侔汛懋?dāng)前前綴P的碼輸出到碼字流

　　②結(jié)束