數(shù)據(jù)壓縮技術(shù)

數(shù)據(jù)壓縮技術(shù)用最少的數(shù)碼來(lái)表示信號(hào)的技術(shù)01技術(shù)介紹點(diǎn)評(píng)數(shù)據(jù)壓縮的可行性技術(shù)簡(jiǎn)史目錄030204基本信息數(shù)據(jù)壓縮技術(shù)，就是用最少的數(shù)碼來(lái)表示信號(hào)的技術(shù)。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻、音頻信號(hào)的數(shù)據(jù)量特別龐大；如果不對(duì)其進(jìn)行有效的壓縮就難以得到實(shí)際的應(yīng)用。因此，數(shù)據(jù)壓縮技術(shù)已成為當(dāng)今數(shù)字通信、廣播、存儲(chǔ)和多媒體娛樂(lè)中的一項(xiàng)關(guān)鍵的共性技術(shù)。技術(shù)介紹技術(shù)介紹在現(xiàn)今的電子信息技術(shù)領(lǐng)域，正發(fā)生著一場(chǎng)有長(zhǎng)遠(yuǎn)影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻、音頻信號(hào)的數(shù)據(jù)量特別龐大，如果不對(duì)其進(jìn)行有效的壓縮就難以得到實(shí)際的應(yīng)用。因此，數(shù)據(jù)壓縮技術(shù)已成為當(dāng)今數(shù)字通信、廣播、存儲(chǔ)和多媒體娛樂(lè)中的一項(xiàng)關(guān)鍵的共性技術(shù)。1．什么是數(shù)據(jù)壓縮其作用是：能較快地傳輸各種信號(hào)，如傳真、Modem通信等；在現(xiàn)有的通信干線并行開通更多的多媒體業(yè)務(wù)，如各種增值業(yè)務(wù)；緊縮數(shù)據(jù)存儲(chǔ)容量，如CD－ROM、VCD和DVD等；降低發(fā)信機(jī)功率，這對(duì)于多媒體移動(dòng)通信系統(tǒng)尤為重要。由此看來(lái)，通信時(shí)間、傳輸帶寬、存儲(chǔ)空間甚至發(fā)射能量，都可能成為數(shù)據(jù)壓縮的對(duì)象。2．?dāng)?shù)據(jù)為何能被壓縮首先，數(shù)據(jù)中間常存在一些多余成分，既冗余度。如在一份計(jì)算機(jī)文件中，某些符號(hào)會(huì)重復(fù)出現(xiàn)、某些符號(hào)比其他符號(hào)出現(xiàn)得更頻繁、某些字符總是在各數(shù)據(jù)塊中可預(yù)見的位置上出現(xiàn)等，這些冗余部分便可在數(shù)據(jù)編碼中除去或減少。冗余度壓縮是一個(gè)可逆過(guò)程，因此叫做無(wú)失真壓縮，或稱保持型編碼。數(shù)據(jù)壓縮的可行性數(shù)據(jù)壓縮的可行性數(shù)據(jù)之所以能被壓縮并能保證數(shù)據(jù)可用，主要是因?yàn)閿?shù)據(jù)往往存在著如下幾種現(xiàn)象。①數(shù)據(jù)中間常存在一些多余成分．即冗余度。如在一份計(jì)算機(jī)文件中．某些符號(hào)會(huì)重復(fù)出現(xiàn)、某些符號(hào)比其他符號(hào)出現(xiàn)得更頻繁、某些字符總是在各數(shù)據(jù)塊中可預(yù)見的位置上出現(xiàn)等。這些冗余數(shù)據(jù)便可在數(shù)據(jù)編碼中除去或減少。冗余度壓縮是一個(gè)可逆過(guò)程，因此叫做無(wú)失真壓縮，或稱保持型編碼。②數(shù)據(jù)間尤其是相鄰的數(shù)據(jù)之間，常存在著相關(guān)性。如圖片中常常有色彩均勻的背景，電視信號(hào)的相鄰兩幀之間可能只有少量的變化景物是不同的，聲音信號(hào)有時(shí)具有一定的規(guī)律性和周期性等等。因此，有可能利用某些變換來(lái)盡可能地去掉這些相關(guān)性數(shù)據(jù)。但這種變換有時(shí)會(huì)帶來(lái)不可恢復(fù)的損失和誤差．因此叫做不可逆壓縮，或稱有失真編碼、熵壓縮等。③人們?cè)谛蕾p音像節(jié)目時(shí)，由于耳、目對(duì)信號(hào)的時(shí)間變化和幅度變化的感受能力都有一定的極限，如人眼對(duì)影視節(jié)目有視覺暫留效應(yīng)．人眼或人耳對(duì)低于某一極限的幅度變化已無(wú)法感知等。因而可將信號(hào)中這部分感覺不出的分量壓縮掉或“掩蔽掉”。這種壓縮同樣是一種不可逆壓縮。

點(diǎn)評(píng)點(diǎn)評(píng)隨著數(shù)據(jù)量的不斷海量，CPU的不斷強(qiáng)勁，雙核四核的叫個(gè)不停，一種叫做時(shí)間換空間的優(yōu)化技術(shù)應(yīng)該會(huì)越來(lái)越流行。所以，數(shù)據(jù)壓縮對(duì)于今后的數(shù)據(jù)庫(kù)來(lái)說(shuō)，應(yīng)該會(huì)從核武器變成常規(guī)武器。Oracle從9i開始羞羞答答的引入表級(jí)壓縮，一直以來(lái)都是像中國(guó)的核電站一樣，宣傳的用處大，論實(shí)際的貢獻(xiàn)就不怎么樣了。Oracle11g似乎是正兒八經(jīng)的要推廣數(shù)據(jù)壓縮技術(shù)了，專門推出了一個(gè)叫做AdvanceCompression的組件，全面支持普通表壓縮，非結(jié)構(gòu)化數(shù)據(jù)壓縮（SecureFile數(shù)據(jù)壓縮），DataPump數(shù)據(jù)壓縮，以及RMAN備份壓縮，數(shù)據(jù)壓縮技術(shù)從此名正言順的登上歷史舞臺(tái)。既然是專門做為一個(gè)Option推出，Oracle一定是對(duì)該特性相當(dāng)有信心，所以需要單獨(dú)為該特性購(gòu)買License。在Oracle9i中雖然引入了表壓縮，但是有很大的限制。只能對(duì)批量裝載操作（比如直接路徑裝載，CTAS等）涉及的數(shù)據(jù)進(jìn)行壓縮，普通的DML操作的數(shù)據(jù)是無(wú)法壓縮的。這應(yīng)該是對(duì)于寫操作的壓縮難題沒有解決，一直遺留到Oracle11g，總算是解決了關(guān)系數(shù)據(jù)壓縮的寫性能問(wèn)題。Oracle的表壓縮是針對(duì)Block級(jí)別的數(shù)據(jù)壓縮，主要技術(shù)和Oracle9i差不多，還是在Block中引入symbol表，將block中的重復(fù)數(shù)據(jù)在symbol中用一個(gè)項(xiàng)表示。Oracle會(huì)對(duì)block進(jìn)行批量壓縮，而不是每次在block中寫入數(shù)據(jù)時(shí)都進(jìn)行壓縮，通過(guò)這種方式，可以盡量降低數(shù)據(jù)壓縮對(duì)于DML操作的性能影響。這樣，在block級(jí)別應(yīng)該會(huì)引入一個(gè)新的參數(shù)，用于控制block中未壓縮的數(shù)據(jù)量達(dá)到某個(gè)標(biāo)準(zhǔn)以后進(jìn)行壓縮操作。技術(shù)簡(jiǎn)史概率奇緣數(shù)學(xué)游戲異族傳說(shuō)音畫時(shí)尚回到未來(lái)12345技術(shù)簡(jiǎn)史概率奇緣一千多年前的中國(guó)學(xué)者就知道用“班馬”這樣的縮略語(yǔ)來(lái)指代班固和司馬遷，這種崇尚簡(jiǎn)約的風(fēng)俗一直延續(xù)到了今天的Internet時(shí)代：當(dāng)我們?cè)贐BS上用“7456”代表“氣死我了”，或是用“B4”代表“Before”的時(shí)候，我們至少應(yīng)該知道，這其實(shí)就是一種最簡(jiǎn)單的數(shù)據(jù)壓縮呀。嚴(yán)格意義上的數(shù)據(jù)壓縮起源于人們對(duì)概率的認(rèn)識(shí)。當(dāng)我們對(duì)文字信息進(jìn)行編碼時(shí)，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長(zhǎng)的編碼，總的編碼長(zhǎng)度就能縮短不少。遠(yuǎn)在計(jì)算機(jī)出現(xiàn)之前，著名的Morse電碼就已經(jīng)成功地實(shí)踐了這一準(zhǔn)則。在Morse碼表中，每個(gè)字母都對(duì)應(yīng)于一個(gè)唯一的點(diǎn)劃組合，出現(xiàn)概率最高的字母e被編碼為一個(gè)點(diǎn)“.”，而出現(xiàn)概率較低的字母z則被編碼為“--..”。顯然，這可以有效縮短最終的電碼長(zhǎng)度。信息論之父non第一次用數(shù)學(xué)語(yǔ)言闡明了概率與信息冗余度的關(guān)系。在1948年發(fā)表的論文“通信的數(shù)學(xué)理論（AMathematicalTheoryofCommunication）”中，Shannon指出，任何信息都存在冗余，冗余大小與信息中每個(gè)符號(hào)（數(shù)字、字母或單詞）的出現(xiàn)概率或者說(shuō)不確定性有關(guān)。Shannon借鑒了熱力學(xué)的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計(jì)算信息熵的數(shù)學(xué)表達(dá)式。這篇偉大的論文后來(lái)被譽(yù)為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。從本質(zhì)上講，數(shù)據(jù)壓縮的目的就是要消除信息中的冗余，而信息熵及相關(guān)的定理恰恰用數(shù)學(xué)手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計(jì)算出信息編碼的極限，即在一定的概率模型下，無(wú)損壓縮的編碼長(zhǎng)度不可能小于信息熵公式給出的結(jié)果。數(shù)學(xué)游戲設(shè)計(jì)具體的壓縮算法的過(guò)程通常更像是一場(chǎng)數(shù)學(xué)游戲。開發(fā)者首先要尋找一種能盡量精確地統(tǒng)計(jì)或估計(jì)信息中符號(hào)出現(xiàn)概率的方法，然后還要設(shè)計(jì)一套用最短的代碼描述每個(gè)符號(hào)的編碼規(guī)則。統(tǒng)計(jì)學(xué)知識(shí)對(duì)于前一項(xiàng)工作相當(dāng)有效，迄今為止，人們已經(jīng)陸續(xù)實(shí)現(xiàn)了靜態(tài)模型、半靜態(tài)模型、自適應(yīng)模型、Markov模型、部分匹配預(yù)測(cè)模型等概率統(tǒng)計(jì)模型。相對(duì)而言，編碼方法的發(fā)展歷程更為曲折一些。1948年，Shannon在提出信息熵理論的同時(shí)，也給出了一種簡(jiǎn)單的編碼方法——Shannon編碼。1952年，又進(jìn)一步提出了Fano編碼。這些早期的編碼方法揭示了變長(zhǎng)編碼的基本規(guī)律，也確實(shí)可以取得一定的壓縮效果，但離真正實(shí)用的壓縮算法還相去甚遠(yuǎn)。第一個(gè)實(shí)用的編碼方法是由man在1952年的論文“最小冗余度代碼的構(gòu)造方法（AMethodfortheConstructionofMinimumRedundancyCodes）”中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時(shí)仍要提及這種被后人稱為Huffman編碼的方法。Huffman編碼在計(jì)算機(jī)界是如此著名，以至于連編碼的發(fā)明過(guò)程本身也成了人們津津樂(lè)道的話題。據(jù)說(shuō)，1952年時(shí)，年輕的Huffman還是麻省理工學(xué)院的一名學(xué)生，他為了向老師證明自己可以不參加某門功課的期末考試，才設(shè)計(jì)了這個(gè)看似簡(jiǎn)單，但卻影響深遠(yuǎn)的編碼方法。Huffman編碼效率高，運(yùn)算速度快，實(shí)現(xiàn)方式靈活，從20世紀(jì)60年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。異族傳說(shuō)逆向思維永遠(yuǎn)是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進(jìn)Huffman或算術(shù)編碼，以獲得一種兼顧了運(yùn)行速度和壓縮效果的“完美”編碼的時(shí)候，兩個(gè)聰明的猶太人J.Ziv和A.Lempel獨(dú)辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個(gè)猶太人姓氏的縮寫，將這些算法統(tǒng)稱為L(zhǎng)Z系列算法。按照時(shí)間順序，LZ系列算法的發(fā)展歷程大致是：Ziv和Lempel于1977年發(fā)表題為“順序數(shù)據(jù)壓縮的一個(gè)通用算法（AUniversalAlgorithmforSequentialDataCompression）”的論文，論文中描述的算法被后人稱為L(zhǎng)Z77算法。1978年，二人又發(fā)表了該論文的續(xù)篇“通過(guò)可變比率編碼的獨(dú)立序列的壓縮（CompressionofIndividualSequencesviaVariableRateCoding）”，描述了后來(lái)被命名為L(zhǎng)Z78的壓縮算法。1984年，h發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)（ATechniqueforHighPerformanceDataCompression）”的論文，描述了他在Sperry研究中心（該研究中心后來(lái)并入了Unisys公司）的研究成果，這是LZ78算法的一個(gè)變種，也就是后來(lái)非常有名的LZW算法。1990年后，等人又陸續(xù)提出了許多LZ系列算法的變體或改進(jìn)版本。說(shuō)實(shí)話，LZ系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡(jiǎn)單地延續(xù)了千百年來(lái)人們對(duì)字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說(shuō)，當(dāng)你用字典中的頁(yè)碼和行號(hào)代替文章中每個(gè)單詞的時(shí)候，你實(shí)際上已經(jīng)掌握了LZ系列算法的真諦。音畫時(shí)尚LZ系列算法基本解決了通用數(shù)據(jù)壓縮中兼顧速度與壓縮效果的難題。但是，數(shù)據(jù)壓縮領(lǐng)域里還有另一片更為廣闊的天地等待著我們?nèi)ヌ剿?。Shannon的信息論告訴我們，對(duì)信息的先驗(yàn)知識(shí)越多，我們就可以把信息壓縮得越小。換句話說(shuō)，如果壓縮算法的設(shè)計(jì)目標(biāo)不是任意的數(shù)據(jù)源，而是基本屬性已知的特種數(shù)據(jù)，壓縮的效果就會(huì)進(jìn)一步提高。這提醒我們，在發(fā)展通用壓縮算法之余，還必須認(rèn)真研究針對(duì)各種特殊數(shù)據(jù)的專用壓縮算法。比方說(shuō)，在今天的數(shù)碼生活中，遍布于數(shù)碼相機(jī)、數(shù)碼錄音筆、數(shù)碼隨身聽、數(shù)碼攝像機(jī)等各種數(shù)字設(shè)備中的圖像、音頻、視頻信息，就必須經(jīng)過(guò)有效的壓縮才能在硬盤上存儲(chǔ)或是通過(guò)USB電纜傳輸。實(shí)際上，多媒體信息的壓縮一直是數(shù)據(jù)壓縮領(lǐng)域里的重要課題，其中的每一個(gè)分支都有可能主導(dǎo)未來(lái)的某個(gè)技術(shù)潮流，并為數(shù)碼產(chǎn)品、通信設(shè)備和應(yīng)用軟件開發(fā)商帶來(lái)無(wú)限的商機(jī)。讓我們先從圖像數(shù)據(jù)的壓縮講起。通常所說(shuō)的圖像可以被分為二值圖像、灰度圖像、彩色圖像等不同的類型。每一類圖像的壓縮方法也不盡相同。傳真技術(shù)的發(fā)明和廣泛使用促進(jìn)了二值圖像壓縮算法的飛速發(fā)展。CCITT（國(guó)際電報(bào)**咨詢委員會(huì)，是國(guó)際電信聯(lián)盟ITU下屬的一個(gè)機(jī)構(gòu)）針對(duì)傳真類應(yīng)用建立了一系列圖像壓縮標(biāo)準(zhǔn)，專用于壓縮和傳遞二值圖像。這些標(biāo)準(zhǔn)大致包括20世紀(jì)70年代后期的CCITTGroup1和Group2，1980年的CCITTGroup3，以及1984年的CCITTGroup4。為了適應(yīng)不同類型的傳真圖像，這些標(biāo)準(zhǔn)所用的編碼方法包括了一維的MH編碼和二維的MR編碼，其中使用了行程編碼（RLE）和Huffman編碼等技術(shù)。回到未來(lái)從信息熵到算術(shù)編碼，從猶太人到WinRAR，從JPEG到MP3，數(shù)據(jù)壓縮技術(shù)的發(fā)展史就像是一個(gè)寫滿了“創(chuàng)新”、“挑戰(zhàn)”、“突破”和“變革”的羊皮卷軸。也許，我們?cè)谶@里不厭其煩地羅列年代、人物、標(biāo)準(zhǔn)和文獻(xiàn)，其目的只是要告訴大家，前人的成果只不過(guò)是后人有望超越的目標(biāo)而已，誰(shuí)知道在未來(lái)的幾年里，還會(huì)出現(xiàn)幾個(gè)Shannon，幾個(gè)Huffman呢？談到未來(lái)，我們還可以補(bǔ)充一些與數(shù)據(jù)壓縮技術(shù)的發(fā)展趨勢(shì)有關(guān)的話題。1994年，M.Burrows和ler共同提出了一種全新的通用數(shù)據(jù)壓縮算法。這種算法的核心思想是對(duì)字符串輪轉(zhuǎn)后得到的字符矩陣進(jìn)行排序和變換，類似的變換算法被稱為Burrows-Wheeler變換，簡(jiǎn)稱BWT。與Ziv和Lempel另辟蹊徑的做法如出一轍，Burrows和Wheeler設(shè)計(jì)的BWT算法與以往所有通用壓縮算法的設(shè)計(jì)思路都迥然不同。如