基于LZW算法的聲波測(cè)井?dāng)?shù)據(jù)壓縮研究

鄒學(xué)玉，馮振，張少華，韓付偉

（長江大學(xué)電子信息學(xué)院，湖北 荊州 434023）

0 引 言

目前，井下傳輸系統(tǒng)的帶寬擴(kuò)容速度遠(yuǎn)遠(yuǎn)不及聲波測(cè)井?dāng)?shù)據(jù)的增長速度，且傳輸系統(tǒng)的帶寬不可能無限制增長。因此，必須對(duì)井下聲波測(cè)井?dāng)?shù)據(jù)進(jìn)行壓縮。不少的研究方法都是基于軟件壓縮，其缺點(diǎn)是壓縮速度慢，不適用于對(duì)大量數(shù)據(jù)進(jìn)行實(shí)時(shí)壓縮。壓縮數(shù)據(jù)總目標(biāo)是要減少容納給定消息集合的信號(hào)空間。存儲(chǔ)空間的減少意味著傳輸效率的提高和占用頻帶的節(jié)省，這就提高了在有限傳輸帶寬的情況下測(cè)井?dāng)?shù)據(jù)的傳輸效率。目前對(duì)聲波測(cè)井?dāng)?shù)據(jù)的壓縮方法：有損壓縮算法預(yù)測(cè)編碼與小波變換相結(jié)合［1］；SPIHT 算法［2］；FLAC 算法；APE 算法［11］；幀相關(guān)壓縮算法［3］；LZW 壓縮方法［4］等。但上述不少編碼是基于數(shù)據(jù)源的統(tǒng)計(jì)概率特性和軟件的?；诮y(tǒng)計(jì)概率的信源編碼是Shannon信息論的基本特征，但是在某些需要實(shí)施壓縮的場(chǎng)合，要確定實(shí)際信源的統(tǒng)計(jì)特性相當(dāng)困難。

本文提出了引入哈希函數(shù)的LZW算法，它是基于數(shù)據(jù)串特性的編碼方法，不依賴于信源統(tǒng)計(jì)特性的編碼方法稱為通用碼［5］。LZW是基于字典的無損壓縮編碼，試驗(yàn)證明，LZW算法和Hash函數(shù)相結(jié)合，不僅壓縮效率高，而且易于用硬件實(shí)現(xiàn)。

1 LZW算法

LZW是一種基于字典的算法。所謂字典算法，即認(rèn)為信源輸出的信息序列是由一本字典中的各種詞條構(gòu)成的。顯然，該字典的詞條應(yīng)由信源符號(hào)的不同排列組合產(chǎn)生。但該字典不是固定不變，而是根據(jù)信源發(fā)出的編碼動(dòng)態(tài)建立。編碼過程也就是建立字典的過程。如果接收端建立的字典與發(fā)送端一樣，就達(dá)到了正確的信息傳送目的。

LZW算法是Terry A.Welch 1984年在LZ78的基礎(chǔ)上加以改進(jìn)提出來的［6］。該算法速度快，壓縮率高，最重要的是不需要知道待壓縮數(shù)據(jù)的概率統(tǒng)計(jì)特性。LZW算法通過字典，把輸入的字符串映射成等長碼字輸出。LZW算法的字典具有前綴特性，這樣就使得任何一個(gè)字典中的字符串的前綴也一定在字典中。例如：如果一個(gè)字符串是WK，其中W是一個(gè)字符串，K是單個(gè)字符，如果WK在字典中，那么W也一定在字典中。

LZW算法對(duì)每個(gè)輸入字符串進(jìn)行逐個(gè)字符檢查，試圖找到最長的和字典已有字符串匹配的字符串并進(jìn)行解析，這樣字典內(nèi)的編碼項(xiàng)會(huì)越來越多，匹配幾率也會(huì)隨之增大，從而達(dá)到壓縮目的。每個(gè)被解析了的字符串通過下一個(gè)輸入字符擴(kuò)展，這樣形成的新字符串會(huì)被存入字典，新字符串會(huì)有一個(gè)新的標(biāo)示符，稱為編碼值，并且同時(shí)輸出前綴碼也就是W的編碼值［6］。LZW編碼流程見圖1。

圖1 LZW算法流程圖

2 Hash函數(shù)

由于傳統(tǒng)LZW算法每次需要查找當(dāng)前詞條是否與字典已有詞條匹配，如果對(duì)逐個(gè)詞條進(jìn)行查找，查找效率勢(shì)必非常低，從而影響壓縮速率。因此，本文引入了Hash函數(shù)，利用哈希查找，只要根據(jù)對(duì)應(yīng)函數(shù)找到給定值K的像h（K）。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在h（K）的存儲(chǔ)位置上，由此，不需要進(jìn)行比較便可直接取得所查記錄。在此，稱這個(gè)對(duì)應(yīng)關(guān)系h為哈希（Hash）函數(shù)，據(jù)此建立的表為哈希表（Hash table）。

然而，對(duì)不同關(guān)鍵字可能得到同一哈希地址，即key1≠key2，而h（key1）＝h（key2），這種現(xiàn)象稱沖突（collision）。因此，在建造哈希表時(shí)不僅要設(shè)定一個(gè)哈希函數(shù)，而且要設(shè)定一種處理沖突的方法［7］。

假設(shè)消息M的長度是L。將M分成為n位的塊，其中n?L，p＝［L／n］，則M＝（m1，m2，…，mp），mj表示第j塊，其中mp塊不足n位用0填充。

將第j塊mj寫成行向量

式中，mji是一個(gè)位。將這些向量堆放在一起形成一個(gè)矩陣。散列函數(shù)h（M）輸出n位，第i位是將矩陣的第i列的所有位進(jìn)行異或得到的，即ci＝m1i⊕m2i⊕…⊕mli可以表示為

因此，在本文中實(shí)際用于壓縮的哈希函數(shù)采用移位和基本算數(shù)運(yùn)算構(gòu)造，這樣使得哈希函數(shù)不僅運(yùn)算速度快，易于實(shí)現(xiàn)，而且從理論上證明了比特之間的異或運(yùn)算和位移運(yùn)算能夠提高哈希值的隨機(jī)特性［8］。哈希函數(shù)如式（3），其中code表示當(dāng)前字符，pre＿code表示前綴字符（串）［9］。

為了減少哈希函數(shù)沖突的發(fā)生，在實(shí)際壓縮時(shí)定義了一個(gè)偏移量，通過探測(cè)再散列來解決哈希函數(shù)的沖突問題。

3 壓縮測(cè)試及結(jié)果分析

3.1 Hash函數(shù)測(cè)試結(jié)果

本文從哈希值的期望、方差、非空桶深期望、非空桶深方差、ASL（平均查找長度）、最大桶深、空桶率、沖突率［10］等方面對(duì)哈希函數(shù)的性能進(jìn)行了測(cè)試，測(cè)試結(jié)果如表1至表3所示。

表1 字典深度為512B

表2 字典深度為1kB

表3 字典深度為1kB，并加入偏移量減少哈希沖突

從表1至表3可以看出，在字典深度一定的情況下，哈希值期望、方差、非空桶深期望、非空桶深方差與輸入詞條數(shù)目的關(guān)系不大，且比較穩(wěn)定，說明所測(cè)試的異或哈希函數(shù)散列性能好。ASL在字典深度不變的情況下，隨著輸入詞條數(shù)目的增加略微增加，但均不超過2，說明字典的查找效率高。通過最大桶深可以確定字典在沖突發(fā)生幾次后清空字典。

最后從空桶率和沖突率可以看出，沖突率是隨著字典深度的增加而減小，隨著輸入詞條數(shù)目增加而增加的，但如果輸入詞條數(shù)太少，就會(huì)使得字典的利用率降低，通過統(tǒng)計(jì)測(cè)試一般輸入詞條數(shù)一般控制在字典深度的70%～75%。這樣既能保證空桶率低于50%，又能保證沖突率低于20%。

3.2 數(shù)據(jù)壓縮測(cè)試結(jié)果

本文測(cè)試的是井下聲波測(cè)井?dāng)?shù)據(jù)，共有4大幀數(shù)據(jù)，每大幀數(shù)據(jù)對(duì)應(yīng)1個(gè)深度點(diǎn)的4道波形數(shù)據(jù)。數(shù)據(jù)格式為16進(jìn)制數(shù)。文件為AcData.txt，文件大小為32kB（32 802B）。

壓縮率＝壓縮后數(shù)據(jù)字節(jié)數(shù)／壓縮前數(shù)據(jù)字節(jié)數(shù)，本文中壓縮前數(shù)據(jù)為32 802B，為了節(jié)省存儲(chǔ)空間，字典深度為512B，壓縮后數(shù)據(jù)為16 460B，經(jīng)計(jì)算壓縮率為50.18%，在壓縮率方面要比算術(shù)編碼的壓縮率80%左右，預(yù)測(cè)編碼的壓縮率70%～90%提高不少［11］。

4 結(jié)束語

針對(duì)聲波測(cè)井?dāng)?shù)據(jù)壓縮提出無損壓縮方法，不僅壓縮效率理想，易于軟硬件實(shí)現(xiàn)，而且LZW和哈希函數(shù)的結(jié)合可以獨(dú)立于信源的統(tǒng)計(jì)特性，實(shí)現(xiàn)實(shí)時(shí)無損壓縮。該方法為硬件壓縮系統(tǒng)的實(shí)現(xiàn)提供了參考，在測(cè)井?dāng)?shù)據(jù)大幅增長的情況下具有很好的應(yīng)用前景。

［1］李傳偉，慕德俊，李安宗，等.隨鉆聲波測(cè)井?dāng)?shù)據(jù)實(shí)時(shí)壓縮算法 ［J］.西南石油大學(xué)學(xué)報(bào)，2008，30（5）：81-84.

［2］張偉，師欒兵.聲波測(cè)井?dāng)?shù)據(jù)壓縮的一種SPIHT改進(jìn)算法 ［J］.電子測(cè)量與儀器學(xué)報(bào)，2008，22（1）：15-19.

［3］漢澤西，郭楓，秦李顆.一種基于測(cè)井?dāng)?shù)據(jù)特征的無損壓縮方法 ［J］.西安石油大學(xué)學(xué)報(bào)，2006，21（1）：61-63.

［4］劉付斌，李艾華.偶極子數(shù)字陣列聲波測(cè)井儀中數(shù)據(jù)壓縮的實(shí)現(xiàn) ［J］.設(shè)計(jì)與研發(fā)，2007，12：58-61.

［5］Knuth D E.The Art of Computer Programming，volume 1／Fundamental Algorithms；volume3／Sorting and Searching［M］.USA：Addison-Wesley，1973.

［6］Welch T A.A Technique for High-performance Data Compression［J］.IEEE Computer，1984，17（6）：8-18.

［7］Wade Trappe，Lawrence C Washington.Introduction to Cryptography with Coding Theory：Second Edition［M］.USA：Pearson Education，Inc.，publishing as Prentice Hall，2002.

［8］程光，龔儉，丁偉，等.面向IP流測(cè)量的哈希算法的研究 ［J］.軟件學(xué)報(bào)，2005，16（5）：652-658.

［9］Li Leiding，Ma Tiehua.FPGA-based Implementation of LZW Algorithm ［J］.Electronic Measurement Technology，2008，31（10）：170-172.

［10］林亞平.異或哈希函數(shù)查找中文詞組性能評(píng)價(jià) ［J］.中文信息學(xué)報(bào)，1995，9（1）：42-48.

［11］賈安學(xué)，喬文孝，鞠曉東，等.聲波測(cè)井井下數(shù)據(jù)壓縮算法壓縮效果測(cè)試 ［J］.測(cè)井技術(shù)，2011，35（3）：288-291.