邢 銳，祁 奇，鄭 滔

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

0 引言

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

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

1 有損壓縮算法介紹

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

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

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

1.2 兩點(diǎn)式壓縮算法［3］

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

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

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

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

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

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

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

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

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

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

算法思想介紹

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

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

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

算法介紹

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

判斷點(diǎn)集Q能否用線段壓縮的方法:

在本題目的要求下，點(diǎn)集Q能夠被線段壓縮的條件等價(jià)于:

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

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

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

顯然條件1和條件2是等價(jià)的。

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

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

顯然條件2和條件3也是等價(jià)的。

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

性質(zhì)1 MinL1和MinL2各自至少經(jīng)過(guò)Q中的一個(gè)點(diǎn)。

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

圖2 性質(zhì)1說(shuō)明

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

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

證畢。

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

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

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

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

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

對(duì)于A點(diǎn)在C點(diǎn)右邊的情況，同理可證明。

證畢。

由以上證明過(guò)程也可以看出:

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

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

條件4:在點(diǎn)集Q中所有滿(mǎn)足條件5的L中，至少有一個(gè)L滿(mǎn)足條件6。

圖3 性質(zhì)2說(shuō)明

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

條件6:Q中的點(diǎn)到L的最大豎直距離dmax不超過(guò)2*MAX_ERROR。

壓縮算法流程

壓縮算法的過(guò)程:

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

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

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

步驟2 判斷有沒(méi)有新來(lái)點(diǎn)，如果沒(méi)有則跳至步驟9。

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

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

圖4 新點(diǎn)H的加入

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

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

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

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

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

壓縮算法可行性分析:

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

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

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

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

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

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

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

擬合算法流程

擬合算法的過(guò)程:

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

3 算法性能分析

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

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

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

表1 誤差范圍為1時(shí)效果比較

表2 誤差范圍為0.5時(shí)效果比較

4 結(jié)束語(yǔ)

本文提出了一種改進(jìn)的旋轉(zhuǎn)門(mén)壓縮算法，并編寫(xiě)了程序?qū)铣蓴?shù)據(jù)和實(shí)際過(guò)程數(shù)據(jù)進(jìn)行了仿真計(jì)算，解決了旋轉(zhuǎn)門(mén)算法中保存原始數(shù)據(jù)點(diǎn)和起始點(diǎn)選取過(guò)于單一的問(wèn)題，實(shí)驗(yàn)數(shù)據(jù)證明該算法確實(shí)能夠在不增加最大誤差的情況下，減少壓縮點(diǎn)的數(shù)目并減少絕對(duì)值平均誤差，完成有損壓縮的要求。改進(jìn)的SDT算法計(jì)算量小，運(yùn)行速度很快;并且很容易被工程技術(shù)人員所接受;它不僅可以用在過(guò)程壓縮過(guò)程中，而且也可以用于過(guò)程趨勢(shì)分析和識(shí)別等等。如果壓縮后的數(shù)據(jù)用于壓縮的話(huà)，還可以采用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í)時(shí)數(shù)據(jù)庫(kù)的有損線性壓縮算法研究與改進(jìn)［J］.微計(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í)時(shí)歷史數(shù)據(jù)庫(kù)的分析與實(shí)現(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).［張望陳新楚盧定興.過(guò)程數(shù)據(jù)壓縮算法SDT的改進(jìn)研究與應(yīng)用［J］.工業(yè)控制計(jì)算機(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).［曲奕霖，王文海.用于過(guò)程數(shù)據(jù)壓縮的自控精度SDT算法［J］.計(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ì)算機(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算法的新的過(guò)程數(shù)據(jù)壓縮算法 ［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ù)庫(kù)的過(guò)程數(shù)據(jù)壓縮方法［J］.軟件技術(shù)與數(shù)據(jù)庫(kù)，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ì)算機(jī)工程，2011，37(2):40-42.］