鄒學玉，馮振，張少華，韓付偉

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

0 引 言

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

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

1 LZW算法

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

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

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

圖1 LZW算法流程圖

2 Hash函數(shù)

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

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

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

將第j塊mj寫成行向量

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

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

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

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

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

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

表1 字典深度為512B

表2 字典深度為1kB

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

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

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

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

本文測試的是井下聲波測井數(shù)據(jù)，共有4大幀數(shù)據(jù)，每大幀數(shù)據(jù)對應1個深度點的4道波形數(shù)據(jù)。數(shù)據(jù)格式為16進制數(shù)。文件為AcData.txt，文件大小為32kB（32 802B）。

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

4 結(jié)束語

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

［1］李傳偉，慕德俊，李安宗，等.隨鉆聲波測井數(shù)據(jù)實時壓縮算法 ［J］.西南石油大學學報，2008，30（5）：81-84.

［2］張偉，師欒兵.聲波測井數(shù)據(jù)壓縮的一種SPIHT改進算法 ［J］.電子測量與儀器學報，2008，22（1）：15-19.

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

［4］劉付斌，李艾華.偶極子數(shù)字陣列聲波測井儀中數(shù)據(jù)壓縮的實現(xiàn) ［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流測量的哈希算法的研究 ［J］.軟件學報，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ù)查找中文詞組性能評價 ［J］.中文信息學報，1995，9（1）：42-48.

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