改進(jìn)的SDT算法

邢 銳，祁 奇，鄭 滔

(南京大學(xué)軟件學(xué)院，江蘇南京210093)

0 引言

在工業(yè)生產(chǎn)過程中長期積累的數(shù)據(jù)是工業(yè)現(xiàn)場寶貴的資源，為診斷和處理故障提供了第一手資料，并同趨勢分析、報警記錄、報表打印等服務(wù)緊密結(jié)合。因此，普遍存在著存儲和利用這些海量生產(chǎn)數(shù)據(jù)的應(yīng)用需求。將數(shù)據(jù)全部存儲到數(shù)據(jù)庫中明顯是不合適也是不現(xiàn)實的，因此需要進(jìn)行壓縮。

當(dāng)前有三類實時數(shù)據(jù)庫系統(tǒng)壓縮算法:有損壓縮、無損壓縮和結(jié)合前兩種方法的二級壓縮。無損壓縮不能滿足存儲海量數(shù)據(jù)要求。而最著名的有損壓縮算法是PI的旋轉(zhuǎn)門算法。本文針對旋轉(zhuǎn)門算法進(jìn)行了分析，改進(jìn)了旋轉(zhuǎn)門中由于必須存儲原始數(shù)據(jù)點而限制壓縮比的缺點。實驗證明改進(jìn)后的算法確實能夠在不提高壓縮誤差的情況下有效提高壓縮比。

1 有損壓縮算法介紹

1.1 工業(yè)標(biāo)準(zhǔn)死區(qū)壓縮算法［1］

很早提出的線性有損壓縮算法，基本思想是:如果當(dāng)前點和最后一個記錄點的差值在一個閾值范圍以內(nèi)，就壓縮當(dāng)前點，否則記錄當(dāng)前點，向后壓縮。

該算法最大的好處就是簡單，實現(xiàn)起來沒有任何難度，而缺點也很明顯，壓縮直線的選取過于單一，如果某一段內(nèi)的點都分布在某條斜率不為0的直線周圍，使用該方法得到的結(jié)果很差。另外也有人將該算法與后面介紹的算法結(jié)合起來，獲得了比較好的效果［2］。

1.2 兩點式壓縮算法［3］

同樣也是很早提出的線性有損壓縮算法，其基本思想是，采用當(dāng)前記錄的兩個點的延長線來預(yù)測后面的數(shù)據(jù)，如果使用這條延長線插值得到的數(shù)據(jù)和當(dāng)前數(shù)據(jù)的值之間的偏差在一個閾值范圍以內(nèi)，就壓縮當(dāng)前點，否則記錄當(dāng)前點，用當(dāng)前點和前一個點向后壓縮。

該方法較工業(yè)標(biāo)準(zhǔn)死區(qū)壓縮算法的好處就是直線的選取不再使用單一的平行于x軸的直線，而采取了兩個點的連線。這樣在一定程度上改善了工業(yè)標(biāo)準(zhǔn)死區(qū)算法中的缺點。但由于直線是采用了之前已經(jīng)存儲的兩個點來確定的，因此過早確定直線導(dǎo)致該算法的預(yù)后性較差。沒有通過后來的點來調(diào)整這條直線位置的缺陷也導(dǎo)致了該算法在效果上不如后面介紹的一些算法。

1.3 旋轉(zhuǎn)門壓縮算法［4］

美國OSI軟件公司研發(fā)的用于實時數(shù)據(jù)庫的有損壓縮算法［4］，對于旋轉(zhuǎn)門壓縮算法來說，先由上一保存數(shù)據(jù)項和當(dāng)前數(shù)據(jù)項來畫出一條直線 (在二維坐標(biāo)圖上)，如果待保存數(shù)據(jù)項不在當(dāng)前數(shù)據(jù)項和上一保存數(shù)據(jù)項的壓縮偏差范圍之內(nèi)，則待保存數(shù)據(jù)項被保存。就算法的具體實現(xiàn)來說，有基本的旋轉(zhuǎn)門壓縮算法和基于斜率比較的旋轉(zhuǎn)門壓縮算法。旋轉(zhuǎn)門壓縮算法是根據(jù)數(shù)據(jù)構(gòu)建一個又一個的高度 (高度即有損壓縮的閾值)固定的平行四邊形去“套住”數(shù)據(jù)，在不能“套住”時將前一個點進(jìn)行歸檔 (存儲)。圖1為旋轉(zhuǎn)門壓縮算法的示意圖。

圖1 旋轉(zhuǎn)門壓縮算法示例

該方法改善了兩點式壓縮算法中過早確定直線的不足，采用該方法能夠根據(jù)后面新來的數(shù)據(jù)調(diào)整直線的位置。這樣能夠很好的根據(jù)數(shù)據(jù)的發(fā)展趨勢進(jìn)行壓縮。

但就直線的選取方法來說，仍顯得有些單一。如果不限定壓縮的直線必須采用首尾點的連線的話，就可以在某個壓縮區(qū)域內(nèi)壓縮更多的點。

1.4 一些基于旋轉(zhuǎn)門壓縮算法的改進(jìn)算法

在旋轉(zhuǎn)門壓縮算法基礎(chǔ)上，有人提出了一些其它的算法，比如動態(tài)調(diào)整旋轉(zhuǎn)門壓縮算法中的閾值來適應(yīng)數(shù)據(jù)的方法［5］，限制一次壓縮的數(shù)據(jù)長度等方法［6］，識別噪聲點的算法［7］，使用曲線進(jìn)行擬合的算法［8］以及增量型 SDT算法［9］。

2 改進(jìn)的旋轉(zhuǎn)門算法

算法思想介紹

旋轉(zhuǎn)門壓縮算法的基本思想是，存儲的數(shù)據(jù)均為原始數(shù)據(jù)。然而有損壓縮算法本身就對誤差有一定的容忍，經(jīng)過實驗發(fā)現(xiàn)，存儲處理后的數(shù)據(jù)而非原始數(shù)據(jù)可以達(dá)到甚至超過旋轉(zhuǎn)門壓縮算法的壓縮效果。

可以不存儲原始數(shù)據(jù)而存儲處理過的數(shù)據(jù)，這個是該改進(jìn)算法重要思想之一。而其他的大部分的旋轉(zhuǎn)門壓縮改進(jìn)算法都是基于原來的旋轉(zhuǎn)門壓縮算法做一些新的處理。比如控制閾值，限制長度等。

在壓縮完一段數(shù)據(jù)以后重新選擇起始點是該改進(jìn)算法的另一個重要思想。由于數(shù)據(jù)變化的連續(xù)性，上一個失效的壓縮點的數(shù)據(jù)失效是因為數(shù)據(jù)的發(fā)展趨勢發(fā)生了變化，而此時使用上一個壓縮區(qū)段的最后點來進(jìn)行存儲會較大的影響壓縮的效果。因此在該算法中，壓縮完一段數(shù)據(jù)后，重新選擇下一個數(shù)據(jù)點作為下一區(qū)段的起點。

算法介紹

算法保存由當(dāng)前可壓縮的點組成的點集Q，每來一個新的點p和Q構(gòu)成新的點集Q’。判斷Q’能否用一條線段來壓縮。如果可以則用Q’替換Q，繼續(xù)讀入新的點。如果不行則存儲用于擬合點集Q中數(shù)據(jù)的線段信息，清空Q，將p添加到點集Q中，然后讀入新的點，開始下一段壓縮。

判斷點集Q能否用線段壓縮的方法:

在本題目的要求下，點集Q能夠被線段壓縮的條件等價于:

條件1 能夠找到一條直線L，滿足:Q中的所有的點到L的豎直距離不超過MAX_ERROR(MAX_ERROR為壓縮算法當(dāng)中的閾值)。

如果有一條直線L滿足條件1，顯然可以使用L來壓縮和恢復(fù)數(shù)據(jù)。而如果Q可以被某條線段壓縮，該線段所在的直線L顯然滿足條件1。

條件2 能夠找到兩條平行的直線L1、L2，滿足:Q中所有的點都在L1的下方 (包括在L1直線上)、L2的上方 (包括在L2直線上)，同時L1、L2在豎直方向的距離d不超過2*MAX_ERROR。

顯然條件1和條件2是等價的。

在滿足條件2的L1、L2當(dāng)中一定有某一對L1、L2，它們之間的豎直距離是最小的。假設(shè)這個距離為dMin，將對應(yīng)dMin的L1和L2記為MinL1和MinL2。

條件3 Q中的MinL1、MinL2的豎直距離dMin不超過2*MAX_ERROR。

顯然條件2和條件3也是等價的。

下面證明MinL1和MinL2的兩個性質(zhì):

性質(zhì)1 MinL1和MinL2各自至少經(jīng)過Q中的一個點。

性質(zhì)2 MinL1和MinL2中至少有一條經(jīng)過了Q中的兩個點。

圖2 性質(zhì)1說明

性質(zhì)1證明:用反證法來證明。

不妨設(shè)MinL1沒有經(jīng)過點集當(dāng)中的點，如圖2所示。則很明顯將MinL1向下平移至經(jīng)過A點的直線MinL1’后也滿足條件 (2)。而此時兩條平行線的距離明顯小于之前的兩條平行線的距離。因此之前的兩條平行線不是dMin最小的兩條平行線，而這與假設(shè)矛盾，因此MinL1必定經(jīng)過Q中的某個點。同理可證，MinL2必定經(jīng)過Q中的某個點。

證畢。

性質(zhì)2證明:仍然用反證法證明。

性質(zhì)1，可假設(shè)MinL1和MinL2各自都只經(jīng)過了Q中的一個點，如圖3所示。設(shè)MinL1經(jīng)過的點為A(xA，yA)，MinL2經(jīng)過的點為C(xC，yC)。假設(shè)MinL1的斜率為k，則通過計算可得，MinL1和MinL2在豎直方向的距離

由于在某個時間點上只能有一個數(shù)據(jù)，因此Q中所有的點均不可能有相同的橫坐標(biāo)。

不妨設(shè)A點在C點左邊，即有xA＜xC。那么由 (1)式可知，k的值越小，d也就越小。也就是說看這兩條線能否繞著A點及C點順時針旋轉(zhuǎn)。

在圖2中，由于兩條直線都只經(jīng)過點集Q中的一個點。明顯可以通過將MinL1順時針旋轉(zhuǎn)至MinL1'(MinL1'經(jīng)過了點集中的另一個點 F)，而將 MinL2順時針旋轉(zhuǎn)至MinL2'。其中F是兩條線同時旋轉(zhuǎn)時它們首先碰到的Q中的其它點。明顯 MinL1'和 MinL2'是滿足條件2的，而MinL1'和MinL2'的距離d小于MinL1和MinL2的距離。這與之前假設(shè)的MinL1和MinL2是最有壓縮的條件矛盾，因此說明假設(shè)不成立。說明MinL1和MinL2至少有一個經(jīng)過了點集Q中的兩個點。

對于A點在C點右邊的情況，同理可證明。

證畢。

由以上證明過程也可以看出:

性質(zhì)3:MinL1和MinL2中至少有一條是點集Q中某兩個點的連線L，而且 L能夠?qū)Ⅻc集Q中所有的點分隔在L的一邊 (包括在L上)。

由以上三條性質(zhì)可知:條件3等價于條件4:

條件4:在點集Q中所有滿足條件5的L中，至少有一個L滿足條件6。

圖3 性質(zhì)2說明

條件5:L是Q中的某兩個點的連線，而且L能夠?qū)中點分隔在L的一邊。

條件6:Q中的點到L的最大豎直距離dmax不超過2*MAX_ERROR。

壓縮算法流程

壓縮算法的過程:

根據(jù)以上的分析，壓縮算法設(shè)計如下:

使用一個數(shù)組LArray記錄Q中所有滿足條件5和條件6的L(包括直線斜率k，y軸截距b，Q中的點到L的最大豎直距離的dmax，點集Q中點和它的位置關(guān)系的一個bool變量location，點在上方為true，下方為false)，使用MinL記錄LArray中dmax最小的L。

步驟1 將Q和LArray置空，讀入新數(shù)據(jù)至newPoint，存儲newPoint，同時將它添加到點集Q中。

步驟2 判斷有沒有新來點，如果沒有則跳至步驟9。

步驟3 讀入新數(shù)據(jù)至newPoint，并將其添加到Q中，將LArray中由于添加了newPoint而不再滿足條件5和條件6的L移除。

步驟4 在newPoint和點集Q中其它點構(gòu)成的直線當(dāng)中，選出斜率最大的直線 kMaxL，和斜率最小的直線kMinL。顯然在這些直線中，有且只有kMaxL和kMinL能夠滿足條件6。(如圖4所示，F(xiàn)H和CH為kMinL和kMaxL)。

圖4 新點H的加入

步驟5 判斷kMaxL是否滿足條件6，如果滿足則將它添加到LArray當(dāng)中。其中的location為true。

步驟6 判斷kMinL是否滿足條件6，如果滿足則將它添加到LArray當(dāng)中。其中的location為false。

步驟7 判斷此時LArray是否為空，如果不為空，取出dmax最小的一個L保存到MinL中，并跳至步驟2。

步驟8 將MinL向location表示的方向平移dmax/2的距離，得到直線LStore。存儲用來恢復(fù)數(shù)據(jù)的LStore。將Q和LArray清空，存儲newPoint并將newPoint添加至Q中，跳至步驟2。

步驟9 將MinL向location表示的方向平移dmax/2的距離，得到直線LStore。存儲用來恢復(fù)數(shù)據(jù)的LStore。將點集Q中最右邊的點存儲，算法結(jié)束。

壓縮算法可行性分析:

步驟1、2、3都是簡單的基本步驟，可以在O(1)時間完成。

將LArray中由于新點的加入而不再滿足條件 (5)或條件 (6)的L移除。需要進(jìn)行以下過程，對LArray中的每條直線判斷是否滿足條件 (5)和條件 (6)。需要進(jìn)行點和直線位置判斷、點到直線豎直距離計算基本步驟。設(shè)LArray中有K條直線，則該步可以在O(K)時間內(nèi)完成。假設(shè)此時點集中點數(shù)據(jù)為N，那么容易知道點集Q中滿足條件 (5)的直線不會超過N個，即K＜=N。O(N)時間內(nèi)完成。

步驟4中，需要進(jìn)行N-1次斜率計算和2* (N-2)次比較，同樣可以在O(N)時間內(nèi)完成。

步驟5和步驟6個需要N-1次距離計算和N-2距離的比較，O(N)時間完成。

步驟7需要一次判斷，可能需要K-1次比較，和一次存儲，O(N)時間完成。

步驟8和步驟9可以在O(1)時間內(nèi)完成。

由以上分析過程可知，算法是可行的。

擬合算法流程

擬合算法的過程:

讀取數(shù)據(jù)庫中的兩個點P1、P2，并讀取存儲的一個LStore信息，使用LStore來恢復(fù)P1和P2之間的數(shù)據(jù) (不包括P1和P2)，然后讀取新的點P3和一個LStore信息，使用LStore恢復(fù)P2和P3之間的數(shù)據(jù) (不包括P2和P3)。依此類推，直到數(shù)據(jù)庫中沒有新的點可以讀取時，算法結(jié)束。由以上描述可知，恢復(fù)算法的運行時間為O(M)，M為壓縮前點的個數(shù)。

3 算法性能分析

對數(shù)據(jù)樣本壓縮的有關(guān)參數(shù)評估。

測試的數(shù)目為6000個數(shù)據(jù)，誤差范圍為分別為1和0.5。表1為誤差范圍為1時效果比較，表2為0.5時效果比較。

由此看來，該算法確實能夠在不增加最大誤差的情況下，減少壓縮點的數(shù)目并減少絕對值平均誤差，完成有損壓縮的要求。

表1 誤差范圍為1時效果比較

表2 誤差范圍為0.5時效果比較

4 結(jié)束語

本文提出了一種改進(jìn)的旋轉(zhuǎn)門壓縮算法，并編寫了程序?qū)铣蓴?shù)據(jù)和實際過程數(shù)據(jù)進(jìn)行了仿真計算，解決了旋轉(zhuǎn)門算法中保存原始數(shù)據(jù)點和起始點選取過于單一的問題，實驗數(shù)據(jù)證明該算法確實能夠在不增加最大誤差的情況下，減少壓縮點的數(shù)目并減少絕對值平均誤差，完成有損壓縮的要求。改進(jìn)的SDT算法計算量小，運行速度很快;并且很容易被工程技術(shù)人員所接受;它不僅可以用在過程壓縮過程中，而且也可以用于過程趨勢分析和識別等等。如果壓縮后的數(shù)據(jù)用于壓縮的話，還可以采用WinZip等軟件進(jìn)一步壓縮的方法［10］。

［1］WANG Jun.Research and improvement of loss linear compression algorithms in the real-time database［J］.Micro Computer Application，2011，32(7):13-18(in Chinese).［王君.基于實時數(shù)據(jù)庫的有損線性壓縮算法研究與改進(jìn)［J］.微計算機(jī)應(yīng)用，2011，32(7):13-18.］

［2］ZHANGXiuxia，HAOJialong，WANGShuangxin.Analysis and implementation of rea-l time historical database of supervisory control and data acquisition configuration software［J］.North China Electric Power，2009(11):50-54(in Chinese).［張秀霞，郝佳龍，王爽心.工業(yè)監(jiān)控組態(tài)軟件實時歷史數(shù)據(jù)庫的分析與實現(xiàn)［J］.華北電力技術(shù)，2009(11):50-54.］

［3］Sivalingam S.Effect of data compression on controller performance monitoring［C］//Trondheim，Norway:Norwegian Univ of Sci＆Technol，2011:594-599.

［4］ZHANG Wang，CHEN XinChu，LU DingXing.Research and application of improved process data compression algorithm-SDT ［J］.Industrial Control Computer，2009(8):1-3(in Chinese).［張望陳新楚盧定興.過程數(shù)據(jù)壓縮算法SDT的改進(jìn)研究與應(yīng)用［J］.工業(yè)控制計算機(jī)，2009(8):1-3.］

［5］QU Yilin，WANGWenhai.Automatic parameter control sdt algorithm for process data compression ［J］.Computer Engineering，2010，36(22):40-42(in Chinese).［曲奕霖，王文海.用于過程數(shù)據(jù)壓縮的自控精度SDT算法［J］.計算機(jī)工程，2010，36(22):40-42.］

［6］ZHANG Qiaofang，LI Guangyao，DING Meilin，et al.Three dimensional canning map generating algorithm from single image［J］.Computer Technology and Development，2010，20(1):22-24(in Chinese).［張巧芳，李光耀，丁關(guān)林，等.基于單幅圖像的三維瀏覽圖生成算法 ［J］.計算機(jī)技術(shù)與發(fā)展，2010，20(1):22-24.］

［7］ZHANGJian，LIU Guangbin.An new data compression based on isdt algorithm and its performance analysis［J］.Fire Control and Command Control，2007，32(2):81-82(in Chinese).［張健，劉光斌.ISDT算法的數(shù)據(jù)壓縮處理及其性能分析［J］.火力與指揮控制，2007，32(2):81-82.］

［8］NING Hainan.A new process data compression algorithm based on sdt algorithm ［J］.Computer Technology and Development，2010(1):25-28(in Chinese).［寧海楠.一種基于SDT算法的新的過程數(shù)據(jù)壓縮算法 ［J］.計算機(jī)技術(shù)與發(fā)展，2010(1):25-28.］

［9］ZHAO Liqiang，YU Tao，WANG Jianlin.Process data compression method based on SQL database［J］.Computer Engineering，2008，34(14):58-62(in Chinese).［趙利強(qiáng)，于濤，王建林.基于SQL數(shù)據(jù)庫的過程數(shù)據(jù)壓縮方法［J］.軟件技術(shù)與數(shù)據(jù)庫，2008，34(14):58-62.］

［10］ZHOU Shuangying，YU Jianqiao.Research of secondary compression algorithm of RWM ＆ DEWS data［J］.Computer Engineering，2011，37(2):40-42(in Chinese).［周雙英，余建橋.RWM＆DEWS數(shù)據(jù)二次壓縮算法研究［J］.計算機(jī)工程，2011，37(2):40-42.］