LZW 无损压缩算法在管道漏磁检测中的应用

陈勇强，陈 亮，成 伟，梁 巍

（电子科技大学机械电子工程学院，四川成都 611731）

管道运输是国民经济综合运输的重要组成部分之一。然而，随着管道的长期运行，泄漏、爆炸等事故频频发生，因此对管道的无损检测是很重要的［1－3］。目前常采用的管道在线无损检测方法有超声检测和漏磁检测。管道漏磁检测的数据往往是非常庞大的，而管道内的容量往往又非常有限，必须对采集的数据进行压缩，为了便于对数据进行后期整理与分析，通常采用无损压缩形式对数据进行压缩以使数据无失真地还原出来［4－5］。常用的无损压缩算法有很多，比如LZW（Lempel、Ziv、Welch）、算术编码、游程编码以及比较流行的WINZIP压缩包。LZW 无损压缩算法采用了基于字典存储技术，能够获得极高的压缩率，特别适用于文本数据的无损压缩［6］。

本文中将LZW 算法应用于管道的漏磁检测，对漏磁无损检测实验数据进行压缩处理。

1 LZW 算法的原理

LZW 核心思想就是用短的编码代替相对较长的字符串，它不对输入的字符串作任何分析，只是将收到的每一个新字符串添加到一个字典中，当已经出现的字符串再次出现时，即用一个短的编码代替该字符串，这样就实现了压缩。LZW 算法输出的编码可以是任意长度的，但必须大于一个字符的编码长度。开始256个编码（0～255）默认给标准字符，余下的编码在处理过程中会被分配给其他的字符串。本设计采用12位的编码，这意味着0～255项指定给256个标准的独立字符，而256～4 096 编码指定给子字串［7－9］。LZW 总是输出已知的字符串。每当出现新的字符串，新的字符串将被添加到字符串表中。

2 LZW 字典的管理、维护与更新

LZW 字典需要存储的内容包括3个部分：前缀码（PREFIX＿CODE）、后缀码（SUFFIX＿CODE）和字典项编码（INDEX＿CODE）。其中，前缀码为12位，后缀码为8位，字典项编码为12位，字典存储器的总数据宽度为32位。该存储器的深度设计为4 099，即存储器的容量为32×4 099。字典建立后，首先初始化前面的256项，即将256个标准的ASCII码字符按照顺序依次存储到字典的前256个位置，然后把第257项和第258项分别初始化给CLEAR 和END 标志位。CLEAR 代表字典将存满，要对字典进行清除；END表示没有字符输入，结束整个LZW 压缩过程。初始化完毕后，接收输入数据，当字符串出现在字典中时，则不输出码字，而是接着读下一个字符。当新出现的字符串没在字典中时，则将该新字符串加入到字典里面，同时输出该字符串的前缀码。当字典存满时，则将字典更新，也即将字典256项以后的257～4 099项全部清零，而前面256项保留。例如当初始化LZW 字典完毕后，接收的输入字符数据依次为ABCD 时，首先接收第一个数据，也即A，判断是否在字典里面，显然A 在第65项，因为所有的256个标准字符都已经按照顺序存储在字典中，所以不输出码字，接着接收下一个字符B，此时的字符串就变成了AB，而AB 没有在字典中，那么此时将字符串AB 存入到字典中的第257项，再输出AB 的前缀编码A，即97。以此类推，完成后面字符串的压缩与存储［10－11］。

LZW 算法中采用哈希表（Hash）的方式对字典进行管理。哈希表又称为散列表，哈希表存储的基本思想是：以数据表中的每个记录的关键字K 为自变量，通过一种函数H（K）计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数，按这种方法建立的表称哈希表或散列表。其存储原理不会将代码258 的字符串存储到数组中258的位置上，而是在数组中存放的位置由字符串本身来决定［12－13］。当需要定位一个给定的字符串时，就检查这个字符串生成的哈希地址，如果顺利的话，第一次即可找到所需的位置。

哈希函数的选择非常重要，不仅要有利于检索，尽可能简单，而且要尽可能地避免冲突。首先建立一个哈希函数INDEX＝H（K）；在字典的字符串的哈希地址INDEX 和它的关键字K 之间建立一个一一对应的确定函数关系，从而使得每个关键字K 和它在字典中的存储位置一一对应，本设计采用的哈希函数为：

其中：＜＜为左移运算；｜｜为或运算；%为取余运算；INDEX为哈希表地址，它是一个13位的寄存器变量；PREFIX 为前缀码，它是一个18 位的寄存器变量；SUFFIX为后缀码，也就是当前码，它是一个8位的寄存器变量；TABLE＿SIZE 为哈希表长度，在这里设定为4 099；OFFSET 为偏移量（为解决哈希冲突而选择的一个中间量），在这里设定为13。

字典的存储步骤：首先将前缀码PREFIX 左移8位，然后与后缀码SUFFIX（也就是当前码或者当前输入字符）进行或的操作；然后对字典长度进行取余运算，以作为该前缀的哈希地址；再把该字符串添加到串表中，当出现冲突时（就是说该地址已经有存储），按式（2）计算，直到没有冲突为止。

为了尽量避免冲突，TABLE＿SIZE 应该比212大，且应该为质数，因此本设计采用的TABLE＿SIZE 为4 099。一方面能够正常实现字典的存储与更新，还能够避免哈希冲突和节省存储器容量。

当字典存满时，就需要对字典进行维护，当检测到字典已经存满时，就对字典255以后的所有字典项进行清零，而前面的0～255项保持不变，再重新进行输入数据的压缩和字典的存储。表1是输入数据为字符串AAAAAAAAAAAAAAAA 时整个压缩过程的详解。从表1 中可以看出，输出编码依次为65、258、259、260、261、65。图1是调用ModelSim 对该字符串仿真的仿真结果图。

表1 字符串AAAAAAAAAAAAAAAA的压缩详解

表1（续）

在图1中：RST为使能信号，RST为1时执行数据的压缩；CLK 为时钟，上升沿有效；COUNT 为计数器，即输入数据的字节数；CHAR 为当前输入字符；OUT＿CODE为输出编码。从图1中可以看出，输出编码依次为65、258、259、260及65。与上面分析的结果一致，从而验证了本设计LZW 算法压缩功能的正确性。

图1 字符串AAAAAAAAAAAAAAAA的仿真结果图

3 LZW 压缩算法在管道漏磁检测中的应用

管道漏磁检测系统包含探头子系统、控制子系统、数据采集子系统和其他相关机构。探头子系统包括磁路，16个霍尔传感器和信号预处理电路。由直流电动机、调速控制器和2个继电器构成的控制子系统是用来控制探头的运动。数据采集子系统主要部分包括PC机和数据采集仪。漏磁数据无损压缩系统框图如图2所示。

图2 漏磁数据无损压缩系统框图

在厚度是12mm 的试样上做不同的人工矩形缺陷，这些缺陷深度都是试样壁厚的50%（6mm），缺陷长度和宽度见表2。第10个传感器采集到的漏磁信号如图3所示。

表2 矩形缺陷参数

图3 漏磁信号的径向分量

实验室采集得来的漏磁数据的大小如图4所示。

图4 实验室采集得来的漏磁数据大小

从图4中可以看出，漏磁数据大小为458 750个字节。对该漏磁数据进行压缩仿真的结果如图5 所示。压缩后的数据大小如图6所示。

图5 实验室漏磁数据压缩仿真图

图6 漏磁数据压缩后的大小示意图

4 结论

从仿真结果可看出，漏磁数据压缩前的大小为458 750个字节，而压缩后的字节数为85 433个字节，漏磁数据经过LZW 算法压缩后的压缩率为18.62%，即压缩到了原来数据量的20%不到，这样便节省了80%多的存储空间。这种压缩效率是很高的，如果应用在实际的管道漏磁数据的实时压缩中，将大大地节省存储器资源和降低经济成本，意义是很大的。

（

）

［1］曾小红，陈亮，李兴.漏磁信号处理中的经验模态分解和能量法阈值的研究［J］.无损检测，2011，33（3）：27－30.

［2］李迅波，李翔，陈亮，等.钢管相邻缺陷漏磁场相互影响的分析［J］.电子科技大学学报，2008，37（5）：797－800.

［3］杨理践.管道漏磁在线检测技术［J］.沈阳工业大学学报，2005，27（5）：522－525.

［4］杨理践，王大为，高松巍.管道漏磁检测数据压缩算法的研究［J］.沈阳工业大学学报，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］袁枚，袁文.数据压缩技术及其应用［M］.北京：电子工业出版社，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 研究与实现［J］.科技创新导报，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］尹云，刘波峰，徐勇，等.核电现场超声无损检测数据压缩［J］.计算机系统应用，2011，20（4）：118－121.

［12］黄贤武，王加俊，李家华.数字图像处理与压缩编码技术［M］.成都：电子科技大学出版社，2000.

［13］Nelson M.数据压缩技术原理与范例［M］.贾起东，译.北京：科学出版社，1995.