文本壓縮(數(shù)據(jù)庫)

時間：2022-11-28 20:30:01 | 來源：信息時代

時間：2022-11-28 20:30:01 來源：信息時代

    文本壓縮 : 采用某種方法對輸入文本進(jìn)行的一種編碼處理,輸出壓縮文本,以便能用更少的字節(jié)數(shù)來表示原有文本,達(dá)到信息的壓縮存儲。文本解壓縮是與文本壓縮相對應(yīng)的概念,即對壓縮文本進(jìn)行解碼處理,輸出原有文本。文本壓縮在文本數(shù)據(jù)中發(fā)揮著重要的作用,這是因為文本壓縮可以減少文本的大小,從而減少數(shù)據(jù)庫的I/O操作,提高數(shù)據(jù)庫性能。目前許多數(shù)據(jù)庫系統(tǒng)(如Oracle、DB2等)一般都支持?jǐn)?shù)據(jù)壓縮功能。
1. 文本壓縮
定義:壓縮率=未壓縮之前文本的大小÷壓縮之后文本的大小。
Shannon曾證明,對給定的一組符號進(jìn)行編碼,每個符號需要的平均位數(shù)等于平均信息量:

E是任何壓縮算法的理論極限。Shannon還指出,在最優(yōu)情況下,出現(xiàn)概率為p的符號需要用log₂(1/p)個位來表示。
2. 文本壓縮方法
(1)基于詞典的壓縮方法:最早由Ziv和lempel在20世紀(jì)70年代提出的,該壓縮方法是基于這樣一個樸素的思想: 在前文中已經(jīng)遇見過的字符串可視為先驗知識,在再次遇到它時可以用較短的碼字來表示它,從而實現(xiàn)壓縮。它不是把單個字符編碼成可變長度的碼字,而是將可變長度的符號串編碼成碼字,或稱為標(biāo)記(token)。如果該碼字的長度短于字符串的長度,則實現(xiàn)了壓縮。LZ系列算法,包括LZW、LZ77、LZ78、LZSS等是目前最常用的通用壓縮算法。
(2)基于統(tǒng)計的文本壓縮方法:其基本原理是統(tǒng)計文本符號的出現(xiàn)頻率,用盡可能少的字節(jié)或者位來表示出現(xiàn)頻率高的文本符號?；诮y(tǒng)計的文本壓縮方法可以細(xì)分為兩個階段:建模階段和編碼階段。建模階段主要是統(tǒng)計符號概率分布模型,也就是每個文本符號的出現(xiàn)概率。編碼階段根據(jù)符號概率分布模型,把文本符號轉(zhuǎn)編碼成二進(jìn)制。建模方法可以主要有靜態(tài)、自適應(yīng)、半靜態(tài)三種。靜態(tài)方法預(yù)先估計文本符號的平均概率分布,不管輸入文本是什么,靜態(tài)方法都該分布來指導(dǎo)編碼。當(dāng)輸入文本與預(yù)先估計的分布相差比較大的時候,靜態(tài)方法的壓縮率很差。自適應(yīng)方法無需任何先驗知識,它們一邊掃描壓縮輸入文本,一邊獲取概率分布。當(dāng)輸入文本比較大的時候,自適應(yīng)方法統(tǒng)計的符號概率分布非常接近真實的概率分布。
3.Huffman編碼的實現(xiàn)
基于統(tǒng)計的編碼方法主要有Huffman編碼和算術(shù)編碼。Huffman編碼先構(gòu)造一個哈夫曼樹,之后就可根據(jù)哈夫曼樹進(jìn)行編碼。
給定字符串a(chǎn)bcdafef,根據(jù)字符出現(xiàn)概率可以構(gòu)造一棵如圖1所示的Huffman樹,使得出現(xiàn)概率越高的字符離根結(jié)點越近。

圖1 Huffman編碼示意圖

經(jīng)哈夫曼樹可以得到字符對應(yīng)的碼值,比如字符a用01,b用0000來表示,而字符f用1來表示。字符串a(chǎn)bcdafef壓縮之后的輸出為010000、0001、0010、01、1、0011、1。只要使用同一棵哈夫曼樹,就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼,即任一個字符的編碼都不是另一個字符的編碼的前綴,這樣可以方便解碼。
算術(shù)編碼是壓縮能力最強(qiáng)的一種編碼方式,它把輸入文本表示成一個[0,1)之間的一個數(shù)值。算術(shù)編碼需要預(yù)先獲得符號的概率,并確定每個符號的編碼間隔。算術(shù)編碼給概率較高的符號分配較大的編碼間隔,給出現(xiàn)概率較低的符號賦予較小的編碼間隔。
表1的例子說明算術(shù)編碼的過程。給定三個符號a₁,a₂,a₃,三者出現(xiàn)的概率分別是p₁＝0.4,p₂＝0.5,p₃＝0.1,編碼字符串a(chǎn)₂a₂a₂a₃。

表1 算術(shù)編碼演示

步驟	輸入符號	間隔	計算方法
0	初始狀態(tài)	[0,1)
1	a2	[0.4,0.9)	0+(1-0)×0.4 0+(1-0)×0.9
2	a2	[0.6,0.85)	0.4+(0.9-0.4)×0.4 0.4+(0.9-0.4)×0.9
3	a2	[0.7,0.825)	0.6+(0.85-0.6)×0.4 0.6+(0.85-0.6)×0.9
4	a3	[0.8125,0.8250)	0.7+(0.825-0.7)×0.9 0.7+(0.825-0.7)×1

根據(jù)概率分配間隔,給a₁,a₂,a₃分別分配一段間隔[0,0.4),[0.4,0.9),[0.9,1)。
初始間隔是[0,1),第一個輸入符號是a₂,它的編碼間隔是[0.4,0.9),因此取輸入間隔的40%～90%部分,輸出[0.4,0.9)。
當(dāng)前間隔是[0.4,0.9),第二個輸入符號還是a₂,因此取[0.4,0.9)的40%～90%,輸出[0.6,0.85)。
如此不斷分隔,表1描述了算術(shù)編碼的整個過程,編碼的最終的結(jié)果是[0.8125,0.8250)。