基于數據敏感度自適應的SDT改進算法*

張涵笑，慕福奇，呂欣巖

(1. 中國科學院物聯網研究發展中心，江蘇 無錫 214135；2. 中國科學院大學 微電子學院，北京 100049；3. 江蘇中科羿鏈通信技術有限公司，江蘇 無錫 214135)

0 引言

隨著物聯網技術的飛速發展與普及，人們身邊越來越多的數據被監測和記錄。例如使用較為廣泛的環境信息監測傳感器，在工廠、醫院、運輸、家庭等各種場景都有應用。這類環境監測數據包含溫度、濕度和PM2.5濃度等多種類型，這些數據的持續上傳形成了海量的歷史時序數據。如何高效地存儲這些數據是物聯網技術研究的重要內容，許多研究者從數據壓縮入手以減少數據占用的存儲空間。

旋轉門壓縮算法(Swinging Door Trending，SDT)是常用的時序數據壓縮算法[1-3]。研究人員針對各種實際使用場景對傳統的SDT算法提出了不同的改進方案。如增加強制記錄限來解決變化幅度較小的數據很長時間不被保存的問題[4]；保存兩記錄點之間的原始數據的逼近線段來代替記錄原始數據點以提高壓縮比[5]；預先對原始數據進行平滑和去噪處理，然后再使用SDT算法進行壓縮以提高壓縮率[6]；將SDT算法與無損壓縮算法結合起來，進一步提高壓縮率[7]；根據數據變化幅度來動態調整壓縮偏差以提高壓縮率；記錄對壓縮精度影響最大的數據點來提高壓縮精度[8]。這些改進基本都是根據應用場景的不同，在運算性能、壓縮率和壓縮精度三項指標間進行權衡，以達到最適合應用場景的壓縮方案。以上方法或增加數據處理步驟，或引入了復雜的數學計算，在提高壓縮率或壓縮精度的同時也增加了算法復雜度，而對于海量數據的處理算法是否高效尤為重要。這些方法對所要處理的所有數據一視同仁，均使用相同的壓縮策略。而現實中，如對環境監測數據，往往比較關心高于或低于某一限值的異常值，對于數據在正常值附近波動并不那么敏感。在這種情況下，對所有數據使用相同的壓縮策略是不合適也不高效的。本文提出一種基于數據敏感自適應的SDT改進算法，根據數據的敏感程度使用不同的壓縮策略，能更好地適用這種場景。

1 旋轉門壓縮算法簡介

旋轉門壓縮算法是一種用于時序數據壓縮的有損壓縮算法[9-11]。其原理如圖1所示。

圖1 標準SDT算法示意圖

A點為數據開始記錄點，在A點上方和下方分別取兩點A+和A-，橫坐標與A點相同，縱坐標與A點相差一個容差參數ΔE。從A點開始向后遍歷數據，分別從A+和A-點向下一數據點B畫線，得到A+B與A-B兩扇門，∠AA+B與∠AA-B為兩扇門的夾角。用同樣的方式去處理后面的數據點，兩扇門的角度只能增大不能減小，且要保證兩夾角之和不能超過180°。如對于數據點C，需要將下面這扇門打開更大的角度來包含住C點，上面那扇門不變。因為兩扇門夾角不超過180°，所以本壓縮周期繼續。直到處理到E點時，此時上面的那扇門為A+D，要想包含E點，需要把下面的那扇門打開至A-E的位置。這樣兩扇門的夾角和就會超過180°，因此需要結束本次壓縮周期，記錄上一數據點D作為此周期的結束點，并將E點作為起點開始新的壓縮周期。使用這樣的方式，只記錄了A、D兩點的值，舍棄了中間的數據點B、C，達到壓縮數據的目的。

2 改進的算法

通過研究標準SDT算法，本文提出了一種基于數據敏感度自適應的SDT改進算法(Sensitivity Adaptive Swinging Door Trending，SASDT)。與算法相關的參數及表示形式如下：

ΔE：容差參數；

k：ΔE的調整系數(0

ΔEL-min:寬松標準容差范圍下限；

ΔEL-max:寬松標準容差范圍上限；

ΔES-min:嚴格標準容差范圍下限；

ΔES-max:嚴格標準容差范圍上限；

Smax:單個壓縮周期的最大步長；

S:本次壓縮周期的步長；

S1:上次壓縮周期的步長；

M:敏感數據區間；

T:當前壓縮周期的壓縮類型，類型分為敏感數據壓縮與非敏感數據壓縮兩類。

2.1 算法思想

在傳統的旋轉門壓縮算法中，ΔE是決定壓縮率與壓縮精度的重要參數。本文基于兩個方面的因素來動態地調整ΔE的值，一是數據點的敏感程度，二是數據變化波動大小。

數據的敏感度區間可由用戶靈活設置，使得用戶關心的數據具有較小的壓縮誤差。原始數據敏感度較低時使用ΔE較大的寬松標準，對高敏感度的原始數據使用ΔE較小的嚴格標準，以此來提高低敏感度數據的壓縮率和高敏感度數據的壓縮精度。在寬松或嚴格的不同標準范圍內，根據數據的波動大小來自動調整ΔE，做到進一步精準壓縮。

因為旋轉門壓縮算法的壓縮原理就是將變化波動小于某一值的一組連續數據用一條線段來擬合表示，所以一次壓縮周期的步長就表示了數據波動相對穩定的連續長度。可以用步長來表征當前數據的變化波動趨勢，當步長較大時說明數據具有長時間穩定的趨勢，反之則說明數據波動較大。在改進的算法中，數據當前壓縮周期的步長大于上一周期步長時說明數據波動在趨于穩定，以系數k按比例增大ΔE可取得更好的壓縮率；反之則說明數據波動趨于變化，以系數k按比例減小ΔE來降低壓縮誤差。

2.2 算法步驟

算法：基于數據敏感度自適應的SDT改進算法

輸入：原始監測時序數據

輸出：壓縮后的時序數據

步驟1：讀取待壓縮數據，根據數據是否在敏感區間M內，判斷數據是否為敏感數據。若數據敏感度與當前壓縮類型一致，則進行步驟2；若不一致，則進行步驟5。

步驟2：判斷當前壓縮周期步長是否超過最大步長Smax，若未超過則進行步驟3，若超過則進行步驟4。

步驟3：根據旋轉門算法判斷待壓縮數據是否可以被當前壓縮周期壓縮。若可以，則本壓縮周期步長加1，進行步驟6；否則跳至步驟4。

步驟4：記錄上一個原始數據作為本壓縮周期的結尾數據。根據S與S1的比較結果來調整ΔE。當S≥S1時，ΔE=ΔE*(1+k)；當S

步驟5：記錄上一個原始數據作為本壓縮周期的結尾數據。根據當前數據的敏感度旋轉相應的壓縮標準，將使用的壓縮標準類型賦值給T。重置參數ΔE，若為寬松標準，則ΔE=(ΔEL-min+ΔEL-max)/2；若為嚴格標準，則ΔE=(ΔES-min+ΔES-max)/2。將S1和S初始化為1。使用這些參數，從當前數據開始，啟動新的壓縮周期，進行步驟1。

步驟6：判斷是否還有新數據，若有則執行步驟1，若無則記錄本壓縮周期首尾數據，結束壓縮周期，退出。

基于數據敏感度自適應的SDT改進算法流程圖如圖2所示，本算法相比標準的SDT算法主要有兩方面改進：一是根據數據敏感度的不同，采用不同的容差標準進行壓縮，可以使得用戶敏感的數據具有較低的壓縮誤差，同時從非敏感數據部分得到壓縮率的補償；二是根據數據的波動情況動態地調整容差，可以進一步提高壓縮率。

圖2 改進的算法流程圖

3 算法分析

為了驗證改進算法的有效性，本文使用Java語言編寫實現了標準SDT算法、文獻中最新研究的自適應SDT算法(Adaptive Swinging Door Trending，ASDT)[6]和本文提出的基于數據敏感度的自適應SDT算法(SASDT)，分別使用這三種算法處理相同的數據，以比較算法的性能。

3.1 評價指標

本文將壓縮率CR、均方根誤差e以及壓縮耗時作為衡量算法性能的三個指標[12]。計算公式如下：

其中，m是壓縮刪除的數據量，n是原始數據量。

3.2 對比分析

待壓縮的原始數據來源于實際環境監測數據，包括溫度數據和濕度數據。選取10組監測數據，每組數據量為10 000個。標準SDT算法中參數為：容差范圍ΔE=1.5，最大步長Smax=100；在ASDT算法中，容差參數ΔEmin=1，ΔEmax=2,最大步長Smax=100；在SASDT算法中，調整系數k=0.2，寬松標準容差參數ΔEL-min=1.5，ΔEL-max=3,嚴格標準容差參數ΔES-min=0.5，ΔES-max=1，最大步長Smax=100，敏感數據區間根據數據類型而定。對多組數據執行壓縮算法后，得到性能平均結果如表1所示。

表1 各算法壓縮性能結果比較

從結果可以看出，相較于標準SDT算法，SASDT算法壓縮率有小幅提升，壓縮誤差減小了32%，效果明顯；與ASDT算法比較，SASDT算法在壓縮率與壓縮誤差上也均得到優化。

SASDT算法復雜度與標準SDT算法相比，僅僅是在處理每個數據點時進行一次比較來判斷數據的敏感度。而且調整容差的依據也是通過壓縮步長來判斷的，不需要額外增加計算和統計。因此，改進算法的時間復雜度與標準SDT算法的復雜度差別不大，從表1中的結果也可以看出這點。而ASDT由于增加了數據處理步驟且引入了復雜的數學計算，因此在運行時長上耗時較大，大約是SASDT算法的50倍。在海量數據的處理中，算法的運行效率尤為重要。

圖3 壓縮恢復數據對比圖

從壓縮數據中選取一段進行還原并繪制折線圖，比較標準SDT算法與SASDT算法壓縮數據的還原情況，結果如圖3所示。從圖3明顯可以看出，在1：00～3：00和5：00～9：00這兩個時間段中SASDT算法的壓縮精度更高，數據還原更準確，保留了很多標準SDT算法中沒有的變化趨勢與細節。

3.3 應用實例

本文提出的基于數據敏感度自適應的SDT改進算法已應用在一個實時監測系統中，使用效果如圖4所示。將系統中的歷史監測數據進行壓縮，可大大減少系統所需的存儲空間。由于算法復雜度低，運行效率很高，能快速高效地對大量歷史數據進行壓縮。同時數據解壓簡單高效，也能滿足系統實時查詢歷史數據的要求。數據還原能夠反映原始數據的變化狀態，而且對于敏感數據具有較高的還原精度。系統可以根據需要動態地調整敏感數據區間，也可以靈活地更改嚴格和寬松的容差范圍，以滿足系統需求的同時取得最好的壓縮效率與壓縮精度。目前，該系統已投入實際使用，數據壓縮及解壓功能運行正常，用戶反饋良好，改進算法的有效性與穩定性得到了進一步驗證。

圖4 實際應用效果圖

4 結論

本文通過對應用場景需求的分析以及對標準SDT算法的研究，從數據敏感度和動態調整容差兩個方面入手，提出并實現了基于數據敏感度自適應的SDT改進算法。該算法針對原始數據敏感度不同的問題，采用精度不同的容差標準，保證了用戶關心的數據的壓縮精度；同時，根據相鄰壓縮周期的步長變化，動態調整下一壓縮周期的容差值，這樣可以減少波動較小的

平穩數據的記錄量，進而提高數據壓縮率。該算法復雜度低，沒有增加復雜的數學計算，具有很高的效率。經過性能對比及實際的使用，算法的有效性得到驗證，可靈活高效地應用于各種環境中監測數據的壓縮場景。

[1] 楊冠杰, 李悅. 工業實時數據壓縮算法的分析[J]. 自動化與儀器儀表, 2016(8):214-215.

[2] 劉佳寶, 梁奕, 方俊. 一種過程數據有損壓縮比的動態控制方法[J]. 計算機工程與應用, 2013, 49(8):138-141.

[3] 趙旭東, 丁杰雄, 邊志遠,等. SDT改進算法在數控系統監控平臺中的應用[J]. 制造技術與機床, 2014(10):155-159.

[4] Li Xinli, Qiu Hongkai, Zhu Yaochuan. Research and design of lossy compression algorithm in embedded real-time database[C]// Proceedings of the Second International Conference on Mechatronics and Automatic Control. Springer International Publishing, 2015:1027-1034.

[5] 邢銳, 祁奇, 鄭滔. 改進的SDT算法[J]. 計算機工程與設計, 2013, 34(2):515-518.

[6] 張宗華, 葉志佳, 牛新征. 面向監測數據壓縮的自適應SDT算法[J]. 中國測試, 2017, 43(2):104-108.

[7] 張煒, 王英潔, 鄔蓉蓉. 面向油中溶解氣體監測時序數據壓縮的改進方法[J]. 電力建設, 2017, 38(5):98-104.

[8] 邱紅鍇. 用電及能效信息采集系統嵌入式實時數據庫關鍵技術研究[D]. 北京：華北電力大學, 2015.

[9] 于松濤, 王曉琨, 趙利強,等. 基于容差動態調整的旋轉門(SDT)改進算法[J]. 北京化工大學學報(自然科學版), 2013, 40(3):109-113.

[10] 曲奕霖, 王文海. 用于過程數據壓縮的自控精度SDT算法[J]. 計算機工程, 2010, 36(22):40-42.

[11] Chen Gang, Li Li. An optimized algorithm for lossy compression of real-time data[C]// IEEE International Conference on Intelligent Computing and Intelligent Systems. IEEE, 2010:187-191.

[12] 寧海楠. 一種基于SDT算法的新的過程數據壓縮算法[J]. 計算機技術與發展, 2010, 20(1):25-28.