無(wú)損壓縮算法有哪些

　　無(wú)損壓縮的定義

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

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

　　Huffman 編碼

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

　　基本原理：

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

　　編碼步驟：

　?。?）初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序。

　　（2）把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)。

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

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

　?。?）從根節(jié)點(diǎn)開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼。

　　Huffman編碼的注意點(diǎn)：

　　Huffman編碼沒有錯(cuò)誤保護(hù)功能，如果碼中有錯(cuò)誤，則可能引起接下來(lái)的一連串譯碼錯(cuò)誤。

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

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

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

　　算數(shù)編碼

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

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

　　符號(hào)的概率和它的編碼間隔

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

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

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

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

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

　　行程（Run-length）編碼

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

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

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

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

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

　　LZW編碼

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

　　基本原理

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

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

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

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

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

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

　?。?）如果“否

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

　　②把綴-符串P+C添加到詞典;

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

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

　　（1）如果“是”，就返回到步驟2

　?。?）如如果“否”

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

　　②結(jié)束