基于有限序列的壓縮新算法

趙宏偉，劉宇琦，特日根，陳長(zhǎng)征，臧雪柏,3

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

0 引 言

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

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

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

1 壓縮排序數(shù)

1.1 CSNB

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

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

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

⊕

(1)

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

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

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

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

CSNBc為100101。

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

(2)

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

(3)

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

10n×CSNA+CSNBc

(4)

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

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

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

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

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

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

2 CSNB解壓

2.1 創(chuàng)建決策樹(shù)

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

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

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

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

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

雖然通過(guò)決策樹(shù)的剪枝方法能夠刪掉大多數(shù)非解節(jié)點(diǎn)，但剪枝后的決策樹(shù)仍然可能存在多個(gè)所在層為n的葉子節(jié)點(diǎn)，所以還需要通過(guò)CSNA對(duì)所有可能解進(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)建決策樹(shù)是從邏輯的角度分析算法的執(zhí)行過(guò)程，本質(zhì)上解壓算法并不需要構(gòu)建決策樹(shù)。決策樹(shù)在選擇節(jié)點(diǎn)時(shí)，是通過(guò)剪枝策略來(lái)判斷其選擇的節(jié)點(diǎn)是否正確，從邏輯角度來(lái)說(shuō)，是嘗試著確定CSNBi的位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

研究了排序序列的記錄及存儲(chǔ)方式，提出了CSNB的存儲(chǔ)方式，CSNB中包含有前序錯(cuò)位求和CSNF、后序錯(cuò)位求和CSNA以及奇偶校驗(yàn)碼3部分。CSNB通過(guò)對(duì)排序序列進(jìn)行壓縮，其空間復(fù)雜度為O(log2n+n)。通過(guò)解壓算法可找到對(duì)應(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é)報(bào)，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] 鄭翠芳. 幾種常用無(wú)損數(shù)據(jù)壓縮算法研究[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.