通信網(wǎng)banner.jpg)
引言
當(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ù)一般分為有損壓縮和無損壓縮。無損壓縮是指重構(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。典型的無損壓縮算法有：Shanno-Fano編碼、Huffman(哈夫曼)編碼、算術(shù)編碼、游程編碼、LZW編碼等。而有損壓縮是重構(gòu)使用壓縮后的數(shù)據(jù)，其重構(gòu)數(shù)據(jù)與原來數(shù)據(jù)有所不同，但不影響原始資料表達(dá)信息，而壓縮率則要大得多。有損壓縮廣泛應(yīng)用于語音、圖像和視頻的數(shù)據(jù)壓縮。常用的有損壓縮算法有PCM(脈沖編碼調(diào)制)、預(yù)測(cè)編碼、變換編碼(離散余弦變換、小波變換等)、插值和外推(空域亞采樣、時(shí)域亞采樣、自適應(yīng))等。新一代的數(shù)據(jù)壓縮算法大多采用有損壓縮，例如矢量量化、子帶編碼、基于模型的壓縮、分形壓縮和小波壓縮等。
3 常用數(shù)據(jù)無損壓縮算法
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所示。
作者：李雷定 馬鐵華 尤文斌 來源：國外電子元器件
