数据压缩算法研究（共8篇）
数据压缩算法研究 篇1
一、引言
随着信息技术和计算机技术的飞速发展, 人们面对的数据越来越多, 在数据储存和传输的过程中, 数据压缩[1]的地位越来越重要。一般来说, 数据压缩可以按压缩的失真度分为有损压缩和无损压缩[2]。有损压缩顾名思义就是把使用压缩技术后的数据进行解码还原, 得到的数据与之前的数据不是完全一样, 却不会使人们对原始资料引起错误的理解。有损压缩一般应用在压缩后的数据不一定要和原始数据完全一致的场合。无损压缩就是指把压缩后的数据进行解码还原, 得到的数据与原始数据一模一样, 没有改变。目前流行的无损压缩编码有哈夫曼编码、LZW编码、算术编码、行程编码等。
目前, 数字化和网络化正在给我们的生活带来翻天覆地的变化, 图像的数字化也将成为一个必然的趋势。占据我们大量存储空间和传输带宽的图像, 如果采用数字化处理, 会使得图像数据有如下优点: (1) 数字化处理后的图像容易储存而且方便处理, 不再是一块难嚼的鸡肋, 能够满足人们的各种需求; (2) 数字化处理后的图像在传输过程中容易传输且快速; (3) 数字化处理后的图像与原始图像一样高分辨率, 优质量; (4) 数字化处理后的图像更增强了稳定性和传输过程中的抗干扰能力。但是, 通常数字化后的图像仍然面临着对海量数据的存储与传送问题。所以, 在计算机的存储空间和信道有限的条件下, 怎样高质量、高效率地对数字化后的图像进行可靠压缩成为计算机技术的热门研究领域。
Lempel-Ziv-Welch (LZW) 编码就是一种主要用于图像数据压缩的算法。这种算法对一些简单平滑的图像和一些噪声小的数据具有比较高的压缩比, 而且本算法有比较快的压缩和解压缩速度。本文主要介绍了LZW算法, 并给出了一个编码实例, 通过实验结果可以证明这是一种有效的数据压缩方法。
二、LZW算法
LZW算法是在数据压缩经典算法LZ77和LZ78二者的基础上改进而成的, 由Terry Welch于1984年提出[3,4]。
LZW算法在开始压缩之前, 字典中只有单个字符和编码的串表。开始压缩时, 读入字符串, 按一定的顺序与字典中已包含的字串进行匹配, 如果能够匹配成功, 则将匹配好的字符串对应编码输出;如果不能进一步匹配, 则将导致匹配失败的字符与之前的字符串合并在一起, 加入串表并给以相应编码。
LZW算法的串表具有前缀性[5], 即表中任何一个字符串的前缀字符也在串表中。也就是说, 如果由某个字符串P和某个单字符C所组成的字符串PC在表中, 则P也在表中。C叫作前级串P的扩展字符。
LZW算法与LZ78算法有着相似的编码和解码过程。这两种算法的主要区别在于进行编码时, 因为在压缩时, 字典中已经包含有每个单字符及其编码的串表, 所以在LZW算法的码字中省略了LZ78算法的码字中关于未匹配字符这项, 只是含有已经匹配成功的字符串的索引值, 由此来降低LZW算法的码字的长度以便提高数据压缩比;解码时, 由于表中需要的未匹配字符要在解压缩下一个输入码字后才可以获得, 因此建表的过程相对于压缩时要推迟一步。
三、LZW算法实例
本文使用VC来编译代码和制作界面。
在压缩开始时, 首先要对存放字符串的hash表、结束标志、清除标志、输入/输出缓冲的位置进行初始化。必须使hash表不是空值, 从0开始记输出缓冲位。需要定义前缀字符串Old和当前读入字符Pixel。如果Old+Pixel字符串存在hash串表当中, 就从中取出该字符串的索引编号Index。
部分代码可表示为:
如果Old+Pixel字符串不在hash串表当中, 就把Old+Pixel字符串添加到String Table编码表。
部分代码可表示为:
进行压缩完成后要清除hash表。在数据解码过程中, hash串表能依据原始字典和Index再次生成。
数据的解压缩过程其实是压缩的逆过程。首先还是必须对字符串表、清除标志、结束标志和输入/输出进行初始化。需要定义前缀字符串Old和当前读入字符Pixel (当前输入的经压缩后的字符) 。如果Code既不是清除标志也不是结束标志时, 算法进行数据解码工作。
部分代码可表示为:
进行解码完成后, 要清空m_pStrBegin指针, 即清空指向String Table表的指针。
下面我们采用一个示例图像, 使用本文的LZW算法来进行压缩。原始图像zuoye如图1所示, 是一个大小为486 Byte, 宽度和高度均为12像素的彩色图像。本文用VC做的界面图, 选择zuoye为压缩文件后, 单击编码按钮就可进行压缩操作。压缩结果如图2所示。
图2压缩结果图
从图2可知, 原文件大小为486字节, 利用LZW算法进行压缩后为132字节, 压缩率为27%。
四、结论
通过实验结果可以看出, 本文提出的算法是一种有效的无损数据压缩算法。许多学者一直在对LZW及其派生算法加以不断地改进和完善, 使之成为了当今数据压缩的主流算法。
参考文献
[1]David Salomon.吴乐南, 等.数据压缩原理与应用 (第二版) [M].北京:电子工业出版社, 2007.
[2]侯阳.数据压缩技术及C语言实例[M].北京:学苑出版社, 2005.
[3]张凤林, 刘思峰.一个改进的LZW数据压缩算法[J].小型微机计算机系统, 2010, 27 (10) .
[4]林小竹, 籍俊伟.一种改进的LZW压缩算法[J].计算机工程, 2009, 31 (14) .
[5]寇海洲, 夏江涛, 赵文东.LZW算法C语言实现及改进[J].淮阴工学院学报, 2007, (12) .
XML数据压缩索引研究 篇2
关键词：XML；后缀树；后缀数组；自索引；BWT
中图分类号：TP311.13 文献标识码：A 文章编号：1674-7712 (2012) 06-0099-01
一、数据压缩知识
数据压缩技术的发展。
随着计算机技术的飞速发展，数据压缩作为解决海量信息存储和传输的支撑技术受到了人们的极大重视，对数据压缩算法的研究也不仅局限于信息论中有关信源编码的范畴，数字图像信号、语音信号的分析和处理等技术被大量引入到有关的研究领域。
1977年，两位以色列科学家Jacob Ziv和Abraham Lempel发表了名为“A Universal Algorithm for Sequential Data Compression”（顺序数据压缩的通用算法）的论文，提出了一种不同与以往的基于字典的压缩方法——LZ77，他们在1978年又提出了LZ77的改进算法——LZ78，这两个算法吧数据压缩的研究推向了一个全新的阶段。1984年，Terry Weleh发表的论文“A Technique for High Performance Data Compression”（高性能数据压缩技术）描述了对LZ78算法的改进和具体实现技术，成为LZW算法。目前，无损数据压缩领域中流行的数据压缩方法多是基于字典的压缩技术。UNIX系统上的一个实用压缩软件COMPRESS和Windows系统下的压缩软件Winzip和Winrar中所使用的压缩算法都是基于字典压缩技术的。
当数据压缩被用于减少存储空间时，可以减少程序的总执行时间。这是因为存储量的减少将导致磁盘存取次数的减少，虽然数据的压缩/解压缩过程会增加额外的程序指令，但由于程序的执行时间通常少于数据的存储时间，因此中的执行时间将减少。也正因如此，数据压缩技术在计算机技术飞速发展的今天仍然有着很重要的作用。
二、XML压缩索引
（一）XML压缩背景
上文中已经述说了XML的优点，但和其它形式的数据表示相比，XML文档往往很大。因此有些时候，传输速度和存储空间会非常重要。具体来说：
1.XML是一种清晰而易用的文本标记格式，但它的弱点就是当有大量数据需要交换，而程序内部处理部分又非常少时，会导致XML文档非常大，这样过大的空间占用意味着更大的处理代价；
2.由于本文压缩算法多年来一直是大量研究项目的课题，目前已经非常成熟。这种类型的算法都能方便的将XML进行压缩，但将XML文本作为一般文本文件进行压缩，这类算法都不大可能改善处理的速度，而且还会增加了解压后再解析的步骤；
3.我们把XML文档用于索引结构，这样就不能只保持了XML文档的结构而无法对XML进行索引搜索。也就排除了一些简单的XML压缩算法。
（二）XML压缩方法
当压缩文档时，通常首先考虑常用的压缩算法，如：Lempel-Ziv和Huffman，以及在它们上面实现变化的一些常用实用程序。在类Unix平台上通常是gzip；在其它平台上，zip更为常用，比如：PKZIP、Info-ZIP和WinZip。但这些实用程序实际上意在充分地减少XML文件的大小。但是，都没有保持了XML文档的结构，或是无法对XML文档进行索引。这样本文选择使用BWT压缩算法而不是顺序Lempel-Ziv算法。
（三）BWT数据压缩
利用BWT压缩算法，我们先把字符文本进行转换，然后进行压缩，这样就解决了XML文档过大的弊端。而且BWT压缩算法要比顺序LZ算法，解压时速度有所提高。BWT算法的具体介绍我们在第5章进行讲解。
三、系统设计
（一）XML文件整体输出
首先，我们先不考虑XML文件的结构，这样把XML数据文件提交给程序，会按照普通文本文件的方式进行处理。程序先读取整个文件的内容，之后将它们作为一个字符串，进行后缀数组排序，然后BWT转换。但是这样的结果并不如意，有以下两个缺点：
1.程序执行的效率不高，文件内容如过大，导致整体的速度下降；
2.不便于查找，整体进行排序换转后打乱了文件结构，不能成为索引；
（二）以XML文件结构进行输出
由于不能破坏XML文件的结构，只能按照XML现有的标签内容进行。这样我们就引入了XML解析器，它可以分析出XML文件的结果和具体内容。先用解析器解析XML文件，我们就方便的判断出，什么是标签，什么是数据。把每个标签或者数据，单独进行排序转换。
具体过程：
1.XML解析器读取分析XML文件；
2.建立一个空的XML文件，进行添加排序转换后的数据；
3.如分析出标签开始，则提取此标签，对其进行排序转换，把结果插入新的XML文件；并记住此标签的级别，用于插入下级标签时使用；
4.如分析出数据，则对数据进行排序转换，并直接把新数据插入包含它的标签中；
5.如分析出标签结束，则关闭此级标签，结束数据转换；并记录新的标签级别，用于插入平级标签时使用。
参考文献：
[1]Donald Knuth.Art of Computer Programming[M].2002,Volume,3
[2]N.Jesper Larsson.Structures of String Matching and Data Compression[D].Sweden:Lund University,1999
无线传感器网络数据压缩算法研究 篇3
传感器节点是一个配备了无线电收发器、微控制器、能量源的信息接收处理单元。因为体积小, 同时考虑到成本问题, 传感器节点受到有限的带宽、电量和计算能力的限制。对于大规模部署无线传感器节点的网络来说, 如何提高节点的能量效率, 延长整个WSN寿命是需要解决的首要问题[1]。
对于监测区域内的传感器节点来说, 其数据采集行为往往具有:同一个信号可能被不同传感器捕获;对于多维度信息采集, 多个传感器的并行采集数据能够形成互补等特点, 这些都容易产生冗余数据[2]。
1 数据冗余
1.1 时间冗余
时间冗余来自于提高精度传感器节点的读数和在传感和通信时承受瞬时故障。时间冗余的应用较为复杂, 主要用于无线传感器网络的环境参数频繁变动的场景, 传感器节点通过发送连续多个采集报告以提高数据置信水平, 这种类型的冗余通常是在视频监视和多代支持基于特定的数据压缩技术的编解码器等应用中采用。时间冗余可以分为:时间感知冗余、时间通信冗余。
1.2 空间冗余
空间冗余来自于传感器网络中某个特定地理区域内, 多个传感器节点采集的信息出现重叠现象。这种空间冗余产生的目的, 主要是为了提供容错或提高测量数据的可靠性以达到一定的安全水平。
空间冗余几乎在任何一个传感器网络部署时都会发生, 因为在无线传感器网络的应用中通常需要密集部署节点以保证网络的连通性。从覆盖问题的角度来说, 空间冗余可以划分为物理冗余和分析冗余, 具体分析如下。
物理冗余是一种非常普遍的技术, 通过节点在某一区域的高密度部署用于保证系统的可靠性, 尤其是考虑到网络受到安全威胁时, 这种冗余非常有必要。当然, 由于节点之间距离过近, 易造成节点采集的数据具有一定的相似性, 而这些数据的产生在无线信道传输过程中无疑会消耗大量的节点能量, 因此, 需要通过一定的数据融合方法来降低数据冗余度, 以节约资源。
分析冗余则是指通过一定的数学模型根据历史监测数据推导出的预估测量值, 用于与节点发送过来的实际测量值进行比较, 目的是获取出现故障或恶意攻击的节点。通常, 当节点数量过多或者数据模型过于复杂时, 分析冗余的计算代价太大, 另外, 分析冗余产生的冗余数据与真实的数据本身不一定能完全契合, 因此, 这种冗余只出现在较少的应用中。
1.3 信息冗余
信息冗余则主要是用于信息表示方法上对冗余数据的描述, 常常定义为使用冗余数据 (例如, 特殊bit) 来重新构造丢失的信息。因此, 信息冗余意味着额外的信息是用来检测和从故障中恢复。奇偶校验位附加到数据块, 使误差检测即可以视为一个实例信息冗余。另一个例子是信息冗余擦除码, 都是通过使用的信息冗余, 无需重传机制即可构造出原始消息。
2 数据压缩算法
大量原始数据转发到基站的路途中将很快耗尽所经过节点的能量, 导致传感器网络死亡, 为了减少数据传输过程的数据量, 从而节省网络能量, 延长网络生命周期, 很多专家学者提出, 通过节点间的协作对传感器网络采集到的数据进行网内处理, 也就是适当地采用数据压缩方法, 使得数据量减少[3]。
2.1 数据压缩方法分类
对观测数据的压缩处理, 可在传感器节点和基站两端分别采用压缩和解压缩技术。在数据发送前提高编码效率, 或者是根据不同应用需求 (例如图像特征的信息, 直接处理非常复杂) 对信息进行数据变换, 实现发送数据前的压缩操作。基站收到数据后再进行解压缩, 降低传输过程中大量冗余数据造成的能量损耗。常见的数据压缩方法有:
(1) 压缩编码。按照特定的编码机制利用较少的数据位元 (或者其他信息相关的单位) 表示信息, 从压缩结果来看可以分为有损压缩和无损压缩, 由于传感器采集的多数为模拟信息, 所以主要采用有损压缩算法。而针对不同的传感器数据特征又可以采用标量数据压缩算法或者矢量数据压缩算法, 并根据不同的数据类别选择对应的数据压缩算法。
(2) 汇聚节点处融合。对于覆盖范围较大的传感器网络, 源节点到基站之间的数据转发采用多跳方式比点对点直接通信更能节省能耗。转发路径上的节点作为汇聚节点, 可以在不丢失信息的前提下通过排序编码丢弃部分于汇聚节点汇合的数据, 实现数据压缩。
(3) 依据数据空间相关性。地理位置相邻的传感器节点收集到的数据存在相关性, 在多个节点中选取一个有代表性的节点数据, 将其完整地发送至基站, 而其他节点的数据提取出偏差部分并压缩后发送, 基站最后通过压缩数据和未压缩数据之间的相关性进行解压缩来重构得到原始数据。
(4) 依据数据时间相关性。单个传感器节点收集到的数据在时间上可能是相关的, 使用例如小波变换等信号处理办法来去除其中的冗余信息, 并在保持信号的统计特性的基础上实现数据压缩的目的。
2.2 典型的数据压缩算法
文献[4]提出了一种能量高效的分布式线性回归数据采集优化策略, 根据同一监测区域附近的传感器节点采集的数据测量值具有极大相关性这一特点, 通过构建线性回归模型表示传感器的感知数据。
假设传感器在时间t1, t2, …tm上感知的数据为y1, y2, …ym, 则构建满足逼近误差最小δi=Y (ti) -yi的函数Y (函数用多项式表示, Y (t) =λ1+λ2t+λ3t2+λ4t3) ;构建函数模型之后, 多个实际测量值仅仅需要在网内传输4个参数值, 即λ1、λ2、λ3和λ4即可得到原始数据。为了使估计值的逼近误差δi最小, 选定使得逼近误差向量的范数最小为优化目标, 即。另外, 文中还提出了回归模型的参数更新方法以采用增量方式更新线性回归系统模型的矩阵和向量参数。该模型大大减少了传感器节点间频繁数据传输带来的通信开销, 降低了节点的能量消耗, 不足之处在于模型中矩阵的运算量偏大。
文献[5]利用一维Haar小波分解算法, 对数据向量通过逐级分解以得到近似分量和细节分量, 针对误差‖e‖∞形成小波系数的误差树, 再根据小波系数的值和误差限ε来判定哪些节点可以被零化, 并通过量化系数的熵编码提高数据的压缩效率, 从而减少传输的数据。此外, 文中还提出了多属性的误差有界小波数据压缩算法, 对每个节点在某时刻采集的多种不同属性的数据进行数据压缩。方案中, 首先对数据进行规范化, 用二维Haar小波变换进行全分解;再根据不同属性的感知数据以及同一属性不同时段的数据具有相关性的特点, 选出基信号, 回归表示其他信号。方案的不足之处在于, 基信号挑选算法将不同的属性按相关性分到某个基代表的组中, 而为了使得误差越小, 需要的基就越多, 压缩效果也将变差。另外, 将基信号等分分段实现多次回归, 但当基分段太多时, 却易造成该段回归结果可能会超过规范化误差的结果。
考虑到网络中部署的传感器节点在监测数据行为上存在数据相关性, 比如在某些应用中, 一个特定区域可能被多个传感器覆盖, 这些传感器很可能监测到同一时间, 产生相同的数据而造成不必要的能耗上的浪费, 文献[6]介绍了一种通过各传感器节点遵循关联机制, 来实现网内数据压缩以减少数据量的行为策略。主要步骤为:
(1) 网络中包含n个传感器节点, 构成集合S={s1, s2, ……, sn}, 时间片λ根据用户可任意设置大小。每个传感器均有一个大小为B的缓冲池, 每经过一个时间片, 各传感器节点根据是否监测到事件发生来设置缓冲区入口。
(2) 传感器的行为数据在一定的时间间隔后发送至基站, 基站通过行为数据获知在这段时间内该节点监测到事件发生的次数。
(3) 该网络中的数据约简是借助创建数据收集树实现的, 称之为最小的节点的数据收集树 (minimum nodes data gathering tree, MNDGT) , 另外结合分布式的约减机制。MNDGT树中只包含了参与制定传感器关联规则的节点以及与基站距离近的部分节点。
(4) 数据收集沿着树形结构从最低层至最高层。在MNDGT最后一级每个叶节点将参与集合发送至双亲节点。双亲节点则根据这些集合来计算所有子节点的交集, 并依据一定的规则设置活动节点。
文献[7]提出了一个分布式数据融合算法, 其主要思想是在中间节点将传入的多个数据包通过PCA (principal component Analysis) 方法将其压缩成一个数据包, 再将融合结果发至父亲节点。具体的数据压缩过程是基于多跳网络, 即假设网络中的节点需通过多跳方式将采集的数据发至基站, 但是最多只能经过两跳, 路径可以任意选择且不一定为最短的路径。再将路径上的节点构造成一棵树型结构, 基站为该数据结构中的根节点。
文献[8]首先提出了一种具有普遍性的体系结构来减少数据流造成的能量开销和延迟方面的影响, 在该体系结构中, 把监测节点采集过程中数据的产生 (感知流) 或是当一个节点转发数据至另一个节点 (路由流) 视为输入流, 当传感器获取过多的样本, 并且不能动态校准处理比目前更多的数据处理时, 通过应用层对感知流进行数据压缩;根据不同应用的需求, 当网络中不需要对过多的数据进行数据转发时, 则交给路由层进行数据压缩以避免无法控制的丢包行为。应用层的数据压缩算法主要分为随机采样、居中采样、多元抽样、概要数据等环节, 压缩后的数据流如果需要转发给其他节点, 则通过网络层进行重新封装后再发给sink节点。
3 结束语
在传统的数据传输模式下, 无线传感器网络中的各节点如果传输全部的感测信息, 将因为大量冗余信息的传输使得能量消耗过大, 因此, 先对数据进行融合处理再发给基站是非常必要的。本文对时间冗余、空间冗余和信息冗余等方面进行了分析, 对数据压缩算法进行了简单的分类, 并对几种典型的数据压缩算法进行了分析比较, 下一步的工作将在这些研究的基础上, 提出考虑数据的空间相关的数据压缩算法。
参考文献
[1]孙利民, 李建中, 陈渝, 等.无线传感器网络[M].北京:清华大学出版社, 2005.
[2]SONG C, LIU M, CAO J, et al.Maximizing network lifetime based on transmission range adjustment in wireless sensor networks[J].Computer Communications, 2009, 32 (11) :316-1325.
[3]谢志军, 王雷, 林亚平.传感器网络中基于数据压缩的汇聚算法[J].软件学报, 2006, 17 (4) :860-867.
[4]宋欣, 王翠荣.基于线性回归的无线传感器网络分布式数据采集优化策略[J].计算机学报, 2012, 35 (3) :568-580.
[5]张建明, 林亚平, 周四望, 等.传感器网络中误差有界的小波数据压缩算法[J].软件学报, 2010, 21 (6) :1364-1377.
[6]BOUKERCHE A, SAMARAH S.In-network data reduction and coverage-based mechanisms for generating association rules in wireless sensor networks[J].IEEE Transactions on Vehicular Technology, 2009, 58 (8) .
[7]ROOSHENAS A, RABIEE H R, MOVAGHAR A, et al.Reducing the data transmission in wireless sensor networks using the principal component analysis.Intelligent sensors, sensor networks and information processing (ISSNIP’10) .
数据压缩算法研究 篇4
面对煤矿生产规模的逐步扩大, 在数据自动化采集过程中涉及到的数据也在成倍增长。面对采集到的大规模监控类数据量, 如何合理、高效地进行数据存储及查询是当前煤矿类软件系统需要处理的一个关键问题, 必须考虑对数据进行压缩处理。
由于生产过程实时数据都是秒级数据, 如果采用传统的直接存储方案, 将会占用大量的存储空间, 大大增加存储成本[1]。生产过程采集到的原始数据中包含大量的冗余和不相关信息, 在保留关键特征数据的基础上去除冗余和不相关信息, 就可达到数据压缩的目的。数据压缩的本质是数据变换, 它试图在压缩比和信号保真度之间寻求一种折衷。过程数据压缩方法基本分为3种[2,3], 即分段线性方法、矢量量化方法及信号变换法[4]。而分段线性方法又包括矩形波串法、向后斜率法、SDT (Swing Door Trending, 旋转门) 法[5]及PLOT (Piecewise Linear On-line Trending, 分段线性在线趋势) 法。
煤矿生产过程中采集到的数据大多是缓慢变化的数据, 采用分段线性化的方法可以很好地表示历史数据的变化趋势。而在实际应用中, SDT数据压缩算法是分段线性方法中比较常用的一种方法, 其突出优点是算法简单、执行速度快。本文对该数据压缩算法的原理及应用推导步骤进行分析, 给出了压缩数据解压还原的方法, 并结合实际应用项目数据给出压缩效果, 证明了该算法的有效性。
1 SDT数据压缩算法原理
SDT数据压缩算法基本原理如图1所示。数据点a上下各有一点, 它们与数据点a之间的距离为E, 这2点作为“门”的2个支点。当只有第1个数据点时, 2扇“门”是关闭的。随着采集数据点的增加, “门”的敞开角度逐步增大。每扇“门”只能向更大的敞开角度打开而不能闭合, 只要2扇“门”未达到平行, 即2个内角之和小于180°, 这种“转门”操作就可以继续进行。图1中的数据点a, b, c, d, e经过SDT数据压缩算法处理后, 将只存储数据点a和数据点e;从点e开始, 2扇“门”再恢复到初始状态, 开始时2扇“门”关闭, 然后逐步打开, 到数据点h后2扇“门”再次平行, 所以数据点e, f, g, h经过SDT数据压缩算法处理后, 将只存储数据点e和数据点h, 当然数据点e在前一处理步骤中已经存储, 将不再重复存储。
2 SDT数据压缩算法的应用推导
SDT数据压缩算法的推导步骤如图2所示。2扇“门”fa和ga在经过数据点b, c, d的SDT数据压缩算法处理后, 两者所处的开合状态为fd和gc。对于数据点d, 是否满足“转门”操作的要求, 判断标准为α+β<180°。
设点f坐标为 (0, fy) , 点g的坐标为 (0, fy+2 E) , 点c的坐标为 (cx, cy) , 点d的坐标为 (dx, dy) 。则有
根据以上推导结论, 即可通过编程实现SDT数据压缩算法。
模拟量数据可采用SDT算法进行数据压缩;开关量数据在数据值发生变化时进行存盘;对于累计量, 可在本次值与上次值之差小于零时存储上次累计量的值。
在实现SDT数据压缩算法进行数据压缩的过程中, 模拟量数据压缩还要在SDT算法的基础上增加对特殊情况的处理:
(1) 模拟量数据状态为故障等的处理。无论模拟量数据在发生故障前的一次采样数据是否满足SDT算法进行存储的条件, 都需要对该采样数据进行存储。对于故障的第一个采样数据也要作为压缩数据进行存储, 在故障结束后的第一个采样数据也要作为压缩数据进行存储。
(2) 模拟量采样值突变情况的处理。当模拟量值发生突变时, 为了使压缩后的数据能正确反映出数据突变的情况, 需要将突变的采样值、突变前的一个采样值作为压缩数据进行存储。
3 压缩数据的解压还原
当需要查看指定测点的历史数据时, 就需要对相关存储数据进行解压还原。数据的解压还原可以通过采取直线趋势化逼近的方法进行还原, 该过程相对简单, 但模拟量测点和开关量测点要分开进行还原处理。
3.1 模拟量测点数据还原方法
需要还原的时间段为StartTime到EndTime, 首先到数据库中查找出该测点在StartTime到EndTime内所有数据的集合DataSet{data (1) , data (2) , …, data (N) , …, data (end) }, 各个数据对应的时间集合TimeSet为{time (1) , time (2) , …, time (N) , …, time (end) }。如果需要还原出时间点time (X) 对应的数据RestoreData (X) , 假设time (X) >time (N) , time (X)
如果需要还原的时间点time (X) >StartTime, 且time (X)
(1) 可以简单的处理, 即RestoreData (X) =data (1) 。
(2) 从数据库中查出该测点在时间time (1) 之前的第1条数据data (0) , 其对应时间为time (0) , 则RestoreData (X) =[time (X) -time (0) ]×[data (1) -data (0) ]/[time (1) -time (0) ]+data (0) 。
对于time (X) >time (end) , 且time (X)
特殊情况处理:
如果从数据库中查找出该测点在StartTime到EndTime内所有数据的集合DataSet为空, 则需要从数据库中查找出该测点在时间StartTime之前的第1条记录Data (start) , 其对应时间为Time (start) , 以及该测点在时间EndTime之后的第1条记录Data (end) , 其对应时间为Time (end) 。最后, 对于需要还原的时间点Time (X) , 其对应的还原数据为RestoreData (X) =[time (X) -time (start) ]×[data (end) -data (start) ]/[time (end) -time (start) ]+data (start) 。
3.2 开关量测点数据还原方法
需要还原的时间段为StartTime到EndTime, 首先到数据库中查找出该测点在StartTime到EndTime内所有数据的集合DataSet{data (1) , data (2) , …, data (N) , …, data (end) }, 各个数据对应的时间集合TimeSet为{time (1) , time (2) , …, time (N) , …, time (end) }。如果需要还原出时间点time (X) 对应的数据RestoreData (X) , 假设time (X) >time (N) , time (X)
如果需要还原的时间点time (X) >StartTime, 且time (X)
特殊情况处理:
如果从数据库中查找出该测点在StartTime到EndTime内所有数据的集合DataSet为空, 则需要从数据库中查找出该测点在时间StartTime之前的第1条记录Data (start) , 其对应时间为Time (start) , 以及该测点在时间EndTime之后的第1条记录Data (end) , 其对应时间为Time (end) 。如果2条记录均能查到, 则对于需要还原的时间点Time (X) , 其对应的还原数据为RestoreData (X) =Data (start) 。
4 数据压缩效果实验
笔者编写相关实验程序对煤矿现场的瓦斯采集数据进行了压缩分析实验。现场某瓦斯传感器的原始历史数据曲线如图3所示, 其中该瓦斯传感器的原始数据条数是19 212条。
该瓦斯传感器的原始历史数据按SDT压缩算法进行处理后的压缩数据曲线 (E=0.01) 如图4所示, 其中该瓦斯传感器原始历史数据压缩处理后的数据条数是777条。
从图3、图4可看出, 该瓦斯传感器的原始采样数据曲线和压缩处理后的数据曲线整体走势一致, 压缩后的数据曲线能够较为正确地反映出该瓦斯传感器的历史数据信息;该瓦斯传感器的原始数据条数是19 212, 当E=0.01时压缩后的数据条数为777, 压缩比率为4.04%, 实现了对原始数据较高的压缩比, 节省了大量的存储空间。
5 结语
通过对SDT数据压缩算法的应用推导, 并结合煤矿类软件系统中采样数据的具体特点, 给出了SDT数据压缩算法在煤矿类软件系统中的具体应用实现。实验结果表明, 压缩后的数据曲线能较为准确地反映出数据的走势和变化, 并有效减少数据存储量。将SDT数据压缩算法在现有的大数据量煤矿类数据采集软件系统中加以应用, 将能有效解决大数据量存储占用空间资源大、耗时长的问题, 从而在降低软件系统成本的同时提高用户的使用满意度。
摘要：为了解决煤矿类软件系统在大规模数据量情况下的数据高效存储和查询问题, 提出了一种将旋转门SDT数据压缩算法应用于煤矿类软件系统的方案。介绍了该算法的原理及应用推导, 给出了模拟量和开关量压缩数据解压还原方法和特殊情况处理方法。应用结果表明, 该算法压缩比高, 节省了大量的存储空间, 能准确地反映出数据的走势和变化。
关键词：过程数据,数据压缩,SDT算法,解压还原
参考文献
[1]段培永, 姚庆梅, 汤同奎.一种用于过程数据压缩的矩形波串法及其性能分析[J].厦门大学学报:自然科学版, 2001, 40 (增刊1) :265-268.
[2]段培永, 汤同奎, 邵惠鹤.一种新的Boxcar算法及其在数据压缩中的应用[J].计算机应用, 2001, 21 (9) :14-17.
[3]董栋, 刘强.一种改进的分段线性趋势压缩算法及应用[J].微计算机信息, 2006, 22 (36) :200-202.
[4]赵利强, 于涛, 王建林.基于SQL数据库的过程数据压缩方法[J].计算机工程, 2008, 34 (14) :58-59.
数据压缩算法研究 篇5
1. 提升变换理论
传统的第一代小波变换是在欧式空间内通过基底的平移和伸缩构造小波基, 不适合非欧式空间的应用。因此, 小波提升方案应运而生, 它是构造第二代小波变换的理想方法。1996年Sweldens提出了小波的提升算法, 有效地解决了传统的基于Mallat的塔式分解小波变换算法计算量大、对存储空间的要求高的问题, 从算法方面提高了小波变换的实现效率。
小波提升算法的特点:它继承了第一代小波的多分辨率的特性;不依赖傅立叶变换;不占用系统内存;反变换很容易从正变换得到。由于提升模型实现了真正意义上的无损可逆小波变换, 因此, 在数据压缩传输领域得到广泛应用, 并成为JPEG2000标准的核心部分。提升模型避免了普通小波变换借助快速傅立叶变换完成卷积操作的步骤, 整个过程仅含有对整数的移位运算和加减运算, 节省了硬件开销, 便于在WSN这类微处理器中实现。提升变换的框架如图1所示。
小波提升算法的基本思想是将现有的小波滤波器分解成基本的构造模块, 一般分以下3个步骤完成小波变换。即:分解 (split) , 预测 (predict) , 更新 (update) , 分解是将输入信号根据奇偶性分为2个序列, 预测是利用P滤波器作用于偶数。序列得到奇数序列的预测值, 得到的预测误差即为高频系数, 更新是使用预测误差线性组合更新偶数序列, 得到低频系数。“提升”算法的基本思想是将现有的小波滤波器分解成基本的构造模块, 分步骤完成小波变换。
2. 基于提升小波变换 (LWT) 的数据压缩算法
在WSN中, 树型结构是最常见的拓扑结构。网络中的所有节点形成一棵以基站为根节点的数据收集树。在每个采样周期, 传感节点首先采集数据, 然后将其发送到自己的父节点。某个节点收到其子节点发来的数据后, 将其转发到自己的父节点。网络中所有节点的数据通过这种多跳路由的方式最终汇聚到根节点。本文提出的基于提升小波变换的数据压缩算法就是基于这种树型网络拓扑结构的。
2.1 算法原理
WSN中传感节点的资源十分有限, 主要体现在电池能量、处理能力、存储容量以及通信带宽等几个方面。在采集和传输信息的过程中, 采用各个节点单独传送数据到Sink节点的方法是不合适的, 一方面浪费通信带宽和能量, 另一方面造成了频繁的冲突碰撞, 降低了通信效率。
针对WSN节点资源有限和数据传输冗余, 本文提出了基于提升小波变换的数据压缩算法。这种算法通过提升格式, 消除提升小波变换所需的额外的数据传输和计算, 利用分布式并行计算把整个提升小波变换算法的计算量分布于各个节点之中, 对于每个节点来说, 能耗都很小, 易于在WSN这样资源极其有限的系统中实现。这种方法能有效消除WSN中节点内和节点间的信息冗余, 大大节省无线传输所消耗的能量。整个算法充分考虑了需采集和传输的油料信息数据的特点, 具有速度快、内存占用小、易于硬件实现的特点。
2.2 算法实现
提升小波变换算法是将普通小波变换过程分为分解、预测和更新三个阶段。假设一个信号数据序列Si, 提升小波变换的步骤为:
(1) 分解 (split) :假设一个原始数据集, 将数据分成两个子集Si-1和di-1。最简单的方法就是把Si序列分成偶数序列di-1和奇数序列Si-1, 即split (Si) = (Si-1, di-1) 。
(2) 预测 (predict) :针对数据间的相关性, 采用一个与数据结构无关的预测算子P。先将P滤波器作用于偶信号上得到奇信号的预测值P (Si-1) , 实际应用中, 预测值P (Si-1) 很可能接近di-1, 这样就可用新的di-1来表示di-1与P (Si-1) 的差值, 即di-1=di-1-P (Si-1) , 此差值di-1将比原来的di-1少很多信息。
(3) 更新 (update) :通过分解产生的系数子集Si-1的某些整体性质 (如均值、消失矩) 和Si不一致, 故引入更新算子U, 对Si-1更新, 保持信号Si的一些整体性, 此时有更新的Si-1=Si-1+u (di-1) 。
2.3 分散计算量
WSN的通信模式一般是多个无线传感器节点向一个Sink节点发送数据, 无线传感器节点转发收到的数据, 形成一个树型分簇网络结构。本文提出的提升小波分解利用WSN的树型分簇结构, 使小波变换的计算量分散在各个节点之间, 树型分簇结构中的每一层完成一级小波分解, 所有节点共同参与完成小波分解计算。
3. 算法分析与仿真
为了评价基于提升小波变换的数据压缩算法的性能, 用MATLAB工具进行仿真, 实验数据取自热带大气海洋项目 (TAO, http://www.pmel.noaa.gov/tao/) , 实验所用数据集是TAO在多个地点 (moorings) 的不同深度共10个点的传感器从2010年1月16日到2010年5月16日每天12:00采集到的海水温度数据。提升小波基采用Haar小波的提升变换, 并与直接传输法和基于普通小波变换的数据压缩算法进行了比较, 从重构信号质量和节能性方面评价了基于提升小波变换的数据压缩算法的性能。
将100个节点随机分布在80m×80m的正方形区域内, 组成一个WSN, 基站节点位于正方形的中心, 每个传感器的感知半径为10m, 传感器的通讯半径等于它的感知半径, 每个节点的初始能量为6J。具体仿真结果如图3、图4所示。
图3描述了两种算法的性能比较 (小波分解层数j=3) , 从图中可以看出, 基于普通小波变换 (WaveletTransform, WT) 的数据压缩算法, 其重构信号质量随着压缩比的提高比基于提升小波变换 (Lifting Wavelet Transform, LWT) 的数据压缩算法要差, 这是由于基于LWT的数据压缩算法是根据信号的局部特性选择预测环节, 预测环节的选择信息不需要额外的存储空间, 而且数据也不会由于阈值处理和压缩编码受到损害, 所以基于LWT的数据压缩算法的重构信号数据质量要好一些。基于提升小波变换的数据压缩算法是利用节点之间的预测和更新来消除信息的冗余, 它在压缩性能和可扩展性方面表现良好。
图4表示了各种算法DT、WT、LWT在把一定量数据传输到Sink节点时所消耗的能量随着传输距离 (感知节点到Sink节点的跳数) 的变化而变化的关系。由于数据在压缩后, 所需要传输的数据是固定的, 所以所有算法的能耗和传输的距离基本都成线性关系。在传输距离为0时, 整个网络所消耗的能量就是算法本身所消耗的能量。因为基于小波变换的数据压缩算法需要额外的计算和无线数据通信, 所以此时基于小波变换的数据压缩算法能耗较高, 而没有任何计算量的直接传输方法 (Direct Transmission, DT) 能耗则是最少的。然而, 直接传输方法 (DT) 由于没有经过压缩, 能耗随着传输距离的增大而迅速提高。在传输距离达到一定程度时, 基于提升小波变换的数据压缩算法在通信能耗上的优势补偿了小波分解时额外的能量消耗, 成为几种算法中最节能的算法。
4. 结论
数据压缩算法研究 篇6
关键词：数据压缩,PPM,PPMD
引言
数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度,达到增大数据密度,最终使数据的存储空间减少的技术。数据压缩就是将字符串的一种表示方式转换为另一种表示方式,新的表示方式包含相同的信息量,但是长度比原来的方式尽可能的短。对于无损压缩而言,PPM模型与算术编码相结合,已经可以最大程度地逼近信息熵的极限。看起来,压缩技术的发展可以到此为止了。不幸的是,事情往往不像想象中的那样简单:算术编码虽然可以获得最短的编码长度,但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。
1. 常用数据压缩算法
1.1 Huffman编码
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。基本的原理是为每个符号找到新的二进制表示,从而通常符号使用很少的位,不常见的符号使用较多的位。
1.2 LZW压缩算法
LZW是Lempel—Ziv—Welch的缩写,主要用于图像数据压缩.对于简单平滑图像且噪声小的信号源具有较高的压缩比,并且其压缩和解压缩速度也比较快。
1.3 算数编码
Huffman编码解决的是整数位编码问题,而这一点有时可能成为一个问题。例如,如果一个字符的概率是1/3,则编码该字符的最优位数是1.6位左右但Huffman编码却必须给代码指定1位或2位,而无论哪一种选择都将导致比理论上可能的长度更长的压缩信息。
1.4 PPM数据解压缩算法
PPM(Prediction by Partial Matching)是一种上下文统计模型技术。它根据输入字符串中一定长度的上下文后面字符出现的次数,得出每个上下文的预测概率,然后利用多个上下文模型来得出输入字符出现的概率,最后根据该概率用算术编码对该字符进行编码。
根据最近输入的字符,来预测即将输入的下一个字符,可以达到数据压缩的目的。PPM就是利用了这种方法。利用最近输入的几个字符(叫做上下文模型),来预测下一个字符。其中,上下文模型的长度k可以从0到已输入字符的最大长度k不等。
对于k长度的上下文模型来说,首先要计算在已输入字符串中,每个k长度的子串后面不同的字符出现的次数,然后可以得到该上下文模型的预测概率。预测概率主要用于计算在该上下文模型后面输入字符出现的概率,以便于用算术编码对该字字符进行编码。这样每个不同长度的上下文模型可以得到相应的预测概率。
因为每个模型具有不同的k值。在计算输入字符出现的概率时,一般都是从最长的模型开始的。对于某个k长度的模型来说,当输入的字符已经被该上下文模型预测出时,该输入字符出现的概率就是预测概率。而当一个新字符,也就是说该上下文模型不能预测出的字符出现时,输入字符出现的概率就无法得到,也就不能对该字符进行编码。这时,就需要用到”跳转”(Esc)概率将不同长度上下文模型各自的预测概率联系起来。”跳转”概率就可以将模型从k跳f,lk-1,看k-1长度的模型能不能预测出该字符。如果可以,该字符的概率就是”跳转”概率k-1模型的预测概率;如果不能,”跳转”过程将一直进行直到某个模型可以预测出该字符。有了”跳转”机制以后,某个字符的预测概率就由可以预测出该字符模型和它以前的所有模型中的”跳转”概率来决定。为了保证无论出现什么字符,最后”跳转”过程都能结束,最低长度的模型中必须包括字母表中所有的字符。根据计算”跳转”概率的方法不同,PPM算法有很多类型,有A,B,C,D,P等形式。
2. 词库压缩程序的设计和实现
2.1 选择PPMD算法为词库解压缩算法的依据
根据计算”逃避”或“跳转”概率的方法不同,PPM算法有很多类型,有A,B,C,D,P等形式。这些不同的模型的“逃避”概率计算方法如下图所示:
以上图中所示的表中:为已输入字符串中的总字符数;U为已输入字符串中不同字符类型总数;t,为已输入字符串中字符出现次的总字符数.越往下版本越高,压缩效果也就越好。
PPMD算法在运行时,对内存的要求不是特别高,运行速度比较快。PPMD算法的阶数可以取1-16的阶数。当阶数落在2-3范围时的压缩率跟ZIP,BZIP2可比较,阶数在4-6范围之内时,压缩率比ZIP,BZIP2快,而且运行速度比ZIP,BZIP2快。在高阶数范围8-16之内时,PPMD算法各方面的表现极为突出。因此,在此系统的词库压缩程序中使用了PPMD算法,并且把阶数选为16。
2.2 词库压缩程序的设计
设计词库压缩程序思路:
使用Dao技术操作数据库。当用户选择某数据库时,首先检查次数据库是否包含名称为DictTag和Tags的两个数据表。当用户选择某个数据表时检查该表是否符合压缩程序的要求。若不符合,则提示给用户。选择好压缩的数据表之后,首先对数据进行分析。在分析过程中主要完成单词和解释字符串的长度,写入压缩文件时使用的数据包编号的计算等。压缩后的词库的名称填写,源语言和目标语言的选择,排序规则的选择等。其中,排序表必须为Excel文件,而且表的结构也要符合规定。生成词库文件时,首先读取单词和单词的长度和解释的长度,先把这些写入文件,然后再把单词解释部分压缩后写入词库文件。
为了方便使用我们在C++中设计了两个类,第一个类是包含PPMD算法功能的类,第二个类是对外提供接口的操作类。在第一个类中还设计了保存上下文环境的结构体PPM_Context。以下是此结构体详细设计结构:
第一个类包含了Start Sub Allocator,Stop Sub Allocator,GetUseMemory,EncodeStream,DecodeStream等五个函数,其中对外可见的有GetUseMemory,EncodeStream,DecodeStream。
第二个类包含了CompressStream,DecompressStream,GetRatio GetCompressTime,GetDecompressStream,GetInputSize,GetOutPutSiz e,GetMemUsage等函数。
3. 小结
对数据压缩技术进行了论述,还有提出了基于PPMD算法的词库压缩程序的设计和实现过程。
参考文献
[1]Shkarin,D.(2001)Improving the efficiency of PPM algorithm.Problems of Information Trans-mission,34(3):44-54,in Russian.
[2]Cleary,J.G.and Witten,I.H.(1984)Data compression using adaptive coding and partial string matching.IEEE Trans.on Comm.,32(4):396-402.
[3]Moffat,A.(1990)Implementing the PPM data compression scheme.IEEE Trans.on Comm.,8(11):1917-1921.
[4]Howard,P.G.(1993)The Design and Analysis of Efficient Lossless Data Compression Systems.PhD thesis,Brown University.
[5]李晓翔,王淑华,赵正校PPM缩算法在图像压缩中的应用[A]计算机工程2002年7月第28卷第7期.
数据压缩算法研究 篇7
电能质量问题引起了供电部门和广大电力用户的普遍重视,目前大多数输配电系统都安装有电能质量监测设备。由于所监测到的相关数据十分庞大,加重了数据存储的负担,也降低了数据的传输效率,因此有必要研究具有高压缩性能的数据压缩方法。至今已有大量的学者对电能质量数据压缩问题进行了研究[1,2,3,4,5,6,7,8,9]。
本文引入数字图像平滑技术,并结合了提升格式的二维小波变换、图像多级树集合分裂SPIHT(Set Partitioning In Hierarchical Tree)编码算法以及DEFLATE编码对电能质量数据进行更有效的压缩。
1 电能质量数据压缩整体方案
本文所提出的电能质量数据压缩整体方案如图1所示。考虑到电能质量信号的周期性特点,为了进一步挖掘这类信号的循环间冗余,首先按整数倍周期将所采集到的一维电能质量原始数据转换为二维矩阵,以信号周期为行、采样点为列进行排列。然后采用数字图像平滑技术对该二维矩阵进行模糊化处理。最后基于提升格式的二维小波变换、图像SPIHT编码以及DEFLATE编码算法进行数据压缩。数据重构则是数据压缩的逆过程,首先对压缩后的数据进行DEFLATE解码、SPIHT解码以及提升格式二维小波反变换,然后再进行逆平滑(清晰化)处理,对逆平滑后的二维数据进行一维转换后即得到重构的一维电能质量数据。
2 图像平滑
图像进行平滑处理后更适合于小波变换编码,更有利于被压缩。本文采用文献[10]所提到的平滑算法,该算法含模糊化以及清晰化2个过程。
模糊化过程:保留维数为[M,N]的图像二维矩阵的第1行和第1列,对其他相邻行列间做如下模糊化运算:
其中,i=2,3,…,M;j=2,3,…,N。经模糊化后相当于用均值代替原来的数值。
清晰化过程:保留维数为[M,N]的待清晰图像二维矩阵的第1行和第1列,对其他相邻行列间做如下清晰化运算:
其中,i=M,M-1,…,2;j=N,N-1,…,2。清晰化过程实际上相当于模糊化过程的逆运算过程。
3 提升格式的二维小波变换
与传统的小波变换相比,提升格式的小波变换具有运算简单、速度快、耗费存储空间少等优点。
本文选用静止图像压缩标准JPEG2000中推荐使用的CDF(9,7)提升小波变换对模糊化后的二维电能质量信号进行分解与重构。CDF(9,7)提升小波变换具有线性相位、消失矩大、能量集中性好等特性,非常适用于图像数据的有损压缩,其提升格式如图2所示[11,12]。
CDF(9,7)提升小波首先将输入x[n]分裂为奇数序列d[n](0)=x[2n+1]与偶数序列c[n](0)=x[2n];然后经过2次预测和更新过程得到预测序列d[n](2)以及更新序列c[n](2);为了便于计算,最后分别对预测和更新序列进行系数缩放得到逼近信号d[n]以及细节信号c[n]。其中,图2中CDF(9,7)提升小波的参数分别为:α=-1.586 134 34,β=-0.052 980 118,γ=0.882 911 076,δ=0.443 506 852,ζ=1.149 604 39。
4 图像SPIHT编码算法
SPIHT算法是一种基于小波域系数零树结构的静态图像压缩方法,采用不重要系数表LIP(List of Insignificant Pixels)、重要系数表LSP(List of Significant Pixels)和不重要集合表LIS(List of Insignificant Sets)来动态控制小波系数的分类扫描和精细扫描过程[13]。
对于节点(i,j),定义O(i,j)为其直系子女的坐标集合,D(i,j)为其直系后代的坐标集合,L(i,j)=D(i,j)-O(i,j)为其非直系后代的坐标集合,H为所有根节点的集合。下面介绍SPIHT编码过程。
a.算法初始化。确定初始量化门限2n,置LSP为空表,将坐标(i,j)H放入LIP,(i,j)H中带有子孙的加入到LIS,并标记为D(i,j)类集合。
b.分类扫描过程。首先扫描LIP,若该像素有效(≥2n),则将其移到LSP并输出其符号位。然后扫描LIS,对于D(i,j)类集合,若其为有效集合则将其分解为(k,l)O(i,j)以及L(i,j),分解后的L(i,j)放入LIS尾部,分解后的每个(k,l)项根据其有效性分别放入LSP或者LIP中;对于L(i,j)类集合,若其为有效集合则将其分解为(k,l)O(i,j),分别形成D(i,j),并放入LIS尾部。
c.细化过程。对LSP中每一项(i,j)(本次扫描产生的除外),输出X(i,j)的第n个最高有效值。
d.量化步长更新过程。n=n-1,返回步骤b进行下一步编码。
文献[14]将SPIHT算法简化为一维算法,结合整数小波变换实现了录波数据压缩,但该方法牺牲了算法性能。本文充分利用SPIHT编码算法的优势,直接使用二维SPIHT编码算法压缩转换后的二维电能质量数据。
5 DEFLATE编码
DEFLATE编码是一种字典型无损数据压缩编码算法,该算法具有良好的压缩性能和速度,在ZIP文件压缩以及PNG图像压缩等领域得到了广泛的应用。
DEFLATE编码同时使用了LZ77与哈夫曼编码算法,其编码过程主要包括2个方面:首先由LZ77编码算法压缩数据,在该过程中采用哈希表来存储字典;然后对LZ77编码后的数据再通过哈夫曼编码进一步进行压缩。
6 数据压缩实验结果及分析
采用压缩比RCR、信噪比RSNR2个指标来衡量压缩算法的性能,分别定义为
其中,Ho表示压缩前信号的数据量,Hn表示压缩后信号的数据量,xo(i)为原始信号,xn(i)为解压缩后的重构信号,N为信号的长度。
用ATP-EMTP仿真一条750 k V传输线的单相接地故障过程(在0.06 s时单相接地,0.14 s时切除故障),信号基波频率选取为50 Hz,信号采样频率为12.8 k Hz,图3给出了B相电压信号uB的波形。
采用本文所提方案压缩该数据,图4表示在不同压缩码率RC下的压缩效果(u′B为图3中电压uB的重构波形,ue为误差信号)。可以看出,压缩效果与压缩码率有很大关系,压缩码率越高,相应的压缩比越低,信噪比越高。因此,可以根据实际需求通过控制压缩码率来调节压缩性能。
采用文献[15]中方法用Matlab软件随机产生以下扰动信号:骤降、骤升、中断、脉冲暂态、谐波、骤降&谐波、骤升&谐波。信号基波频率选取为50 Hz,信号采样频率为12.8 k Hz,持续采样200个周期。在压缩码率为0.5 bit/pel时,对各类电能质量扰动数据进行压缩的性能指标如表1所示。由表1可以看出,经图像平滑处理后,压缩性能得到了较大提高。
为进一步验证本文所提出压缩算法的有效性,以较为复杂的电能质量扰动骤降&谐波为例,分别采用几种不同的电能质量压缩方法对该类信号进行压缩,其结果如图5所示。可以看出,在压缩比一致的情况下,本文算法能达到更大的信噪比,压缩性能更加优越。
7 结论
本文提出并设计了电能质量数据压缩方案,该方案通过二维表示挖掘了电能质量数据的循环间冗余,同时应用数字图像平滑技术对二维转换后的图像矩阵进行平滑处理,并采用基于提升格式的二维小波变换,该变换具有运算速度快、占用内存小、计算简单、逆变换简单等优点,然后基于图像SPIHT编码以及DEFLATE编码算法压缩二维小波变换后的小波系数。该方案具有较好的压缩效果,同时还可以根据实际情况灵活调节压缩性能。仿真实验结果验证了所提方案能有效压缩电能质量数据。
摘要：为满足电能质量数据存储与传输的需要,基于图像平滑算法、二维离散小波变换以及图像多级树集合分裂编码算法提出了一种电能质量数据压缩新方法。将一维电能质量数据转换为二维矩阵以挖掘电能质量数据的循环间冗余性;应用数字图像平滑技术对二维变换后所得到的电能质量图像矩阵进行平滑处理以有利于二维小波变换编码;结合二维离散小波变换、图像多级树集合分裂编码以及DEFLATE编码算法对电能质量数据进行压缩。仿真实验结果表明,相对现有的电能质量数据压缩方法,所提出的方案不仅能更有效地压缩电能质量数据(同等压缩比的情况下,信噪比更高),而且还可以根据实际需求通过对压缩码率的控制灵活调节电能质量数据压缩性能。
数据压缩算法研究 篇8
小波变换相对于傅里叶变换的不同点在于小波分解可以根据信号特征选取不同的小波函数:选用恰当的小波函数,可以很好地分析信号的特征;相反,若小波函数选取不正确,分解系数很可能淹没信号的特征。目前经典小波中的小波空间和尺度空间是由对同一母小波函数进行伸缩,平移得到的[2],构造起来简单,但单小波基难以与复杂数据的特征波形匹配。为此,文献[3][4]提出了多小波电能质量压缩算法,将小波的光滑性,正交性,紧支性等完美结合起来,提高了压缩效果,但多小波计算需要对信号进行预处理,且需进行多次的小波分解构,大大增加了算法的复杂度。
为了获得多小波基的灵活性同时避免多小波计算量大的问题,文献[5]提出混合小波基的概念,并证明了混合小波基的存在。文献[6]在混合小波基的基础上提出混合小波包(Combined Wavelet Packets,CWP)。本文在此基础上优化混合小波包的算法:利用自定义的信息代价函数,通过遗传算法优化小波函数族,使得电网故障数据可以用最合适的混合小波包基来分解。与传统的小波包相比,在保持原有算法复杂度基本不变的情况下,获得更好的时频域特性和压缩性能。
1 混合小波包
1.1 小波包算法
经典小波算法具有小尺度大频窗,大尺度小频窗的时频分布规律,而电力系统中故障数据的暂态或稳态扰动通常只出现在特定频带,为了更好去除冗余,希望故障存在频带具有最大化时/频域分辨率,解决办法是在小波算法基础上推广小波包分解,使得频谱窗口进一步细化,以便找到合适的小波包树结构,用最少的小波系数提取出电力系统故障信息。
构造小波包是从长度的2N的滤波器h(n)和g(n)开始,定义函数族{wn(t)},n=0,1,3…,当n=0时,w0=(t)是尺度函数,w1=ψ(t)是小波函数,小波包WP1可以由下列递推式生成:
1.2 混合小波包
不同小波函数具有不同时频特性[7]:电网监测系统录波数据的低频基波部分通过高正则性,高消失矩的光滑小波基将最大部分信号能量集中;针对故障扰动,选用具有良好的时频局部性短支撑的小波基进行特征匹配,可以有效地表示系统故障的突变特征。混合的小波包可以在不同频段实现不同的小波分解,设小波函数族分别为Ψ[1](t),…,ψ[K](t),对应的小波空间:({Vj}j∈z,φ[1](t),…,{Vj}j∈z,φ[K](t))由k个小波函数可以构成一组混合小波基,再由混合小波基来构造混合小波包,运用提升方案[10]构造有相同的空间结构小波包基,有φ[k](t)∈V0V1,ψ[k](t)∈V1,k=1,2,…,K,而φ[1](2t-n)是空间V1的正交基,所以存在hn[k]∈R,gn[k]∈R,使得混合小波包能够替换1.1中的小波包WP1函数形成的:
用w2n[k](t)代替WP1里的w2n(t)或用w2n[k+]1替换w2n+1(t),就可以得到新的函数族,成为混合小波包。原理证明见文献[5][6]。由图1表明WP1与混合小波包具有相同的空间的结构,每个小波子空间中,混合小波包有k种选择来构成其正交基。
以电压暂降数据为算例,分别采用db1小波包,电力系统压缩最常用小波db4小波包以及混合小波包做2层分解,得到小波系数[7],其中W20为低频系数,W21为细节系数。计算系数W21的能量集中性作为评价值1,具体原理见文献[6],获得的数值越小表示能量越集中;计算W21系数的频带混叠性作为评价值2,具体原理见文献[9],幅值越大表示频带混叠现象越严重。从表1可知混合小波包分解性能优于db4小波包。
将db4和混合小波包分解的系数列出如图2,放大图2可以发现,混合小波包的对应W21中毛刺明显少于db4,说明混合小波包能量集中性好于db4小波包,更多的能量集中到低频系数W20中。
2 优化混合小波包
2.1 基于熵准则的小波包基选择
选择小波包基的基本思想就是通过调整小波包树结构来获得最优基[9],原始信号在小波包正交基上投影,获得一系列的系数,如果只有少数系数很大,那么用这几个少数系数就可以代表信号的特征。定义具有可加性代价函数M为代价函数。则称为M以可加性的信息代价函数。本文采用的是香农熵[7],引入可加函数:
则M(x)可以表示为:
将M(x)为代价信息代价的数字写在树的终端节点里。从最下层的小波包树的终端节点开始,对于非终端节点,我们采用文献[7]的步骤寻找最优树。当小波系数包含信息集中度最小时,M(x)达到最大值,反之,当信息集中度很大时M(x)对应一个极小值。因此只要计算出不同小波包基对应的M(x),具有最小M(x)值的小波包基为最优基。
2.2 遗传算法优化函数族
由上一节得到的熵函数作为遗传算法的代价函数,搜索最优小波函数族ψ[1](t),…,ψ[K](t)。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化概率搜索算法[11]。它将问题的解空间组成的符号串表示为染色体,使用的遗传算子作用于染色体后进行种群繁殖,从而得到新一代种群,通过优胜劣汰完成对染色体的搜索过程。本文引入db小波,sym小波,bior小波,rbio小波,cdf小波构造混合小波函数族[13],以3层小波包分解为例,采用6位二进制遍码构造小波函数族染色体:[w0 w1 w2 w3 w4 w5 w6 w7],长度48位,选择方法为线性排名[11]。设定种群数量500,繁殖100代,交叉系数为250,变异系数位50,交叉算子取为整体算术交叉,变异算子采用多级变异。
按照2.1的熵函数M(x)判断染色体优劣,算法流程如下:
(a)随机初始化种群,计算M(X),保留当前最好解;(b)种群根据计算出的代价函数和选择策略确定选择概率来选择染色体;(c)根据繁殖概率和交叉系数进行繁殖或进行杂交以产生新种群。根据变异系数进行变异操作,跳出局部最优解的限制;(d)计算新种群适应值,保留当前最好解;(e)满足终止条件或迭代次数到达最大值,程序终止送出最优解;否则转到(b)。
图3为优化示意图:迭代40遍获得最优小波函数族。测试样本为电力系统谐波录波数据,横坐标为迭代次数,纵坐标为M(x)值。
3 基于混合小波包的压缩
为了对数据压缩算法的性能进行评估,定义了如下衡量指标[12]:
1.压缩比(CR):
Sraw:原始数据的长度,Scmp:压缩数据的长度
2.均方误差百分值(MSE)和信噪比(SNR,db):
X(i):原始的信号,Xc:(i)重建的信号,N:信号长度。
按照IEC标准测试的代表性的电能质量事件,在表2列出的暂态和稳态电能质量事件的数学模型,随机产生测试样本,持续时间为10个工频周期,实例数据采用电机启动电压电流录波数据。调整采样率12.8k,加入45db背景白噪声。
4 仿真测试
采用db4小波,db4小波包以及混合小波包分别对测试样本做3层分解,为了方便对比,保留分解得到小波系数模值最大的15%用于重构信号,即在保证压缩比一定情况下,比较重构信号的精度。分别列出db4小波,db4小波包以及混合小波包压缩系数重构后与原始信号的误差指标。每种电能质量事件数据随机生成200个测试样本。表3中列出结果是200个样本的测试得到的压缩性能指标的平均值。可以看出混合小波包分解系数压缩后的恢复效果最好,小波包恢复效果略好于小波分解。
评估不同压缩算法的性能也可以在确保压缩精度一定时,比较各自的压缩比。本文采用可以良好筛选奇异信号的模极大值法[8]用于电能质量数据压缩,具体实现为:保留低频系数,对于高频系数可以计算子空间系数平均值mean和相邻的系数差值p,若(p-mean)/mean>η,η为给定阈值(本文为10)那么认为模的最大值存在,p所对应的小波系数得到保留,非模的最大值对应的系数被置零后舍弃。
分别采用模的极大值压缩脉冲振荡的小波系数。图4为压缩比CR和分解层数的关系,横坐标为压缩层数,纵坐标为压缩比。粗点划线为混合小波包压缩曲线;★号线为db4小波包压缩曲线;▲号曲线为db4小波压缩曲线。可以看出,混合小波包在不同分解层数所对应的压缩比都优于db4小波,db4小波包。
5 结论