摘   要： 針對數(shù)據(jù)庫中數(shù)據(jù)急速膨脹的狀況，提出一種新的適用于語義壓縮的數(shù)據(jù)庫壓縮算法——基于最優(yōu)匹配的OPMC算法。算法將數(shù)據(jù)表中的屬性元組分類并進(jìn)行最優(yōu)匹配的篩選為每類選取一個(gè)代表元組，將數(shù)據(jù)集中到最優(yōu)匹配的聚類中心點(diǎn)上，消除相似的、冗余的數(shù)據(jù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。該算法經(jīng)仿真實(shí)驗(yàn)驗(yàn)證,有效改善了壓縮比率，相對其他算法的壓縮比率提高18%。
關(guān)鍵詞： 最優(yōu)匹配； OPMC算法； 數(shù)據(jù)壓縮

    數(shù)據(jù)庫正在急速膨脹成應(yīng)用系統(tǒng)中巨大的組成部分，吞噬著系統(tǒng)的性能。當(dāng)單一數(shù)據(jù)庫逐步膨脹為PB容量時(shí)，要查詢到適當(dāng)?shù)拇鎯?nèi)容就會越來越困難。每個(gè)數(shù)據(jù)表的容量正在迅速膨脹，數(shù)百萬行的數(shù)據(jù)表正在膨脹為數(shù)十億行的大規(guī)模數(shù)據(jù)表，還需要額外的空間來備份所有這些數(shù)據(jù)。所以，存儲訪問將更大規(guī)模的數(shù)據(jù)納入更小的空間是未來數(shù)據(jù)庫面臨的巨大挑戰(zhàn)。這就需要有更好、更有效率的壓縮算法和更高性能的壓縮技術(shù)。IDG集團(tuán)資深專欄作家Sean McCown預(yù)測網(wǎng)絡(luò)業(yè)的下一件大事就是新的數(shù)據(jù)壓縮技術(shù)[1]。
    傳統(tǒng)的語法壓縮方法不能滿足大型數(shù)據(jù)庫的需要，因此近年來人們開始研究如何將語義壓縮很好地應(yīng)用于大型數(shù)據(jù)庫。相關(guān)研究較早的有Fascicles[2]算法，是鑒于數(shù)據(jù)表中一些元組在某些屬性值上具有相似性，對其聚合成簇，得到數(shù)據(jù)的簡約表示；ItCompress[3]算法是根據(jù)大型數(shù)據(jù)表中一些元組在某些屬性上取值的相似性，提出的一種有損語義的壓縮方法。貝爾實(shí)驗(yàn)室在大型數(shù)據(jù)表的基于模型的語義壓縮系統(tǒng)(A Model-Based Semantic Compression System for Massive Data Tables)中提出了SPARTAN[4]方法，其主要思想是發(fā)掘數(shù)據(jù)屬性間的依賴關(guān)系、構(gòu)建屬性間的CART決策樹預(yù)測模型和行向聚合成簇。而最新有關(guān)數(shù)據(jù)壓縮方法的研究有以消除數(shù)據(jù)冗余為主要宗旨的DHFXSC算法[4]，它通過構(gòu)造哈夫曼樹獲得相應(yīng)的哈夫曼編碼，然后匹配產(chǎn)生的哈夫曼編碼，該算法的動態(tài)構(gòu)造哈夫曼樹是一個(gè)比較復(fù)雜的過程，會影響壓縮效率；而增量型SDT算法[5]僅對連續(xù)重復(fù)字節(jié)的壓縮和重復(fù)出現(xiàn)的字串的壓縮比較有效；基于均方誤差約束的MSA算法[6]需要非常多的計(jì)算從而影響壓縮速度。
    針對以上方法在靈活性和壓縮性能方面的缺陷，本文提出一種新的行壓縮算法。
1 基于最優(yōu)匹配模型的OPMC（最優(yōu)匹配聚類）算法
    本文的壓縮算法是通過聚類的方法將數(shù)據(jù)聚集到較少的聚類中心點(diǎn)上，消除相似的、冗余的數(shù)據(jù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮，數(shù)據(jù)對象主要是數(shù)據(jù)庫中數(shù)據(jù)表的行數(shù)據(jù)。
    現(xiàn)有聚類算法有K-均值聚類算法、基于模糊劃分的迭代算法、基于遺傳算法的最優(yōu)統(tǒng)計(jì)分析(GAC)等。這些聚類方法一般是根據(jù)“距離”的度量來確定數(shù)據(jù)分類的歸屬，但如果應(yīng)用在允許一定誤差的語義壓縮方面，這種基于“距離”的量度則會影響壓縮效果。因此提出一種新的最優(yōu)匹配模型來解決數(shù)據(jù)分類的歸屬問題。
1.1 最優(yōu)匹配模型

    本文的基于最優(yōu)匹配的聚類算法(簡稱OPMC算法)也采用這種模式。所謂匹配指給定某屬性r的允許誤差e，通過聚類分組后，如果聚類中心值與實(shí)際值在屬性r的誤差在e范圍內(nèi)的，稱屬性r上匹配；滿足上述匹配條件的屬性個(gè)數(shù)越多，匹配越好。同時(shí)也追求最小化存儲代價(jià)，它包括模型數(shù)據(jù)和孤立數(shù)據(jù)?？傮w匹配程度越好，則獨(dú)立數(shù)據(jù)越少。因此要做的就是找到最優(yōu)匹配。
　實(shí)現(xiàn)過程如圖1所示,由允許誤差e，計(jì)算與ai最優(yōu)匹配的P中的元組，變量v指最優(yōu)匹配的P中元組的下標(biāo)，sum指最優(yōu)匹配的數(shù)目。其中外層循環(huán)計(jì)算P中所有元組與ai的匹配數(shù)目，內(nèi)層循環(huán)遍歷判斷每個(gè)屬性是否匹配，輸出最優(yōu)匹配的元組下標(biāo)v及其數(shù)目sum。

1.2 基于最優(yōu)匹配模型的OPMC算法

    Fascicles 算法是針對數(shù)據(jù)表中一些元組在某些屬性值上具有相似性，對其聚合成簇，實(shí)現(xiàn)數(shù)據(jù)的壓縮。ItCompress算法是根據(jù)大型數(shù)據(jù)表中一些元組在某些屬性上取值的相似性，將數(shù)據(jù)表的元組分類并為每類選取一個(gè)代表元組，對每一類的任意元組，均用代表元組表示，除非它與代表元組的誤差超出了指定范圍。
    OPMC算法部分參考了ItCompress算法的思想，進(jìn)行了適當(dāng)?shù)奶幚?。如在調(diào)整聚類中心值的過程中，求取最頻繁出現(xiàn)的屬性區(qū)間，ItCompres采用分片小區(qū)間滑動窗口機(jī)制[3]，而本算法采用了兩個(gè)指針s和t掃描數(shù)據(jù)，時(shí)間復(fù)雜度為O(n)，n為樣本數(shù)目。OPMC算法由數(shù)據(jù)表及其屬性的允許誤差e，求元組歸屬向量M/聚類中心矩陣P和孤立數(shù)據(jù)。如圖2所示，給定初始聚類中心矩陣P，然后循環(huán)計(jì)算總的匹配數(shù)目sumH(P)，并對數(shù)據(jù)表中的每個(gè)元組An計(jì)算最優(yōu)匹配的P中元組，最后在暫時(shí)的聚類分組基礎(chǔ)上,調(diào)整聚類中心矩陣P中每個(gè)元組的值。

    OPMC算法在壓縮前先通過最優(yōu)匹配模型來篩選，克服了DHFXSC算法構(gòu)造哈夫曼樹和MSA算法過多計(jì)算的影響，可以提高壓縮效率,而且OPMC算法尤其適合數(shù)據(jù)屬性間線性相關(guān)的數(shù)據(jù)，這點(diǎn)要優(yōu)于增量型SDT算法。
2 OPMC算法仿真實(shí)驗(yàn)
　設(shè)計(jì)了仿真實(shí)驗(yàn)來驗(yàn)證算法的性能。因Fascicles 算法和ItCompress算法與本算法同是行壓縮算法，故將三種算法一起進(jìn)行實(shí)驗(yàn)比較。
　實(shí)驗(yàn)數(shù)據(jù)是《華爾街日報(bào)》的紐約股票交易所版面上給出的每支股票52周以來每股最高價(jià)、最低價(jià)、分紅率、價(jià)格/ 收益比率、日成交量、日最高價(jià)、日最低價(jià)、收盤價(jià)等信息總共15個(gè)屬性。實(shí)驗(yàn)數(shù)據(jù)取部分樣本數(shù)據(jù)，樣本比率為1%左右，各屬性允許誤差的設(shè)置取值為屬性取值范圍寬度的一個(gè)百分比，如3%。實(shí)驗(yàn)首先觀察給定允許誤差對數(shù)據(jù)壓縮比率的影響，如圖3所示。由圖可以看出，在數(shù)據(jù)屬性間線性相關(guān)關(guān)系明顯的情況下，采用OPMC算法進(jìn)行數(shù)據(jù)壓縮，壓縮比率比Fascicles和ItCompress算法平均高18%左右(將兩算法的壓縮比率取平均與OPMC算法相比較)。原因是實(shí)驗(yàn)數(shù)據(jù)中的股票最高價(jià)、最低價(jià)、分紅率等屬于連續(xù)型數(shù)據(jù)，F(xiàn)ascicles和ItCompress方法比較擅長處理的是非連續(xù)型數(shù)據(jù)，而且它們只對行進(jìn)行壓縮，而由于數(shù)據(jù)本身存在明顯的屬性間線性關(guān)系，所以在行壓縮前先通過最優(yōu)匹配模型來篩選，能夠提高壓縮比率。

   圖4顯示的是OPMC算法的壓縮比率隨樣本比率大小的變化情況，可看出當(dāng)樣本比率大小從0.1%~1.1%變化時(shí)，壓縮比率變化不大，這說明即使較少的樣本數(shù)據(jù)亦可提取較為理想的壓縮模型，由此可見該算法的靈活性。

　大型數(shù)據(jù)庫系統(tǒng)急需更好的壓縮算法以滿足其不斷發(fā)展的需要，語義壓縮比較適合大型數(shù)據(jù)庫系統(tǒng)。本文提出的語義壓縮算法——OPMC算法主要適用于連續(xù)型數(shù)據(jù)，特別是存在明顯的屬性間線性關(guān)系的數(shù)據(jù)。因其在進(jìn)行行壓縮前先通過最優(yōu)匹配模型篩選代表元組，從而可以改善提高壓縮比率（相對同類行壓縮算法Fascicles和ItCompress可提高18%的壓縮比率）。本算法不足之處在于對非連續(xù)型數(shù)據(jù)其壓縮比率表現(xiàn)并不優(yōu)于其他三種算法——Fascicles算法、ItCompress算法和SPARTAN方法，對此有待進(jìn)一步研究改進(jìn)。
參考文獻(xiàn)
[1]  MCCOWN S. 網(wǎng)絡(luò)業(yè)未來12件大事[J].網(wǎng)絡(luò)世界，2007(8):11.
[2]  VJAGADISH H, MADAR J, NG R. Semantic compression  and pattern extraction with fascicles[C]. In Proc. of the  25th Intl. Conf.on Very Large Data Bases. 1999.
[3]  VJAGADISH H, RAYMOND TNg, BENG C C,et al.  It compress: an iterative-semantic compression mgorithm[C].20th International Canference on Data Engineering(ICDE’04).2004:646-657.
[4]  張曉琳,翟國鋒,譚躍生,等. 基于動態(tài)哈夫曼編碼的XML數(shù)據(jù)流壓縮技術(shù)[J]. 內(nèi)蒙古科技大學(xué)學(xué)報(bào),    2007,26(04):331-336.
[5]  趙利強(qiáng),于濤,王建林. 基于SQL數(shù)據(jù)庫的過程數(shù)據(jù)壓縮方法[J]. 計(jì)算機(jī)工程,2008,34(14):58-62.
[6]  高寧波,金宏,王宏安. 歷史數(shù)據(jù)實(shí)時(shí)壓縮方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(28):167-170.
[7]  BABU S, GAROFALAKIS M, RASTOGI R. Spartan: a  model-based semantic compression syatem for massive  data tables[C]. In Proc of the ACM SIGMOD′2001 International Conference on Management of Data. May,2001.