基于FFT和LZW波形数据压缩

1、基于FFT的电能质量波形数据的LZW压缩算法第一章 绪论1.1前言随着科技的进步，现代电力系统中用电负荷结构发生了重大变化。其非线性、冲击性以及不平衡等的负荷特性，使电网的电压波形发生畸变或引起电压波动和闪变以及三相不平衡，甚至引起系统频率波动等，对供电电能质量造成严重的干扰或污染。电网正面对越来越多的电能质量问题，这使得电能质量的研究十分紧迫。在电能质量监控方面，有两个趋势：其中之一是智能化，智能化旨在减轻人的劳动，能自动对电能质量问题进行识别和数据处理，从而实现全面的无人监控功能。另一个则是远程化。随着电力工业的发展和电网规模的扩大，供电部门和用户都迫切需要对较大量的监测点进行监控，然而各

2、点的分散，距离远近不同，监测电能质量的问题也根据用户和电网的需要而各不相同。所以远程化就可以适应不同层次的监控要求，从而使电能质量的监控点能够分布到电网中的任何地方，并且具有良好的在线功能。而远程化必然带来的问题就是，监测点和监控站之间的通信问题以及大量的电能质量数据的传输问题都十分重要。因此对数据进行压缩是减少数据存储费用和提高性能的有效办法，具有重大的实际意义。电能质量分析仪表需要采集大量的三相电数据，从数据中解析出工业用电的各种参数，以便指导生产过程。而由于嵌入式设备本身的CPU处理能力、通信能力和存储能力所限，要求对采集到的大量数据先进行压缩然后再传输、存储和分析等，以缓解嵌入式设备的

3、通信带宽低、存储容量小、计算能力弱等缺点带来的不便。1.2 国内外研究近况随着计算机技术的飞速发展，数据压缩作为海量信息存储和传输的支撑技术受到了人们的极大重视。目前，对于数据压缩算法的研究主要集中在数字图像处理、语音信号的分析等研究领域，也已经取得了显著的成果，而数据压缩技术在电力系统中的应用则相对较少。目前电能质量问题主要的分析方法可分为时域、频域和基于数学变换的分析方法三种。时域分析方法如差值法等，主要用于电能质量扰动信号的检测，方法快速简单，适合于检测电压凹陷、暂态脉冲等暂态电能质量问题，而不能检测如电压偏差、谐波、周期性陷波等稳态、周期性电能质量问题。频域分析方法主要用于电能质量中的

4、谐波问题的分析，包括频谱分布、谐波潮流计算等。基于数学变换的分析方法主要有傅立叶变换方法、矢量变换方法以及近年出现的小波变换方法和人工神经网络分析方法等。傅立叶变换作为经典的信号分析方法具有正交、完备等许多优点，如FFT 这样的快速算法。在频域，傅立叶变换具有较好的局部化能力，特别是对于那些频率成分比较简单的确定性信号，傅立叶变换很容易把信号表示成各频率成分的叠加和形式；但在时域中，傅立叶变换是对整个时间段的积分，没有局部化能力。由于小波分析方法具有良好的时-频局部化特性，它通过对不同的频率成分采用逐渐精细的采样步长，可以聚焦到信号的任意细节，能很好地处理微弱或突变信号，特别适合于对非稳态畸变

5、波形问题进行分析。1.3 本文任务本文针对提供的离线电能质量波形文件进行压缩，利用了有损压缩和无损压缩的结合；有损压缩部分是利用了对数据FFT之后的取阀值省去了一部分接近于0的数据，无损部分选择了对于重复性比较高的数据压缩效率高的LZW算法。压缩完后，再解压，计算谐波，谐波精度仍然要满足以下要求： 表 1 压缩要求压缩率要求：保证精度的要求下压缩率越高越好。压缩速度： 优先级较低。第二章 FFT2.1 快速傅立叶变换傅立叶变换在频域具有良好的局部化能力，可以较好地描述信号的频率特性，适合用于谐波等电力系统稳态或稳态扰动现象的分析，如果信号为稳态扰动（如正弦波形、谐波等），采用快速傅立叶变换对信

6、号进行压缩，得到相应的频率谱，记录了原始信号中不同频率成分的分量，于是这里选择了傅立叶变换没有选择对于暂态扰动有优势的小波变换。变换之后只要记住其中较大的系数，即可记录原始扰动数据中的大部分信息，达到压缩数据的目的，这里便成为有损压缩精度损失的来源。2.2 离散傅立叶变换（DFT）DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到发现了FFT算法，这种情况才发生了改变。当序列的点数不超过时，它的点定义为 （1）反变换定义为

7、（2）二者形式相似，快速算法的原理一样，这里先就其正变换进行讨论。令，当依次取为时，可表示为如下的方程组： （3）由上式可见，直接按照定义计算点序列的点时，每行含个复乘和个加，从而直接按定义计算点的总计算量为个复乘和个加。当较大时，很大，计算量过大不仅耗时长，还会因字长有限而产生较大的误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。下面介绍两种经典的算法基于频域抽取和时域抽取的算法。2.2.1 基于频域抽取基2FFT算法这里仅介绍基2算法，即是2的整次幂的情况。由定义 （4）把分成两半，即和，代入（4）式得 （5）由于（5）式两项又可合并为 （6）当

8、为偶数时，注意到，（6）式变为 （7）当为奇数时， ，（6）式变为 （8）这样就把一个点序列（）的点（）计算化成了两个点序列（和）的点（和）计算。由划分成和的计算量为个加，即和和个乘，即由于算出的点，是的点（）中为偶数的那一半，由算出的则是为偶数的那一半，故需要把偶数的抽出来放在一起作为的（）输出，同时把奇数的抽出来放在一起作为的（）输出。由于是频域变量，故这种算法称为频域抽取的算法。接着，两个点仍可用上述方法各经个乘个加划分成两个点（同时还要做相应的频域抽取），从而共划分成4个点，总划分计算量仍是个加和个乘。这样的划分可一步步做下去，不难看出，每步的总划分计算量都是个加和个乘。经过步的划分后

9、就划成了个如下两点的计算问题 （9）上式所需计算量是2个加和1个乘，于是完成个两点的总计算量仍是个加和个乘。从而完成全部点的总计算量个加和个乘，这比直接按定义计算所需的个乘和加要少得多。例如，用算法计算所需的乘法个数为，而直接按定义计算所需的乘法个数为，二者相差倍。若直接计算需半小时，而用计算只需9s即可完成，可见其效率之高，而且越大，的效率提高越明显。f0 F0000 F0 F0000f1 -1 W20 F4100 F2 F1001 gnf2 -1 W40 F2010 F4 F2010f3 -1 W41 -1 W20 F6110 F6 F3011f4 -1 W80 F1001 F1 F410

10、0f5 -1 W81 -1 W20 F5101 F3 F5101 pnf6 -1 W82 -1 W40 F3011 F5 F6110f7 -1 W83 -1 W41 -1 W20 F7111 F7 F7111图1 频域抽取的8点FFT计算流图一般情况下，由于做了次分奇偶的抽取，此算法最后的个两点计算出的不是顺序抽取的。次序的变化可用二进码来说明：第一次抽取所分的奇偶是由二进码第1位是1或0来区分的，该位为0时为偶数，该位为1时为奇数，第二次抽奇偶是由二进码第2位是1或0来区分的，每次抽取都是把偶数项放在前（左）边，把奇数项放在后（右）边，从而抽取以后数的二进码是按照二进制位从左向右依次排列的，

11、和普通二进制数从右向左依次排列的的规律正好相反，所以称为倒位序。在计算出之后要把倒位序变成顺序。所谓逆变换是指由求的计算，若直接按定义做计算，则除了求和号和正变换相同的计算量外，每算一个都还需再多做一个乘的乘法运算。故按定义完成全部点的总计算量是个加和个乘。下面从图导出它的快速算法，先讨论第3列的2点的逆运算如何完成。由式（7）得，由上式不难解出 （10）F0000 F0 F0000 1/8 f0F1001 F2 F4100 1/8 W2-0 -1 f1F2010 F4 F2010 1/8 W4-0 -1 f2F3011 F6 F6110 1/8 W2-0 -1 W4-1 -1 f3F4100

12、 F1 F1001 1/8 W8-0 -1 f4F5101 F3 F5101 1/8 W2-0 -1 W8-1 -1 f5F6110 F5 F3011 1/8 W4-0 -1 W8-2 -1 f6F7111 F7 F7111 1/8 W2-0 -1 W4-1 -1 W8-3 -1 f7图2 频域抽取的8点IFFT计算流图此计算过程如图2所示，可以看出：左边各列的划分计算也都是由个碟形运算来完成的，只是各碟形运算所乘的相移因子不同。把每个碟形运算都用图的办法变成对应的逆运算，并把它们按输入在左、输出在右重新排列，就得到了全部点的计算流图。给出了的示例，图中先对顺序输入的做次的频域抽取，并把个乘的

13、运算合成了一个乘的运算放在了最前边，然后就开始做求逆的碟形运算。2.2.2基于时域抽取的基2FFT算法比较正变换和反变换的定义式可见，去掉乘的运算，把换成，交换、和、，反变换定义式就变成了正变换的定义式。对图2做这些变换，则得到图3的流程图。对图1做这些变换，则得到图4的流程图。这就是时域抽取的算法流图。进行碟形运算之前，先要对顺序的时域输入序列进行次的奇偶抽取，故称为时域抽取的算法。f0000 f0 f0000 F0f1001 f2 f4100 W20 -1 F1f2010 f4 f2010 W40 -1 F2f3011 f6 f6110 W20 -1 W41 -1 F3f4100 f1 f

14、1001 W80 -1 F4f5101 f3 f5101 W20 -1 W81 -1 F5f6110 f5 f3011 W40 -1 W82 -1 F6f7111 f7 f7111 W20 -1 W41 -1 W83 -1 F7图3 时域抽取的8点FFT计算流图这里先算出个两点的 （11）f01/8 F0000 F0 F0000f11/8 -1 W2-0 F4100 F2 F1001 f21/8 -1 W4-0 F2010 F4 F2010f31/8 -1 W4-1 -1 W2-0 F6110 F6 F3011f41/8 -1 W8-0 F1001 F1 F4100f51/8 -1 W8-1

15、-1 W2-0 F5101 F3 F5101f61/8 -1 W8-2 -1 W4-0 F3011 F5 F6110f71/8 -1 W8-3 -1 W4-1 -1 W2-0 F7111 F7 F7111图4 时域抽取的8点IFFT计算流图然后把个两点的组合成个4点的，再把个4点的组合成个8点的，经过次的组合之后，就得到了顺序点计算结果。图5就给出了用FFT算法与直接DFT算法所需乘法次数的比较曲线：图5 FFT算法与直接DFT算法所需乘法次数的比较曲线2.3 基2FFT算法编程以频域抽取的基2 FFT正变换为例，对FFT的信号流图进行讨论，以找到FFT算法的规律。1）分级在进行变换的过程中，

16、从点到两点共分了M级，如图1所示，从左到右依次为级，级，级。2）倒位序在频域抽取的基2 FFT算法中，输出数据不是按照序列的先后顺序排列的，这是由于变换过程中，输出按奇、偶抽取的缘故。如果将序列中标号用二进制值表示，那么在FFT信号流图输入端，位于处，称为倒序。以8点FFT为例，顺序和倒序的关系如表2所示。表2 顺序和倒序对照表顺序倒序十进制数二进制数二进制数十进制数012345670 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 104261537从表1可以看出，一个自然顺序二进制数，

17、是在最低位加1，逢2向左移位；而倒序数的顺序是在最高位加1，逢2向右移位。用表示顺序数，表示倒序数，表示位权重。对于一个倒序数来说，下一个倒序数可以按下面的方法求：先对最高位加1，相当于十进制运算。如果，说明二进制最高位为0，则直接由得到下一个倒序值；如果，说明二进制最高位为1，则将的最高位变为0，通过实现，同时令，接着判断次高位是否为0，直到位为0时，令。归结起来算法流程图如图6所示。输出j=N/2i=1 to N-2t=fifj=fifi= fjk=N/2j=j-kk=k/2kjj=j+ki<j是是否否 输入N, 信号fNM=log2Nl=1 to lbr=(l-1)×2m

18、-1n=(l-1): la: N- 2m=1 to Mla=2M+1-m lb=la/2lc=n+lbt=fn+flcflc=(fn-flc) WNrfn=t倒位序重排信号输出 图6 倒位序程序流程图 图7 频域抽取FFT程序流程图3）蝶形运算单元和同址计算频域抽取的信号流图中，基本的运算结构如图8所示，该运算结构的形状像蝴蝶，故称为“蝶形运算单元”。在这一结构中，DFT和IDFT运算关系分别为 （12）Fm-1p Fm pFm-1q -1 WNr Fmq (a) 两点DFT的计算 fm-1p 1/2 fmpfm-1q WN-r -1 1/2 fmq(b) 两点IDFT的计算图8 频域抽取FF

19、T算法流图中第m级碟形单元而在时域抽取的信号流图中，基本的运算结构如图9所示。在这一结构中，DFT和IDFT运算关系分别为 （13）Fm-1p FmpFm-1q WNr -1 Fmq(a) 两点DFT的计算fm-1p 1/2 fm pfm-1q -1 WN-r/2 fmq (b) 两点IDFT的计算 图9 时域抽取FFT算法流图中第m级碟形单元其中，、分别表示该蝶形运算单元的上下节点的序号。可以看出参与运算的输入序号，输出序号仍为，并且该运算不涉及到其它的点，因此我们可以将输出的结果仍然放在数组中，称这样的操作为同址计算。也就是说，共同占有同一个存储单元。4）寻址和相移因子的计算时域抽取基2

20、FFT信号流图中，每一级有个蝶形单元。每一级的个蝶形单元又可以分为若干组，每一组具有相同的结构和因子的分布。如图1所示，第1级分为1组，第2级分为2组，第级分为组。在第级中，相邻组之间的间距（也即每个分组所含节点数）为，每个蝶形单元的上下节点之间的距离（也即每个分组所含碟形单元数）为。每组的相移因子，其中 综合以上各步骤，得到频域抽取FFT程序流程图如图7所示。第三章 LZW压缩算法3.1 LZW基本原理词典编码主要利用数据本身包含许多重复的字符串的特性，用一些简单的代号代替那些重复出现的字符串，从而实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算

21、法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。这里所用到的LZW(Lempel-Ziv-Walch)压缩编码方法。LZW的核心思想是用短的编码代替字符串。它不对输入的字符串做任何分析，只是将收到的每一个新字符串添加到一张字符串表中。当已经出现的字符串再次出现，即用一个短的编码代替该字符串，这就实现了压缩。LZW 算法基本思想是将每一个字节的值都要与下一个字节的值配成一个字符对，并为每一个字符设置一个代码。当同样的一个字符对再度出现时就用代号代替这一字符对，然后再用这个代号与下一个字符配对。在配对过程中，必须建立三个表格，分别为字首表、字符表和代号表，所有字符对和代号都分别存入

22、这三个表格中，数据量大大减少，可以获得较高的压缩比。LZW是完全可逆的，所有信息都保留了，其符号表在压缩和解压缩过程中完全自生成。LZW 的优点在于不仅可以对连续出现的相同字符进行压缩，而且可以对经常出现的由不同字符组成的字符串进行压缩。相对于其他算法，LZW 算法比较有利于用硬件来实现，实时性较好。3.2 LZW 算法的具体实现方法3.2.1 所定义的数据结构： Charstream：字符数据流，一个被编码的数据序列； Character：字符，字符数据流Charstream 中的基本数据元素； Prefix：前缀，在一个字符Character 钱的一个字符序列； String：字符串，由字

23、符Character 和它的前缀Prefix 构成； Code Word：码字，在编码数据流中的基本数据元素，它代表字典Dictionary 中的一个字符串String； Codestream：编码数据流，一个由码字Code Word 和字符Charact 组成的序列（即经过编码算法处理后的输出数据流）； Dictionary：字典，一个由字符串String 构成的表，按照在字典中的索引号，每个字符串String 都被分配了一个码字Code Word；Current Prefix：当前前缀，在编码算法中当前正被处理过的前缀Prefix 用P 来标识； Current Character；当前字

24、符，在编码算法中被确定的一个字符Character，通常这个字符就是在当前前缀Current Prefix 后的字符，用C 来标识； Root：根，一个单字元（String-character）的字符串； Current Code Word：当前码字，当前正在被处理的Code Word，它用cW 来表示，它所表示的字符串用String.cW 来表示； Previous Code Word：先前码字，在编码数据流中限于Current Code Word 的码字，它用pW 来表示，它所表示的字符串用String.pW 来表示。3.2.2编码算法：（1）编码开始时，字典包含所有可能的根，同时前缀P

25、为空；（2）读入在字符数据流中的下一个字符C；（3）字符串P+C 存在于当前字典中吗？YES：使P=P+C，即用字符C 扩展P；NO：把表示前缀P 的码字输出到编码数据流；然后将字符串P+C 添加进字典，并定义P=C，现在P 仅包含一个字符C；（4）在字符数据流中还有字符吗？1）YES：返回（2）继续进行编码过程；2）NO：输出表示P 的码字到编码数据流编码结束。3.2.3译码算法：（1）译码开始时字典包含所有的根；（2）读入在编码数据流中的第一个码字cW（他表示一个Root）（3）输出当前前缀字符串String.cW 到字符数据流码字流；（4）使先前码字pW=当前码字cW；（5）读入编码数据

26、流的下一个码字cW；（6）判断在字典中有String.cW 吗？YES：1）将先前前缀字符传String.cW 输出给字符数据流；2）使当前前缀P=String.pW；3）使当前字符C=String.cW 的第一个字符；4）将前缀字符串P+C 输出到数据流，并将其添加进字典。（7）在编码数据流中还有码字吗？YES：返回（4）继续进行译码；NO：结束。第四章 基于FFT和LZW算法的对于波形的压缩4.1 对波形FFT变换对于给定的波形数据，以200MS为例，有八路数据，分别为A相电压、B相电压、C相电压、N相电压（空） A相电流、B相电流、C相电流、N相电流。其中A相电压加入5%的二次谐波和15

27、%的三次谐波两张图片分别为利用200ms数据所绘制的三相电压波形和电流波形图 10 三相电压波形图 11 三相电流波形因为对8个通道同时采样，存储的数据也是按照每个采样点的8个数据同时存进去，读取时也是依次读出每个采样点的电压、电流数据。所以在对数据进行FFT的时候，需要做分离处理，把8组数据分离开来分别进行FFT变换，为了保证数据可以还原，分别对虚部实部进行保存。为了增加无损压缩的效率，还要对数据进行简化，小于一定阀值的数都以0来存储，这样大大降低了数据的复杂度，为后面的处理提供了保证。（具体程序见附录）4.2 对变换好的数据进行LZW压缩对上面FFT变换结束的实部虚部数据分别进行LZW压缩

28、，在运行指令中输入操作方式，源文件，目标文件即可，具体流程图：图12 LZW流程图压缩结束的数据保存在目标文件中，即完成了压缩。（具体程序见附录）第五章 MATLAB仿真分析由于压缩对于谐波分量要达到一定的误差要求，所以这里用MATLAB对压缩前压缩后的数据进行了仿真分析，以确保压缩的有效性。以提供的200MS数据为例，压缩前，先对A相数据进行采集、FFT变换并做出频谱火柴杆图。具体M文件及结果图如下：close all;clear all;clc;fid=fopen('osc200ms_binary.dat','r');x=fread(fid,'flo

29、at');fclose(fid);Y=reshape(x,8,4096);%转矩阵的型，分成8组AU=;BU=;CU=;NU=;AI=;BI=;CI=;NI=;i=1:1:4096; AU(i)=Y(1,i),BU(i)=Y(2,i),CU(i)=Y(3,i),NU(i)=Y(4,i), AI(i)=Y(5,i),BI(i)=Y(6,i),CI(i)=Y(7,i), NI(i)=Y(8,i);au=fft(AU,4096); f=(0:4095)*20480/4096;mag1=abs(au)/(4096/2);mag1(1)=mag1(1)/2;stem(f,mag1);axis(0

30、 200 0 400);图 13 A相电压压缩前离散频谱图由图中可以读出主波和谐波的电压大小：UN=310.8488, Uh2=15.5327, Uh3=46.6167。压缩结束后，对保存的实部虚部数据文档进行LZW解压缩，生成的文件同理导入到MATLAB中，对于A相的数据画出离散频谱图：图14 A相电压压缩后离散频谱图由图中可以读出此时谐波的电压大小：UN=310.8475， Uh2=15.5511， Uh3=46.6253；计算误差均满足表一中的要求。附录1 压缩解压缩示例（以200ms数据为例）1. 压缩在窗口运行如下命令，即把经过FFT变换后的real.txt文件进行LZW压缩，结果保

31、存在1.txt文件中：同理对虚部文件也进行压缩。2. 解压缩在窗口运行如下命令，即把压缩好的1.txt文件进行解压缩保存在real1.txt中：由结果可知达到了60多倍的压缩。附录 2 C语言程序/*fft 部分*/#include "math.h"#include "stdio.h"struct compx double real; double imag; compx ;struct compx EE(struct compx b1,struct compx b2) /*对两个复数进行乘法运算*/ struct compx b3; b3.real=b

32、1.real*b2.real-b1.imag*b2.imag; b3.imag=b1.real*b2.imag+b1.imag*b2.real; return(b3);void FFT(struct compx *xin,int N) int f,m,LH,nm,i,k,j,L; double p , ps ; int le,B,ip; float pi; struct compx v,w,t; LH=N/2; f=N; for(m=1;(f=f/2)!=1;m+); nm=N-2; j=N/2; /*变址运算*/ for(i=1;i<=nm;i+) if(i<j)t=xinj;x

33、inj=xini;xini=t; k=LH; while(j>=k) j=j-k;k=k/2; j=j+k; for(L=1;L<=m;L+) /*用蝶形运算完成FFT*/ le=pow(2,L); B=le/2; /*同一蝶形结中参加运算的两个点的距离*/ pi=3.14159; /*PI的取值也是进度损失的一部分*/ for(j=0;j<=B-1;j+) p=pow(2,m-L)*j; ps=2*pi/N*p; w.real=cos(ps); /*W为系数商，当前系数与之前系数的商*/ w.imag=-sin(ps); for(i=j;i<=N-1;i=i+le)

34、ip=i+B; /*i,ip为参加运算的两个节点*/ t=EE(xinip,w); xinip.real=xini.real-t.real; xinip.imag=xini.imag-t.imag; xini.real=xini.real+t.real; xini.imag=xini.imag+t.imag; return ; /*lzw 算法*/#include <stdio.h> #include <string.h> #include <stdlib.h> #define BITS 12 #define HASHING_SHIFT BITS-8 #de

35、fine MAX_VALUE (1 << BITS) - 1 #define MAX_CODE MAX_VALUE - 1 #if BITS = 14 #define TABLE_SIZE 18041 #endif #if BITS = 13 #define TABLE_SIZE 9029 #endif #if BITS <= 12 #define TABLE_SIZE 5021 #endif void *malloc(); /* 函数原型 */ int LZW_Compression(char *in_filename, char *out_filename); int L

36、ZW_Decompression(char *in_filename, char *out_filename); /* 内部函数 */ int find_match(int hash_prefix,unsigned int hash_character); unsigned char *decode_string(unsigned char *buffer,unsigned int code); unsigned int input_code(FILE *input); void output_code(FILE *output,unsigned int code); /* 全局变量，编码/解

37、码使用的内存缓冲区 */ int *code_value; unsigned int *prefix_code; unsigned char *append_character; unsigned char decode_stack4000;/* LZW_Compression() 本函数用LZW算法压缩指定的文件，并将结构存储到新的文件中 */ int LZW_Compression(char *in_filename, char *out_filename) unsigned int next_code; unsigned int character; unsigned int strin

38、g_code; unsigned int index; int i; FILE *input; FILE *output; /* 分配空间 */ code_value=(int*)malloc(TABLE_SIZE*sizeof(int); prefix_code=(unsigned int *)malloc(TABLE_SIZE*sizeof(unsigned int); append_character=(unsigned char *)malloc(TABLE_SIZE*sizeof(unsigned char); if (code_value=NULL | prefix_code=NU

39、LL | append_character=NULL) printf("Fatal error allocating table space!n"); return 0; /* 打开文件 */ input=fopen(in_filename,"rb"); output=fopen(out_filename,"a"); if (input=NULL | output=NULL) printf("Fatal error opening files.n"); return 0; ; /* 压缩 */ next_code=

40、256; for (i=0;i<TABLE_SIZE;i+) code_valuei=-1; i=0; printf("Compressing.n"); string_code=getc(input); /* * This is the main loop where it all happens. This loop runs util all of * the input has been exhausted. Note that it stops adding codes to the * table after all of the possible code

41、s have been defined. */ while (character=getc(input) != (unsigned)EOF) if (+i=1000) i=0; printf("."); index=find_match(string_code,character); if (code_valueindex != -1) string_code=code_valueindex; else if (next_code <= MAX_CODE) code_valueindex=next_code+; prefix_codeindex=string_code

42、; append_characterindex=character; output_code(output,string_code); string_code=character; /* * End of the main loop. */ output_code(output,string_code); output_code(output,MAX_VALUE); output_code(output,0); printf("n"); /* cleanup. */ fclose(input); fclose(output); free(code_value); free(

43、prefix_code); free(append_character); return 1; int find_match(int hash_prefix,unsigned int hash_character) int index; int offset; index = (hash_character << HASHING_SHIFT) hash_prefix; if (index = 0) offset = 1; else offset = TABLE_SIZE - index; while (1) if (code_valueindex = -1) return(index); if (int)prefix_codeindex = hash_prefix && append_characterindex = hash_character) return(index); index -= offset; if (index < 0) index += TABLE_SIZE; /* LZW_Decompression() 用LZW对文件进行