1引言
當(dāng)今,，各種信息系統(tǒng)的數(shù)據(jù)量越來越大,，如何更快、更多,、更好地傳輸與存儲(chǔ)數(shù)據(jù)成為數(shù)據(jù)信息處理的首要問題,，而數(shù)據(jù)壓縮技術(shù)則是解決這一問題的重要方法,。事實(shí)上，從壓縮軟件WINRAR到熟知的MP3，數(shù)據(jù)壓縮技術(shù)早已應(yīng)用于各個(gè)領(lǐng)域,。
2 數(shù)據(jù)壓縮技術(shù)概述
本質(zhì)上壓縮數(shù)據(jù)是因?yàn)閿?shù)據(jù)自身具有冗余性。數(shù)據(jù)壓縮是利用各種算法將數(shù)據(jù)冗余壓縮到最小,，并盡可能地減少失真，從而提高傳輸效率和節(jié)約存儲(chǔ)空間,。
數(shù)據(jù)壓縮技術(shù)一般分為有損壓縮和無(wú)損壓縮,。無(wú)損壓縮是指重構(gòu)壓縮數(shù)據(jù)(還原,，解壓縮),，而重構(gòu)數(shù)據(jù)與原來數(shù)據(jù)完全相同。該方法用于那些要求重構(gòu)信號(hào)與原始信號(hào)完全一致的場(chǎng)合,，如文本數(shù)據(jù),、程序和特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(如指紋圖像,、醫(yī)學(xué)圖像等)的壓縮,。這類算法壓縮率較低，一般為1／2~1／5,。典型的無(wú)損壓縮算法有：Shanno-Fano編碼、Huffman(哈夫曼)編碼,、算術(shù)編碼、游程編碼,、LZW編碼等。而有損壓縮是重構(gòu)使用壓縮后的數(shù)據(jù),，其重構(gòu)數(shù)據(jù)與原來數(shù)據(jù)有所不同,，但不影響原始資料表達(dá)信息，而壓縮率則要大得多,。有損壓縮廣泛應(yīng)用于語(yǔ)音、圖像和視頻的數(shù)據(jù)壓縮,。常用的有損壓縮算法有PCM(脈沖編碼調(diào)制),、預(yù)測(cè)編碼,、變換編碼(離散余弦變換,、小波變換等),、插值和外推(空域亞采樣,、時(shí)域亞采樣、自適應(yīng))等,。新一代的數(shù)據(jù)壓縮算法大多采用有損壓縮，例如矢量量化,、子帶編碼、基于模型的壓縮,、分形壓縮和小波壓縮等。
3 常用數(shù)據(jù)無(wú)損壓縮算法
3．1 游程編碼
這種數(shù)據(jù)壓縮思想：如果數(shù)據(jù)項(xiàng)d在輸入流中連續(xù)出現(xiàn)n次,，則以單個(gè)字符對(duì)nd來替換連續(xù)出現(xiàn)n次的數(shù)據(jù)項(xiàng),，這n個(gè)連續(xù)出現(xiàn)的數(shù)據(jù)項(xiàng)叫游程n，這種數(shù)據(jù)壓縮方法稱游程編碼(RLE),，其實(shí)現(xiàn)流程如圖1所示,。RLE算法具有實(shí)現(xiàn)簡(jiǎn)單,，壓縮還原速度快等優(yōu)點(diǎn),，只需掃描一次原始數(shù)據(jù)即可完成數(shù)據(jù)壓縮,。其缺點(diǎn)是呆板，適應(yīng)性差,，不同的文件格式的壓縮率波動(dòng)大,，平均壓縮率低,。實(shí)踐表明,，RLE能夠壓縮復(fù)雜度不高的原始點(diǎn)陣圖像。
3．2 基于字典編碼技術(shù)的LZW算法
LZW算法是LZ78的流行變形,，由Terrv Welch在1984年開發(fā),。LZW算法首先將字母表中的所有字符初始化到字典，常用8位字符,，在輸入任何數(shù)據(jù)前優(yōu)先占用字典的前256項(xiàng)(0～255),。LZW編碼的原理：編碼器逐個(gè)輸入字符并累積一個(gè)字符串I。每輸入一個(gè)字符則串接在I后面,，然后在字典中查找I,；只要找到I，該過程繼續(xù)執(zhí)行搜索,。直到在某一點(diǎn),，添加下一個(gè)字符x導(dǎo)致搜索失敗，這意味著字符串I在字典中,，而Ix(字符x串接在I后)卻不在,。此時(shí)編碼器輸出指向字符串,，的字典指針；并在下一個(gè)可用的字典詞條中存儲(chǔ)字符串Ix,；把字符串I預(yù)置為x,。其壓縮流程如圖2所示。
因?yàn)樽值涞那?56項(xiàng)被占用,，因此字典指針必須高于8位,。由于LZW算法的字典中的字符串每次僅增加一個(gè)字符。因此,，要獲得長(zhǎng)字符串則需較長(zhǎng)時(shí)間，這樣才能較好地壓縮．IZW編碼能夠適應(yīng)輸入數(shù)據(jù),。
LZW算法與其他算法相比具有自適應(yīng)的特點(diǎn),，即可以根據(jù)壓縮內(nèi)容不同來建立不同字典,，以減少冗余度,，提高壓縮比,；并且解壓時(shí)這個(gè)字典無(wú)需與壓縮代碼同時(shí)傳送,，而是在解壓過程中逐步建立與壓縮時(shí)完全相同的字典,，從而完整、準(zhǔn)確地恢復(fù)被壓縮內(nèi)容,。因此,，LZW算法是一種解碼速度與壓縮性能較好的壓縮算法,。
實(shí)現(xiàn)LZW算法需要考慮以下幾點(diǎn)：
(1)字典建立(數(shù)據(jù)結(jié)構(gòu)與字典大小) LZW字典的數(shù)據(jù)結(jié)構(gòu)是一棵多叉樹。字典越大,，代替的子串越多,。但應(yīng)用中字典容量則受一定限制,，要權(quán)衡利弊選擇合適的字典,。
(2)字典維護(hù)與更新字典指針由哈希函數(shù)生成,。正確選擇哈希函數(shù)非常重要,，這將影響執(zhí)行效率,。正確的哈希函數(shù)所產(chǎn)生的重復(fù)值極少,，這樣檢索字符串所需比較次數(shù)也較少，從而可有效提高代碼的執(zhí)行效率,。
當(dāng)字典滿時(shí)，字典的維護(hù)和更新對(duì)壓縮率也是至關(guān)重要的,。可重新從初始狀態(tài)建立字典,；也可監(jiān)測(cè)壓縮率,，當(dāng)壓縮率變壞時(shí)全部或部分清除字典,。
(3)壓縮數(shù)據(jù)代碼長(zhǎng)度壓縮時(shí)，輸入數(shù)據(jù)一般是8位,。但壓縮后的輸出是轉(zhuǎn)化的字符串代碼,，其中0～255為8位碼,，256為9位碼，25l～512為10位碼,，l 024為11位碼,。解壓則相反，需要位操作,。因此,，輸出可以從9位碼開始，隨著字典內(nèi)容的增加,，碼字也逐漸增加,。這樣可提高執(zhí)行效率，但在譯碼時(shí)需考慮不等長(zhǎng)碼的識(shí)別,，可通過設(shè)置標(biāo)志位來解決,。
3．3 基于哈夫曼編碼原理的壓縮算法
哈夫曼算法的過程為：統(tǒng)計(jì)原始數(shù)據(jù)中各字符出現(xiàn)的頻率,；所有字符按頻率降序排列,；建立哈夫曼樹：將哈夫曼樹存入結(jié)果數(shù)據(jù),；重新編碼原始數(shù)據(jù)到結(jié)果數(shù)據(jù),。哈夫曼算法實(shí)現(xiàn)流程如圖3所示。
哈夫曼算法的實(shí)質(zhì)是針對(duì)統(tǒng)計(jì)結(jié)果對(duì)字符本身重新編碼，而不是對(duì)重復(fù)字符或重復(fù)子串編碼,。實(shí)用中．符號(hào)的出現(xiàn)頻率不能預(yù)知,，需要統(tǒng)計(jì)和編碼兩次處理，所以速度較慢,，無(wú)法實(shí)用,。而自適應(yīng)(或動(dòng)態(tài))哈夫曼算法取消了統(tǒng)計(jì)，可在壓縮數(shù)據(jù)時(shí)動(dòng)態(tài)調(diào)整哈夫曼樹,，這樣可提高速度,。因此,，哈夫曼編碼效率高,，運(yùn)算速度快,，實(shí)現(xiàn)方式靈活。
采用哈夫曼編碼時(shí)需注意的問題：
(1)哈夫曼碼無(wú)錯(cuò)誤保護(hù)功能,，譯碼時(shí),，碼串若無(wú)錯(cuò)就能正確譯碼,；若碼串有錯(cuò)應(yīng)考慮增加編碼,，提高可靠性,。
(2)哈夫曼碼是可變長(zhǎng)度碼,，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容,，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮,。
(3)哈夫曼樹的實(shí)現(xiàn)和更新方法對(duì)設(shè)計(jì)非常關(guān)鍵,。
3．4 基于算術(shù)編碼的壓縮算法
算術(shù)編碼壓縮也是一種根據(jù)字符出現(xiàn)概率重新編碼的壓縮方案。該思想和哈夫曼編碼有些相似,，但哈夫曼編碼的每個(gè)字符需用整數(shù)個(gè)位表示,。而算術(shù)編碼方法則無(wú)這一限制，它是將輸入流視為整體進(jìn)行編碼,。雖然算術(shù)編碼壓縮率高．但運(yùn)算復(fù)雜,，速度慢。
4 結(jié)語(yǔ)
游程編碼和LZW編碼屬于基于字典模型的壓縮算法,，而哈夫曼編碼和算術(shù)編碼屬于基于統(tǒng)計(jì)模型的壓縮算法,，前者與原始數(shù)據(jù)的排列次序有關(guān)而與其出現(xiàn)頻率無(wú)關(guān)，后者則正好相反,。這兩類壓縮方法算法思想各有所長(zhǎng),，相互補(bǔ)充。許多壓縮軟件結(jié)合了這兩類算法。例如WINRAR就采用了字典編碼和哈夫曼編碼算法,。這幾種數(shù)據(jù)無(wú)損壓縮算法應(yīng)用廣泛,，設(shè)計(jì)人員可以根據(jù)具體應(yīng)用中的數(shù)據(jù)流特點(diǎn)來改進(jìn)算法從而開發(fā)適用的軟硬件壓縮器。