趙宏偉，劉宇琦，特日根，陳長征，臧雪柏,3

(1.吉林大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，長春 130012；2.中國科學(xué)院 應(yīng)用光學(xué)國家重點(diǎn)實(shí)驗(yàn)室，長春 130033； 3.吉林大學(xué) 符號計算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室，長春 130012；4.長光衛(wèi)星技術(shù)有限公司，長春 130000)

0 引 言

數(shù)據(jù)業(yè)務(wù)和多媒體通信業(yè)務(wù)等通信量越來越大，給信息存儲特別是網(wǎng)絡(luò)傳輸帶來前所未有的壓力?，F(xiàn)有數(shù)據(jù)壓縮算法分為無損壓縮和有損壓縮。有損壓縮通過數(shù)據(jù)挖掘等手段從數(shù)據(jù)來源、數(shù)據(jù)特性出發(fā)，提取關(guān)鍵信息予以保存。語音識別、市場銷售數(shù)據(jù)、氣象數(shù)據(jù)、電信通信數(shù)據(jù)等均可采用有損壓縮方法處理。針對這種數(shù)據(jù)的有損壓縮通常有兩類辦法[1]：數(shù)據(jù)匯聚和數(shù)據(jù)近似。匯聚函數(shù)以拋棄數(shù)據(jù)中的原始結(jié)構(gòu)為代價，減少數(shù)據(jù)量，但這種方法使得一些有用的知識被刪除，其中主要包括COUNT、SUM、AVG等方法；數(shù)據(jù)近似[2]可視為基于模型的數(shù)據(jù)獲取，通過對采集到的感知數(shù)據(jù)進(jìn)行分布式建模，可減少數(shù)據(jù)傳輸量、節(jié)省網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)生命。有損壓縮方法可分為基于概率模型[3]、基于時間序列分析模型[4]、基于數(shù)據(jù)挖掘模型[5]、基于數(shù)據(jù)壓縮模型[6]4類，其共性在于壓縮率高，數(shù)據(jù)還原質(zhì)量依賴于算法實(shí)現(xiàn)的代價。

無損壓縮技術(shù)[7]在數(shù)據(jù)壓縮過程中不允許損失精度，可以保真還原。主要用于文本文件、數(shù)據(jù)庫、程序數(shù)據(jù)和特殊應(yīng)用場合的圖像數(shù)據(jù)(如指紋圖像、醫(yī)學(xué)圖像)等壓縮。游程長度編碼[8]通過去除文本中的冗余字符或字節(jié)中的冗余位，達(dá)到減少數(shù)據(jù)文件所占的存儲空間的目的，其壓縮效能取決于整個數(shù)據(jù)流的重復(fù)字符出現(xiàn)次數(shù)、平均游程長度以及所采用的編碼結(jié)構(gòu)。由于該算法是針對文件的某些特點(diǎn)所設(shè)計的，具有一定的局限性。G?del[9]提出一種不依賴于數(shù)據(jù)庫的無損壓縮方法，稱為哥德爾數(shù)方法，但其使用范圍局限于對圖靈機(jī)程序的壓縮，因此不具有普遍性。

本文提出了CSNB(Compress sequence number-Binary)壓縮算法，通過增加校驗(yàn)位的形式實(shí)現(xiàn)壓縮。

1 壓縮排序數(shù)

1.1 CSNB

定義1 對于任意序列，其對應(yīng)的最小字長的二進(jìn)制序列為原序列的CSNB序列。

例：若序列為1，3，2，6，5，4，則CSNB序列為001，011，010，110，101，100。

定義2 任意1到n的全排列序列，通過式(1)計算得到的二進(jìn)制數(shù)為此序列的奇偶校驗(yàn)碼CSNBc：

⊕

(1)

式中：N⊕表示在二進(jìn)制數(shù)N中每位依次求異或所得到的值；CSNBi為CSNB序列中的第i個數(shù)。

例：若序列為1，3，2，6，5，4，CSNB序列為001，011，010，110，101，100，則奇偶校驗(yàn)碼的計算過程為：

001⊕=1；011⊕=0；010⊕=1；

110⊕=0；101⊕=0；100⊕=1

CSNBc為100101。

定義3 任意CSNB序列，通過式(2)計算所得的值為CSNB序列的前序錯位求和部分CSNF。

(2)

定義4 任意CSNB序列，通過式(3)計算所得的值為CSNB序列的后序錯位求和部分CSNA。

(3)

定義5 任意CSNB序列，通過式(4)計算所得的值為CSNB序列的CSNB。

10n×CSNA+CSNBc

(4)

因?yàn)镃SNB序列為二進(jìn)制序列，所以式(4)為二進(jìn)制計算。

例：CSNB序列為：001，011，010，110，101，100

10n×CSNA+CSNBc=101111×

(100×1+101×11+1010×10+

1011×110+10100×101+10101×100)+

10110×(100×100+101×101+1010×110+

1011×10+10100×11+10101×1)+

100101=10000111110000110100101

1.2 CSNB與原序列的比較

原序列以十進(jìn)制的方式記錄排序序列。計算機(jī)對十進(jìn)制數(shù)常用的編碼方式是BCD碼，以16位計算機(jī)為例，在記錄十進(jìn)制數(shù)時計算機(jī)會為每個十進(jìn)制數(shù)預(yù)留16位。而CSNB序列是以二進(jìn)制的方式記錄排序序列，計算機(jī)在記錄時不需要編碼轉(zhuǎn)換。其對比結(jié)果如表1所示。

原序列、CSNB序列以及CSNB都具有記錄序列的功能，其空間復(fù)雜度對比結(jié)果如表2所示(計算機(jī)為k位)。

表1 原序列與CSNB序列的比較Table 1 Comparison of original sequence and sequence CSNB

表2 CSN序列、CSNB序列以及CSNB占用空間對比Table 2 CSN sequence,CSNB sequence and CSNB space comparison bit

由表2可知，當(dāng)序列長度n≤8時，CSNB序列較CSNB有更好的空間利用率，且CSNB序列并沒有進(jìn)行改裝壓縮，所以也不需要繁瑣的解壓過程，但當(dāng)8

2 CSNB解壓

2.1 創(chuàng)建決策樹

定義6 如果一個節(jié)點(diǎn)N的奇偶校驗(yàn)碼為N⊕1，其祖先節(jié)點(diǎn)要求的奇偶校驗(yàn)碼為1，且N⊕1≠1，則剪枝發(fā)生在該節(jié)點(diǎn)之上，此時，稱該剪枝過程為奇剪枝。

定義7 如果一個節(jié)點(diǎn)N的奇偶校驗(yàn)碼為N⊕1，其祖先節(jié)點(diǎn)要求的奇偶校驗(yàn)碼為0，且N⊕1≠0，則剪枝發(fā)生在該節(jié)點(diǎn)之上，此時，稱該剪枝過程為偶剪枝。

定義8 如果一個在第n層(根節(jié)點(diǎn)為第0層)的節(jié)點(diǎn)N與回溯到根節(jié)點(diǎn)中所有遍歷到的節(jié)點(diǎn)進(jìn)行式(3)的計算，得到結(jié)果的倒數(shù)第n位為C，其祖先節(jié)點(diǎn)要求的01校驗(yàn)碼為1，且C≠1，則剪枝發(fā)生在該節(jié)點(diǎn)之上，此時，稱該剪枝過程為1剪枝。

定義9 如果一個在第n層(根節(jié)點(diǎn)為第0層)的節(jié)點(diǎn)N與回溯到根節(jié)點(diǎn)中所有遍歷到的節(jié)點(diǎn)進(jìn)行式(3)的計算，得到結(jié)果的倒數(shù)第n位為C，其祖先節(jié)點(diǎn)要求的01校驗(yàn)碼為0，且C≠0，則剪枝發(fā)生在該節(jié)點(diǎn)之上，此時，稱該剪枝過程為0剪枝。

性質(zhì)1 由于奇偶剪枝不需要累加運(yùn)算，且在選定下一節(jié)點(diǎn)時可直接計算，并且奇偶剪枝針對的是真實(shí)的排序值，所以奇偶剪枝較01剪枝速度更快、效率更高。

雖然通過決策樹的剪枝方法能夠刪掉大多數(shù)非解節(jié)點(diǎn)，但剪枝后的決策樹仍然可能存在多個所在層為n的葉子節(jié)點(diǎn)，所以還需要通過CSNA對所有可能解進(jìn)行檢驗(yàn)。

例：CSNB序列為：001，011，010，110，101，100，CSNB=100001111100101，其剪枝策略如圖1所示，先進(jìn)行奇偶校驗(yàn)，再進(jìn)行01校驗(yàn)。其中，“奇×”、“偶×”、“1×”和“0×”分別表示進(jìn)行奇剪枝、偶剪枝、1剪枝和0剪枝操作。

圖1 剪枝策略示意圖Fig.1 Pruning strategy schematic

2.2 CSNB解壓算法

創(chuàng)建決策樹是從邏輯的角度分析算法的執(zhí)行過程，本質(zhì)上解壓算法并不需要構(gòu)建決策樹。決策樹在選擇節(jié)點(diǎn)時，是通過剪枝策略來判斷其選擇的節(jié)點(diǎn)是否正確，從邏輯角度來說，是嘗試著確定CSNBi的位置。

根據(jù)式(2)求CSNBi，本質(zhì)上是在求以CSNB1，CSNB2，…，CSNBn為未知數(shù)，方程CSNF=20×CSNB1+21×CSNB2+…+2n-1×CSNBn(方程為十進(jìn)制方程)的解，其中當(dāng)i≠j時，CSNi≠CSNj且1≤CSNi≤n。

而決策樹是在明確CSNBi值的情況下，去求其位置，即為求以x1,x2,…,xn為未知數(shù)，方程CSNF=2x1×CSNB1+2x2×CSNB2+…+2xn×CSNBn(方程為十進(jìn)制)的解，其中當(dāng)i≠j時，xi≠xj且1≤xi≤n-1。

根據(jù)以上分析，可制定CSNB解壓算法的步驟如下所示。

(1)建立記錄所有未知數(shù)狀態(tài)的未知數(shù)狀態(tài)表(Statetable)，所有未知數(shù)的初始狀態(tài)是Uncertain。若未知數(shù)個數(shù)為n，則未知數(shù)的其他可能狀態(tài)數(shù)為[1,n]中的整數(shù)。

(2)從Statetable中提取一個未被測試過的且狀態(tài)為Uncertain的未知數(shù)，并執(zhí)行第(3)步。如果不存在符合條件的未知數(shù)，則執(zhí)行第(5)步。

(3)將選定的未知數(shù)依次通過奇偶檢驗(yàn)和01檢驗(yàn)，如果都通過，則執(zhí)行第(4)步；否則，將此未知數(shù)視為已檢測狀態(tài)，并執(zhí)行第(2)步。

(4)將選定的未知數(shù)的初始狀態(tài)更改為未被選定的狀態(tài)中最小的狀態(tài)數(shù)，將其他狀態(tài)為Uncertain的未知數(shù)均視為未被測試狀態(tài)，執(zhí)行第(2)步。

(5)若Statetable中仍存在狀態(tài)為Uncertain的未知數(shù)，則將狀態(tài)數(shù)最大的未知數(shù)以及之后的未知數(shù)狀態(tài)設(shè)定為Uncertain，將之后的未知數(shù)視為未檢測狀態(tài)，并繼續(xù)執(zhí)行第(2)步；否則執(zhí)行第(6)步。

(6)通過CSNA判斷找到的可能解的正確性，若正確，算法結(jié)束；否則，將狀態(tài)數(shù)最大的未知數(shù)以及之后的未知數(shù)狀態(tài)設(shè)定為Uncertain，將之后的未知數(shù)視為未檢測狀態(tài)，并執(zhí)行第(2)步。

3 系統(tǒng)測試及結(jié)果分析

3.1 解的唯一性正向檢驗(yàn)

所謂正向檢驗(yàn)，就是給定任意排列的CSNB，由CSNB解其原序列，若解唯一，不僅能說明CSNB系統(tǒng)的正確性，還能檢驗(yàn)解壓算法的正確性。

任意長度為n的CSNB序列，其全排列的總數(shù)為n!，當(dāng)n=9時，一共有9!=362880種排列情況，一一測試是不合理的，所以當(dāng)1

表3 正向檢驗(yàn)解的唯一性Table 3 Positive test uniqueness of the solution

由表3可知，CSNA的查錯率更高。假設(shè)沒有奇偶校驗(yàn)和沒有CSNA校驗(yàn)的多解率符合某種概率分布，且是相互獨(dú)立的，則當(dāng)5

3.2 解的唯一性反向檢驗(yàn)

所謂反向檢驗(yàn)，就是給定任意排列的CSNB，計算是否存在一個不同的CSNB序列的CSNB與其相同，若存在則解不唯一；若不存在則解唯一。通過對比正向檢驗(yàn)和反向檢驗(yàn)的結(jié)果可知解壓算法的正確性。

任意長度為n的CSNB序列，其全排列的總數(shù)為n!，通過與其所有不同的CSNB序列作對比，其比較次數(shù)為n!!。當(dāng)n=9時，一共有9!!=362880!次比較，這樣測試是不合理的，所以采用與正向檢驗(yàn)相同的方法對其進(jìn)行反向檢驗(yàn)，即當(dāng)1

表4 反向檢驗(yàn)解的唯一性Table 4 Uniqueness of the solution of reverse test

4 結(jié)束語

研究了排序序列的記錄及存儲方式，提出了CSNB的存儲方式，CSNB中包含有前序錯位求和CSNF、后序錯位求和CSNA以及奇偶校驗(yàn)碼3部分。CSNB通過對排序序列進(jìn)行壓縮，其空間復(fù)雜度為O(log2n+n)。通過解壓算法可找到對應(yīng)的原序列，實(shí)現(xiàn)序列還原。CSNB的壓縮不僅可以使其具有更好的空間利用率，而且能夠增加信息傳遞的可靠性。

參考文獻(xiàn)：

[1] Deligiannakis A，Kotidis Y，Roussopoulos N. Dissemination of compressed historical information in sensor networks[J]. The VLDB Journal，2007，16(4)：439-461.

[2] 張建明，林亞平，周四望，等. 傳感器網(wǎng)絡(luò)中誤差有界的小波數(shù)據(jù)壓縮算法[J]. 軟件學(xué)報，2010，21(6)：1364-1377.

Zhang Jian-ming，Lin Ya-ping，Zhou Si-wang，et al. Haar wavelet data compression algorithm with error bound for wireless sensor networks[J]. Journal of Software，2010，21(6)：1364-1377.

[3] Chu D，Deshpande A，Hellerstein J M，et al. Approximate data collection in sensor networks using probabilistic models[C]∥Proceedings of the 22nd International Conference on Data Engineering，Atlanta，USA，2006：48-59.

[4] Najafi H，Lahouti F，Shiva M. AR modeling for temporal extension of correlated sensor network data[C]∥International Conference on Software in Telecommunications and Computer Networks,Split, Croatia,2006：117-120.

[5] Borgne Y L，Bontempi G. Unsupervised and supervised compression with principal component analysis in wireless sensor networks[C]∥13th ACM International Conference on Knowledge Discovery and Data Mining，New York，USA，2007：94-103.

[6] Ganesan D，Estrin D，Heidemann J. DIMENSIONS：Why do we need a new data handling architecture for sensor networks?[J]. ACM SIGCOMM Computer Communication Review,2003，33(1)：143-148.

[7] 鄭翠芳. 幾種常用無損數(shù)據(jù)壓縮算法研究[J]. 計算機(jī)技術(shù)與發(fā)展，2011，21(9)：73-76.

Zheng Cui-fang. Research of several common lossless data compression algorithms[J]. Computer Technology and Development，2011，21(9)：73-76.

[8] Tsang P，Liu J P，Cheung K. Modern methods for fast generation of digital holograms[J]. 3D Research，2010，1(2):11-18.

[9] G?del K. über formal unentscheidbare S?tze der Principia Mathematica und Verwandter Systeme I[J]. Mathematics and Statistics，1931，38(1)：173-198.