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

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

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

1.2 基于最優匹配模型的OPMC算法

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

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

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

　大型數據庫系統急需更好的壓縮算法以滿足其不斷發展的需要，語義壓縮比較適合大型數據庫系統。本文提出的語義壓縮算法——OPMC算法主要適用于連續型數據，特別是存在明顯的屬性間線性關系的數據。因其在進行行壓縮前先通過最優匹配模型篩選代表元組，從而可以改善提高壓縮比率（相對同類行壓縮算法Fascicles和ItCompress可提高18%的壓縮比率）。本算法不足之處在于對非連續型數據其壓縮比率表現并不優于其他三種算法——Fascicles算法、ItCompress算法和SPARTAN方法，對此有待進一步研究改進。
參考文獻
[1]  MCCOWN S. 網絡業未來12件大事[J].網絡世界，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]  張曉琳,翟國鋒,譚躍生,等. 基于動態哈夫曼編碼的XML數據流壓縮技術[J]. 內蒙古科技大學學報,    2007,26(04):331-336.
[5]  趙利強,于濤,王建林. 基于SQL數據庫的過程數據壓縮方法[J]. 計算機工程,2008,34(14):58-62.
[6]  高寧波,金宏,王宏安. 歷史數據實時壓縮方法研究[J].計算機工程與應用,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.