[發(fā)明專利]一種實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法

在審

• 申請?zhí)枺?/td>: 201710544023.2
• 申請日: 2017-07-05
• 公開（公告）號(hào): CN107315829A
• 公開（公告）日: 2017-11-03
• 發(fā)明（設(shè)計(jì)）人: 李迅波;王振林
• 申請（專利權(quán)）人: 成都電科智聯(lián)科技有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 四川君士達(dá)律師事務(wù)所51216
• 代理人: 芶忠義

技術(shù)領(lǐng)域

本發(fā)明屬于規(guī)則集領(lǐng)域，尤其涉及一種實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法。

背景技術(shù)

隨著工業(yè)系統(tǒng)的大型化，數(shù)據(jù)存儲(chǔ)的壓力急劇增加。通用的數(shù)據(jù)壓縮技術(shù)包括PPM算法、BWT算法、LZ系列算法均是對單一規(guī)則(模型)和單一域的簡單壓縮，隨著規(guī)模集增大，壓縮效率逐漸降低，處理時(shí)間也會(huì)越來越長。因此，本文主要針對實(shí)時(shí)數(shù)據(jù)庫中數(shù)據(jù)存儲(chǔ)環(huán)節(jié)的壓縮算法提出改進(jìn)辦法。

傳統(tǒng)壓縮算法

一、旋轉(zhuǎn)門壓縮算法

通過查看當(dāng)前數(shù)據(jù)點(diǎn)與前一個(gè)被保留的數(shù)據(jù)點(diǎn)所構(gòu)成的壓縮偏移覆蓋區(qū)來決定數(shù)據(jù)取舍。偏移覆蓋區(qū)若能覆蓋兩者之間的所有數(shù)據(jù)點(diǎn)，則不保留該數(shù)據(jù)點(diǎn)，否則保留當(dāng)前數(shù)據(jù)點(diǎn)的前一個(gè)節(jié)點(diǎn)，并作為最新保留的數(shù)據(jù)點(diǎn)作為新的起點(diǎn)。實(shí)時(shí)數(shù)據(jù)庫將數(shù)據(jù)進(jìn)行例外測試，變化程度超出預(yù)設(shè)偏差時(shí)，數(shù)據(jù)將被收集，其一以數(shù)據(jù)快照形式保存在主存，其二經(jīng)過壓縮后進(jìn)行數(shù)據(jù)存儲(chǔ)歸檔。

其原理如下圖所示，設(shè)ΔE為SDT算法的壓縮精度，t₀為第一個(gè)保留節(jié)點(diǎn)，從t₀開始作±ΔE的邊界線，隨著數(shù)據(jù)點(diǎn)的增加，旋轉(zhuǎn)門進(jìn)行例外測試，直到數(shù)據(jù)點(diǎn)命中或超出邊界線，保留當(dāng)前節(jié)點(diǎn)，則完成一次壓縮段。接著，以當(dāng)前節(jié)點(diǎn)為起始點(diǎn)同樣作±ΔE的邊界線，直到旋轉(zhuǎn)門轉(zhuǎn)向，錄入新的保留節(jié)點(diǎn)。最后重復(fù)以上步驟，完成所有節(jié)點(diǎn)的壓縮。可以看出，經(jīng)過旋轉(zhuǎn)門壓縮后，t₀～t₇實(shí)際只需保留t₀,t₄,t₇三個(gè)節(jié)點(diǎn)，壓縮率為62.5％。

然而，該數(shù)據(jù)壓縮算法效率跟數(shù)據(jù)本身關(guān)聯(lián)性比較大。如果數(shù)據(jù)變化呈正玄波變化規(guī)律，則壓縮效果較好，否則數(shù)據(jù)為隨機(jī)點(diǎn)時(shí)，幾乎不會(huì)壓縮。另外，ΔE的取值很重要，過小則壓縮率很低，過大則解壓后的誤差較大。在工業(yè)環(huán)境中，壓縮諸如溫度、線速度、張力等參數(shù)的數(shù)據(jù)時(shí)，效果較好。

二、死區(qū)限值壓縮算法

死區(qū)限制壓縮算法通過判斷當(dāng)前值偏離最后一個(gè)記錄的范圍是否大于死區(qū)限值，決定是否記錄此數(shù)據(jù)。如果大于死區(qū)限值，則記錄該數(shù)據(jù)并以此數(shù)據(jù)為新的起點(diǎn)進(jìn)行死區(qū)限值壓縮。假設(shè)誤差精度ΔE為5，則第一次死區(qū)范圍為[23.5,33.5]，如果出現(xiàn)死區(qū)外的點(diǎn)，如46.5則保留節(jié)點(diǎn)，并更新死區(qū)為[41.5,51.5]。這樣10個(gè)數(shù)據(jù)點(diǎn)，只需保留28.5,46.5,55這3個(gè)數(shù)據(jù)點(diǎn)，壓縮率為70％。可知，該類壓縮算法適用于數(shù)據(jù)點(diǎn)上下浮動(dòng)率較小的情況。

三、基于斜率比較的旋轉(zhuǎn)門壓縮算法

斜率比較法只存儲(chǔ)斜率最大和最小的數(shù)據(jù)值,當(dāng)前節(jié)點(diǎn)與上一個(gè)保留節(jié)點(diǎn)形成的斜率如果在最大和最小斜率之間，則舍棄該節(jié)點(diǎn)。否則，需判斷最大斜率和最小斜率的數(shù)據(jù)是否落在己存儲(chǔ)數(shù)據(jù)和新數(shù)據(jù)形成的平行四邊形內(nèi)，從而決定存儲(chǔ)前一個(gè)點(diǎn)(落在平行四邊形外)或者繼續(xù)接收新的數(shù)據(jù)點(diǎn)(落在平行四邊形內(nèi))。

綜上所述，現(xiàn)有技術(shù)存在的問題是：現(xiàn)有技術(shù)大多是對單一規(guī)則(模型)和單一域的簡單壓縮，隨著規(guī)模集增大，壓縮效率逐漸降低，處理時(shí)間也會(huì)越來越長。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)存在的問題，本發(fā)明提供了一種實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法，

本發(fā)明是這樣實(shí)現(xiàn)的，一種實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法，所述實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法先提取每條規(guī)則信息，然后利用Hash運(yùn)算將規(guī)則散列，并以散列值作為查找關(guān)鍵字構(gòu)建二叉樹；為二叉樹的每個(gè)葉節(jié)點(diǎn)建立沖突列表，在沖突列表中逐條規(guī)則比較；最后，遍歷二叉樹進(jìn)行規(guī)制合并，直至規(guī)則集中沒有可以合并的規(guī)則。

進(jìn)一步，所述實(shí)時(shí)數(shù)據(jù)庫中基于規(guī)則集的快速壓縮方法包括以下步驟：

步驟一，規(guī)則集標(biāo)志位置零，構(gòu)建新的空二叉樹；

步驟二，對于未產(chǎn)生合并操作的規(guī)則，進(jìn)行Hash散列；

步驟三，進(jìn)行節(jié)點(diǎn)匹配，若匹配成功則返回沖突列表，進(jìn)行合并測試；否則作為新的節(jié)點(diǎn)插入二叉樹，并建立沖突列表；

步驟四，遍歷匹配節(jié)點(diǎn)的沖突列表，若該規(guī)則與沖突列表內(nèi)的所有規(guī)則均合并，則將其插入沖突列表；

步驟五，重復(fù)步驟二～步驟四，直至所有規(guī)則都被處理；

步驟六，遍歷二叉樹，獲取所有沖突列表；

步驟七，將沖突列表中的規(guī)則合并，有合并發(fā)生時(shí)，合并標(biāo)志位置1；對于規(guī)制R_i若產(chǎn)生了被合并或合并其他規(guī)則的合并操作，分別置對應(yīng)標(biāo)志；

步驟八，刪除二叉樹，如果合并標(biāo)志位為1，則返回步驟一；