陳勇強，陳 亮，成 偉，梁 巍

（電子科技大學機械電子工程學院，四川成都 611731）

管道運輸是國民經(jīng)濟綜合運輸?shù)闹匾M成部分之一。然而，隨著管道的長期運行，泄漏、爆炸等事故頻頻發(fā)生，因此對管道的無損檢測是很重要的［1－3］。目前常采用的管道在線無損檢測方法有超聲檢測和漏磁檢測。管道漏磁檢測的數(shù)據(jù)往往是非常龐大的，而管道內(nèi)的容量往往又非常有限，必須對采集的數(shù)據(jù)進行壓縮，為了便于對數(shù)據(jù)進行后期整理與分析，通常采用無損壓縮形式對數(shù)據(jù)進行壓縮以使數(shù)據(jù)無失真地還原出來［4－5］。常用的無損壓縮算法有很多，比如LZW（Lempel、Ziv、Welch）、算術(shù)編碼、游程編碼以及比較流行的WINZIP壓縮包。LZW 無損壓縮算法采用了基于字典存儲技術(shù)，能夠獲得極高的壓縮率，特別適用于文本數(shù)據(jù)的無損壓縮［6］。

本文中將LZW 算法應(yīng)用于管道的漏磁檢測，對漏磁無損檢測實驗數(shù)據(jù)進行壓縮處理。

1 LZW 算法的原理

LZW 核心思想就是用短的編碼代替相對較長的字符串，它不對輸入的字符串作任何分析，只是將收到的每一個新字符串添加到一個字典中，當已經(jīng)出現(xiàn)的字符串再次出現(xiàn)時，即用一個短的編碼代替該字符串，這樣就實現(xiàn)了壓縮。LZW 算法輸出的編碼可以是任意長度的，但必須大于一個字符的編碼長度。開始256個編碼（0～255）默認給標準字符，余下的編碼在處理過程中會被分配給其他的字符串。本設(shè)計采用12位的編碼，這意味著0～255項指定給256個標準的獨立字符，而256～4 096 編碼指定給子字串［7－9］。LZW 總是輸出已知的字符串。每當出現(xiàn)新的字符串，新的字符串將被添加到字符串表中。

2 LZW 字典的管理、維護與更新

LZW 字典需要存儲的內(nèi)容包括3個部分：前綴碼（PREFIX＿CODE）、后綴碼（SUFFIX＿CODE）和字典項編碼（INDEX＿CODE）。其中，前綴碼為12位，后綴碼為8位，字典項編碼為12位，字典存儲器的總數(shù)據(jù)寬度為32位。該存儲器的深度設(shè)計為4 099，即存儲器的容量為32×4 099。字典建立后，首先初始化前面的256項，即將256個標準的ASCII碼字符按照順序依次存儲到字典的前256個位置，然后把第257項和第258項分別初始化給CLEAR 和END 標志位。CLEAR 代表字典將存滿，要對字典進行清除；END表示沒有字符輸入，結(jié)束整個LZW 壓縮過程。初始化完畢后，接收輸入數(shù)據(jù)，當字符串出現(xiàn)在字典中時，則不輸出碼字，而是接著讀下一個字符。當新出現(xiàn)的字符串沒在字典中時，則將該新字符串加入到字典里面，同時輸出該字符串的前綴碼。當字典存滿時，則將字典更新，也即將字典256項以后的257～4 099項全部清零，而前面256項保留。例如當初始化LZW 字典完畢后，接收的輸入字符數(shù)據(jù)依次為ABCD 時，首先接收第一個數(shù)據(jù)，也即A，判斷是否在字典里面，顯然A 在第65項，因為所有的256個標準字符都已經(jīng)按照順序存儲在字典中，所以不輸出碼字，接著接收下一個字符B，此時的字符串就變成了AB，而AB 沒有在字典中，那么此時將字符串AB 存入到字典中的第257項，再輸出AB 的前綴編碼A，即97。以此類推，完成后面字符串的壓縮與存儲［10－11］。

LZW 算法中采用哈希表（Hash）的方式對字典進行管理。哈希表又稱為散列表，哈希表存儲的基本思想是：以數(shù)據(jù)表中的每個記錄的關(guān)鍵字K 為自變量，通過一種函數(shù)H（K）計算出函數(shù)值。把這個值解釋為一塊連續(xù)存儲空間（即數(shù)組空間）的單元地址（即下標），將該記錄存儲到這個單元中。在此稱該函數(shù)H為哈希函數(shù)或散列函數(shù)，按這種方法建立的表稱哈希表或散列表。其存儲原理不會將代碼258 的字符串存儲到數(shù)組中258的位置上，而是在數(shù)組中存放的位置由字符串本身來決定［12－13］。當需要定位一個給定的字符串時，就檢查這個字符串生成的哈希地址，如果順利的話，第一次即可找到所需的位置。

哈希函數(shù)的選擇非常重要，不僅要有利于檢索，盡可能簡單，而且要盡可能地避免沖突。首先建立一個哈希函數(shù)INDEX＝H（K）；在字典的字符串的哈希地址INDEX 和它的關(guān)鍵字K 之間建立一個一一對應(yīng)的確定函數(shù)關(guān)系，從而使得每個關(guān)鍵字K 和它在字典中的存儲位置一一對應(yīng)，本設(shè)計采用的哈希函數(shù)為：

其中：＜＜為左移運算；｜｜為或運算；%為取余運算；INDEX為哈希表地址，它是一個13位的寄存器變量；PREFIX 為前綴碼，它是一個18 位的寄存器變量；SUFFIX為后綴碼，也就是當前碼，它是一個8位的寄存器變量；TABLE＿SIZE 為哈希表長度，在這里設(shè)定為4 099；OFFSET 為偏移量（為解決哈希沖突而選擇的一個中間量），在這里設(shè)定為13。

字典的存儲步驟：首先將前綴碼PREFIX 左移8位，然后與后綴碼SUFFIX（也就是當前碼或者當前輸入字符）進行或的操作；然后對字典長度進行取余運算，以作為該前綴的哈希地址；再把該字符串添加到串表中，當出現(xiàn)沖突時（就是說該地址已經(jīng)有存儲），按式（2）計算，直到?jīng)]有沖突為止。

為了盡量避免沖突，TABLE＿SIZE 應(yīng)該比212大，且應(yīng)該為質(zhì)數(shù)，因此本設(shè)計采用的TABLE＿SIZE 為4 099。一方面能夠正常實現(xiàn)字典的存儲與更新，還能夠避免哈希沖突和節(jié)省存儲器容量。

當字典存滿時，就需要對字典進行維護，當檢測到字典已經(jīng)存滿時，就對字典255以后的所有字典項進行清零，而前面的0～255項保持不變，再重新進行輸入數(shù)據(jù)的壓縮和字典的存儲。表1是輸入數(shù)據(jù)為字符串AAAAAAAAAAAAAAAA 時整個壓縮過程的詳解。從表1 中可以看出，輸出編碼依次為65、258、259、260、261、65。圖1是調(diào)用ModelSim 對該字符串仿真的仿真結(jié)果圖。

表1 字符串AAAAAAAAAAAAAAAA的壓縮詳解

表1（續(xù)）

在圖1中：RST為使能信號，RST為1時執(zhí)行數(shù)據(jù)的壓縮；CLK 為時鐘，上升沿有效；COUNT 為計數(shù)器，即輸入數(shù)據(jù)的字節(jié)數(shù)；CHAR 為當前輸入字符；OUT＿CODE為輸出編碼。從圖1中可以看出，輸出編碼依次為65、258、259、260及65。與上面分析的結(jié)果一致，從而驗證了本設(shè)計LZW 算法壓縮功能的正確性。

圖1 字符串AAAAAAAAAAAAAAAA的仿真結(jié)果圖

3 LZW 壓縮算法在管道漏磁檢測中的應(yīng)用

管道漏磁檢測系統(tǒng)包含探頭子系統(tǒng)、控制子系統(tǒng)、數(shù)據(jù)采集子系統(tǒng)和其他相關(guān)機構(gòu)。探頭子系統(tǒng)包括磁路，16個霍爾傳感器和信號預(yù)處理電路。由直流電動機、調(diào)速控制器和2個繼電器構(gòu)成的控制子系統(tǒng)是用來控制探頭的運動。數(shù)據(jù)采集子系統(tǒng)主要部分包括PC機和數(shù)據(jù)采集儀。漏磁數(shù)據(jù)無損壓縮系統(tǒng)框圖如圖2所示。

圖2 漏磁數(shù)據(jù)無損壓縮系統(tǒng)框圖

在厚度是12mm 的試樣上做不同的人工矩形缺陷，這些缺陷深度都是試樣壁厚的50%（6mm），缺陷長度和寬度見表2。第10個傳感器采集到的漏磁信號如圖3所示。

表2 矩形缺陷參數(shù)

圖3 漏磁信號的徑向分量

實驗室采集得來的漏磁數(shù)據(jù)的大小如圖4所示。

圖4 實驗室采集得來的漏磁數(shù)據(jù)大小

從圖4中可以看出，漏磁數(shù)據(jù)大小為458 750個字節(jié)。對該漏磁數(shù)據(jù)進行壓縮仿真的結(jié)果如圖5 所示。壓縮后的數(shù)據(jù)大小如圖6所示。

圖5 實驗室漏磁數(shù)據(jù)壓縮仿真圖

圖6 漏磁數(shù)據(jù)壓縮后的大小示意圖

4 結(jié)論

從仿真結(jié)果可看出，漏磁數(shù)據(jù)壓縮前的大小為458 750個字節(jié)，而壓縮后的字節(jié)數(shù)為85 433個字節(jié)，漏磁數(shù)據(jù)經(jīng)過LZW 算法壓縮后的壓縮率為18.62%，即壓縮到了原來數(shù)據(jù)量的20%不到，這樣便節(jié)省了80%多的存儲空間。這種壓縮效率是很高的，如果應(yīng)用在實際的管道漏磁數(shù)據(jù)的實時壓縮中，將大大地節(jié)省存儲器資源和降低經(jīng)濟成本，意義是很大的。

（

）

［1］曾小紅，陳亮，李興.漏磁信號處理中的經(jīng)驗?zāi)B(tài)分解和能量法閾值的研究［J］.無損檢測，2011，33（3）：27－30.

［2］李迅波，李翔，陳亮，等.鋼管相鄰缺陷漏磁場相互影響的分析［J］.電子科技大學學報，2008，37（5）：797－800.

［3］楊理踐.管道漏磁在線檢測技術(shù)［J］.沈陽工業(yè)大學學報，2005，27（5）：522－525.

［4］楊理踐，王大為，高松巍.管道漏磁檢測數(shù)據(jù)壓縮算法的研究［J］.沈陽工業(yè)大學學報，2006，28（6）：628－631.

［5］Chen L，Li X B，Qin G X，et al.Signal Processing of Magnetic Flux Leakage Surface Flaw Inspect in Pipeline Steel［J］.Russian Journal of Nondestructive Testing，2008，44（12）：859－867.

［6］袁枚，袁文.數(shù)據(jù)壓縮技術(shù)及其應(yīng)用［M］.北京：電子工業(yè)出版社，1995.

［7］Tsiskaridze Vakhtang.Lossless compression of ATLAS Tile Calorimeter raw data［J］.Journal of Physics：Conference Series，2010，219（1）：4－7.

［8］王方，馮玲.無損壓縮算法LZW 研究與實現(xiàn)［J］.科技創(chuàng)新導報，2008，12（1）：77－78.

［9］Lakhani Gopal.Reducing coding redundancy in LZW［J］.Information Sciences.2006，176（10）：1417－1434.

［10］Lossless Data Compression.CCSDS 120.0－B－1.Blue Book［M］.Issue 1，Washington，D.C.：CCSDS，1997.

［11］尹云，劉波峰，徐勇，等.核電現(xiàn)場超聲無損檢測數(shù)據(jù)壓縮［J］.計算機系統(tǒng)應(yīng)用，2011，20（4）：118－121.

［12］黃賢武，王加俊，李家華.數(shù)字圖像處理與壓縮編碼技術(shù)［M］.成都：電子科技大學出版社，2000.

［13］Nelson M.數(shù)據(jù)壓縮技術(shù)原理與范例［M］.賈起東，譯.北京：科學出版社，1995.