基于织物信息的动态Huffman压缩算法优化

卢小杰，叶明全，黄道斌

(皖南医学院 计算机教研室， 安徽 芜湖 241000)



基于织物信息的动态Huffman压缩算法优化

卢小杰，叶明全，黄道斌

(皖南医学院 计算机教研室， 安徽 芜湖 241000)

摘要：针对嵌入式系统内存不足的特点，为了使上下位机更有效地进行数据传输，对动态Huffman压缩算法进行优化，使用堆排序的方法来构造Huffman树，缓解了嵌入式系统的内存压力；在数据传输过程中增加CRC校验位，以此来提高数据传输精度，并在解压中处理了无效位。同时对嵌入式织造系统中的织物信息数据进行频谱分析。实验结果表明，优化的Huffman压缩算法能够获得更好的压缩效果，并且压缩率与数据的频率相关。

关键词：嵌入式技术；FFT；数据压缩； Huffman压缩算法； CRC校验位

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.012

随着现代纺织业的发展，嵌入式技术(Embedded Technology)和物联网(Internet of Things，IOT)技术被应用在纺织机械控制系统中，称为嵌入式织造系统，一般由上下位机构成，上位机为PC机或其他嵌入式主控系统，下位机为51单片机系统或者其他精简的单片机系统。如图1所示。

图1　织造系统示意图

在实际工业生产中，把织物信息数据由上位机的主控系统传输至下位机中，由下位机控制纺织机械。为了保障数据在工业级应用中有较好的实时性和较低的误码率，本文研究针对织物信息数据的压缩算法。任何一种数据形态都有一定的冗余度，有效地减少冗余度可以大大提高数据的传输速度、节省数据存储空间、减少内存消耗、降低硬件成本。因此，研究针对嵌入式织造系统中织物信息数据的压缩算法具有很高的应用价值。在上位机中压缩后的数据传输至下位机，在下位机有限的内存空间和较低的运算速度下有效地解压出来[1]。目前应用于嵌入式系统的压缩算法很多，如RLE压缩算法[2]、Huffman压缩算法、LZSS压缩算法[3-4]和LZW压缩算法[5]等，这些压缩算法各有其特点和适用领域。本文在此基础上选取Huffman压缩算法，对其进行改进，使之能够对织物数据有较好的压缩效果。

1织物信息数据

织物信息数据中比较重要的一项为纹板数据，即用来控制织物的纹板花纹的数据。纹板数据包含穿综信息和组织信息，如图2。冲孔为1，不冲孔为0，形成二进制数据流，如图3。

图2　某条织物纹板图

0001001001001000éëêêêêêùûúúúúú

图3纹板图和纹板矩阵

由图3可知，纹板数据可以看作二进制流的数据文件。织物信息数据从统计学上说是一种随机的二维矩阵，对此二维系数矩阵进行频谱分析，在频域空间上进行傅里叶(FFT)变换。

N点序列x(n)的离散傅里叶变换(DFT)和离散傅里叶逆变换(IDFT)的复数表示形式为[6]

(1)

FFT是DFT在工程应用中的快速傅里叶变换，基于2-DFT的蝶形运算，如经过8点蝶形运算的DFT化为FFT。假设采样频率为F，采样点数为N，某点n频率为

Fn=(n-1)F/N

(2)

在Matlab中二维系数矩阵为A(∶)，经过函数fftshift(fft(A(∶)))变换后得到相应的织物信息频谱。织物信息数据的频谱与后面研究的Huffman压缩算法得到的压缩率相关。

2动态Huffman压缩算法

在嵌入式织造系统中常常要求有较高的实时性，使用动态的Huffman压缩可以一边压缩一边解压，字符的编码长度是与压缩和解压一个字符的时间成正比，可以实时进行。

2.1动态Huffman压缩过程

动态Huffman压缩算法主要是针对静态Huffman压缩算法存在的不足而提出来的。静态Huffman压缩算法具有以下缺陷[7]：

(1)要对文件扫描两遍，先遍历所有字符，在数据传输过程中很难预知所有字符概率，现实应用中可行性差；

(2)先建立Huffman编码表，浪费了额外的空间来维护和传输编码表；

(3)静态Huffman压缩算法在实际应用中压缩效率比较低，且将Huffman树的信息随着压缩数据传输，不利于较短数据的压缩。

动态Huffman压缩算法无需预知字符概率，核心是边读取数据边修改Huffman树，压缩和解压缩都由空Huffman树开始，第i+1个字符的编码是根据第i个字符的Huffman树来进行的，不停地改变树的结构，不需要为解压而保存树的有关信息。

动态Huffman压缩算法步骤如下[8]

(1) 初始化根结点、空叶子结点；

(2) 读入第1个字符，作为根结点的右孩子，其重量为1，空叶子结点作为根结点的左孩子，其重量为0。

(3) 读入字符，如果是文件结尾则结束，反之判断该字符是否出现在编码树中，如果不是进入步骤(4)，反之输出字符编码，以该字符结点作为当前结点。

(4) 输出空叶子结点编码，将该字符作为当前空叶子结点的右孩子，新空编号为当前空叶子结点编号减1，叶子结点作为当前空叶子结点的左孩子，编号为当前空叶子结点编号减2，且左右孩子的权重均为零。

(5) 判断当前结点是否为根结点。如果是进入步骤(6)，反之进入步骤(7)。

(6) 把当前根结点到该字符结点路径上所有结点的重量加1，重复(2)到(5)。

(7) 将当前结点与权重相同、序号最大的结点(该结点不为当前结点的父结点)进行交换(不交换序号)，并使序号最大结点的父结点成为新的当前结点，重复步骤(5)。

2.2动态Huffman解压过程

解压是压缩的逆过程。考虑下位机有限的内存空间，如果Huffman树以字节为单位，由于纹板数据每位的概率是随机的，因此最大需要建立256个叶子结点的Huffman树，而动态Huffman树是根据输入字节的频度动态调整Huffman树的，在上位机压缩后无需传输编码树，下位机也可以解压出来。另外在下位机中解压出来的数据可以转存出去，有效缓解了下位机的存储压力。

动态Huffman解压算法步骤如下[9]

(1) 初始化根结点、空叶子结点；

(2) 读入第1个字符，作为根结点的右孩子，其编码为1，空叶子结点作为根结点的左孩子，其编码为0。

(3) 若不是文件结尾，从压缩文件中读入1位二进制数，若是0，则沿左孩子搜索；若是1，则沿右孩子搜索。

(4) 判断是否是叶子结点，如果是重复步骤(3)，反之判断是否是空叶子结点；如果是将该叶子结点代表的字符取出存盘，反之，从压缩文件读入1个字符存盘。

(5) 修正Huffman树，直至文件解压结束。

3动态Huffman压缩算法优化

3.1堆排序的设计

Huffman树构造过程常使用链表方式选择排序，这种方法效率低、速度慢，本文使用堆排序，堆排序可以减小对内存的读取、提高系统的响应速度[10]，这有利于嵌入式系统实时控制纺织机械。

本文使用极小堆的方式排序，极小堆是一种每个结点都小于其叶子结点的完全二叉树， 算法如下

void HuffHeapSort(DataType R[],int n){

int i;

for i=n/2 to 0

HeapAdjust(R,i,n);//调整堆算法

for i=n to 0

R[0]=R[1]; R[1]=R[i]; R[i]=R[0];//R[i]交换堆底元素

HeapAdjust(R,1,i-1);

}

堆排序比较次数和移动次数较小，对于无规则且数据流0、1交替较密集的纹板数据来说可以有效减少内存读取次数，缓解内存压力。另外堆排序的算法时间复杂度是O(nlog2n)，一般选择排序的时间复杂度为O(knlog2n)，最坏的时间复杂度为O(n2)，所以堆排序要优于选择排序算法。

3.2减小误码率的设计

嵌入式织造系统对织物信息数据的传输精度要求高，在工业级应用中采用RS485和RS232的数据传输方式，保障了短距离物联网空间中数据的精度，要求数据传输过程有较高的抗噪能力，保障数据有足够高的正确率。

本文使用以下两种方法减少误码率：

(1)在数据字符串尾部加上CRC(CyclicRedundancyCheck)校验位[11]，CRC校验是循环冗余校验，相对于奇偶校验、和校验等其他校验方式具有很好的纠错能力，这种数据传输错误检查方法经常被用在较易受工业干扰的嵌入式控制系统通信上。

在上位机到下位机传输数据的过程中，二进制数据流易造成“0”“1”互换差错，在嵌入式系统中实现CRC校验方式要求算法简单、易于实现。在经过Huffman压缩后的数据流后加上CRC校验位，其算法流程如图4所示。

图4　CRC算法流程图

经过试验表明，CRC循环冗余校验会稍微增加一定的冗余度，但是能够很好地进行差错控制，使得数据纠错率达97%以上。所以在嵌入式通信领域是被应用最广泛的一种纠错方式。

(2)如果出现传输错误，采用重新发送的方式解决错误。这是由于Huffman编码压缩是可变长度的编码压缩方式，无法从压缩文件中恢复查找内容，织造系统数据传输单元又是实时自动传输的，因此须重新发送数据。

3.3处理无效位的设计

数据被压缩以后以数据流的形式传输到下位机，以bit位为基本单元，8bit为一个字节，以字节为单位解压，如果以最高位开始，压缩码不是从字节的最高位开始，需要一定的数据结构来处理无效的位，其数据结构如下所示：

DATA_TAB

DB00000000b,10000000b,11000000b

DB11100000b,11110000b,11111000b

DB11111100b,11111110b,11111111b

Huffman每个字符与以上相应的数据进行“与”运算，用来处理无效的位。

4实验结果

选用M058LBN型号的单片机作为下位机、PC机作为上位机进行实验。M058LBN单片机属于Cortex-M0系列单片机，此系列单片机因价格低廉、高性能的CPU及较高的性价比被广泛应用在嵌入式控制系统中。M058LBN单片机具有4kBRAM，其空间大小完全满足算法的需要。

实验中选用压缩率作为压缩效果的标准。压缩率为压缩后的数据大小与原数据大小的比值，在信息论中作为衡量压缩效果的一个重要指标，一般认为压缩率越小越好，大于1的则称为负压缩。实验结果如表1所示。

表1　实验结果对比

由实验结果可以看出，经过优化的动态Huffman压缩算法能够降低压缩率，提高了压缩效果，节省了传输时间；另外使用堆排序构建Huffman树也一定程度上缓解了内存压力，降低了算法的时间复杂度；在算法实现的过程中，在数据传输过程中增加CRC校验位和使用一定的数据结构处理无效的数据位，有效提高了数据传输精度，减小了误码现象。总之，经过优化的Huffman压缩算法在嵌入式织造系统中有很高的实际应用价值。

选用.jc5格式的纹板数据，这种纹板数据在江浙一带的织造业中比较常见。对上述4组数据进行频谱分析，频谱图如图5所示。

图5纹板数据采样频谱图

Huffman压缩算法对于不同纹板数据的压缩效果也会出现差别。由纹板数据的频谱图可以看出，聚集在0点频率周围的频谱压缩率低，压缩效果相对较好，相对数据压缩效果越好；而频率点分散的压缩效果比较差，如数据4.jc5。这是因为Huffman压缩算法是基于统计模型的压缩算法，数据概论统计的权值比较均衡的压缩率高，压缩效果差，反之压缩率低。

5结束语

本文介绍了动态Huffman压缩算法在嵌入式织造系统中的应用，说明了Huffman算法存在的不足，改进后的Huffman压缩算法节省了数据传输时间，这对实时性要求较高的织造控制系统是非常有效的。 同时，经过对织物信息数据频谱的分析，结合嵌入式系统的特点，简单易行的Huffman压缩算法也得到了很好的应用，经过改进后的算法可以保障解压的顺利进行，在工业级上的抗噪性能设置也具有很好的实用价值，另外经过频谱分析可以看出织物信息数据频谱与压缩率有很大的关联性。此研究方法同样可以运用到其他嵌入式系统的数据压缩中去，具有非常高的实用价值。

参考文献:

[1] 王海威, 倪宏, 朱明, 等. 一种嵌入式系统多媒体文件快速传输协议[J]. 小型微型计算机系统, 2011, 2(2): 208-213.

[2]SahnounK,BenabadjiN.AhybridDPCM-DCTandRLEcodingforsatelliteimagecompression[J].IJCSITCE,2014,1(1):1-6.

[3] 王驰, 王健, 杨萌, 等. 一种新型的FPGA配置位流压缩算法[J]. 复旦学报(自然科学版), 2014, 53(3): 365-370.

[4] 马庆, 吕玉琴.SIP信令压缩动态字典方案[J]. 计算机工程, 2009, 35(24):72-74.

[5]LiShujun,LiChengqing,KuoJ.OnthesecurityofasecureLempel-Ziv-Welch(LZW)algorithm[C].IEEEInternationalConferenceonMultimediaandExpo,Piscataway:IEEE, 2011:1- 5.

[6] 李焱, 张云泉. 异构平台上性能自适应FFT框架[J]. 计算机研究与发展, 2014, 51(3): 637-649.

[7] 萨洛蒙. 数据压缩原理与应用[M]. 2版. 吴乐南, 译. 北京: 电子工业出版社, 2003.

[8] 张银铃, 武彤, 邓少勋. 基于快速排序和Huffman树的物化视图增量保持算法[J]. 计算机科学, 2014, 41(6A): 451-454.

[9]LinYinkai,HuangShuchien.AfastalgorithmforHuffmandecodingbasedonarecursionHuffmantree[J].TheJournalofSystems&Software, 2012,85 (4):974-980.

[10] 赵学锋, 杨海斌, 张贵仓. 基于堆的最小连通支配集高效近似算法[J]. 计算机工程, 2011, 37(2):54-56.

[11] 宁平.FPGA上实现CRC16纠错编码并行计算的探讨[J]. 计算机工程与科学, 2014, 36 (6):1023-1027.

Dynamic Huffman Compression Algorithm Optimization Based on Fabric Information

LU Xiao-jie, YE Ming-quan, HUANG Dao-bin

(School of Computer teaching, Wannan Medical College, Wuhu, Anhui 241000, China)

Abstract:According to the insufficient memory, in order to make the host-computer and lower system more efficient data transmission, the paper improves the dynamic Huffman compression algorithm, uses the heap sort of method to construct the Huffman tree, alleviates the pressure memory of the embedded system. In order to improve the precision of data transmission, the CRC check bits is increased and invalid bits in the decompression are eliminated. Meanwhile, the frequency spectrum of fabric information data spectrum in embedded weaving system is analyzed. The experimental results show that the optimization of Huffman compression algorithm can obtain better compression effect, and the compression ratio is associated with the data frequency.

Key words:Embedded technology; FFT; data compression; Huffman compression algorithm; CRC check Bits

* 收稿日期：2015-09-24

基金项目：安徽省高校省级自然科学研究重点项目 (KJ2014A266)。

作者简介：卢小杰，女，安徽阜阳人，硕士，皖南医学院教师，研究方向为数据处理、嵌入式技术。E-mail:luxiaojie06@163.com

中图分类号：TP399

文献标识码：A

文章编号：1007-4260(2016)02-0043-05

网络出版时间：2016-06-08 12:57网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.012.html