数据压缩算法研究与设计

文章应用Java编程实现了基于统计模型、字典模型、RLE的压缩算法的数据压缩程序并进行了数据实验。实验结果表明目前的算法不是对所有数据都是最优的。文章还依据文件存储的本质,即任何一个文件本质上都可以转换为一个数字序列,讨论了基于数字序列的无损压缩算法和给出了表整数为幂和的方法,从实验的结果来看,这两种算法在某些情况下的压缩比率比现有压缩算法有所提高,能够将有的文件压缩到40%~95%左右。     

多重压缩DNA序列数据

根据DNA序列数据的特点,提出对DNA序列数据进行多重压缩的思想。多重压缩的首要步骤是扩展字母表。首先对DNA序列数据进行0/1编码,然后每8位转换成一个ASCII码字符,将原来的DNA序列数据仅含有的4个字符扩展到256个字符。第二步采取基于统计模型的Huffman编码压缩算法和基于转换模型的Burrows-Wheeler算法,对扩展后的DNA序列数据进行二次压缩。最后对各种算法的压缩结果进行性能分析比较,比较结果显示,多重压缩算法有较优的压缩比。     

超长DNA序列的高效压缩算法研究

DNA序列虽然只由四个碱基组成,但数据量却非常巨大。有效的压缩DNA数据能大量节省传输的时间开销。目前已经有一些DNA序列专用的压缩算法,如Biocompress,DNACompress和CTW＋LZ。虽然这些算法可以获得较好的压缩比,但是由于采用了传统的CTW算法或Iz系列的字典替换,导致花费太多的时间。为了解决这一问题,提出使用改进的RLE,差分编码和可变长整形等一系列编码方式进行多重压缩的高效压缩算法Dzip。标准DNABenchmark数据测试的实验数据表明,该算法与现行DNA专用压缩算法相比,加速比至少为28。     

一种改进的LZW算法在图像编码中的应用

在医学、安全、遥感等领域,由于数据保真度要求苛刻,对高效的图像无损压缩方法有着迫切的需求.本文通过对字典压缩方法的研究和分析,针对传统LZW方法在建立字典初期压缩效果差这一不足,提出了一种动静结合的改进LZW字典压缩算法.实验结果表明,改进的LZW算法的压缩比相对于传统算法有较明显的提高.     

一种遥测数据实时采集压缩系统的实现

设计了一种对遥测大容量速变数据的实时压缩采集方案,通过采用改善无损压缩算法的压缩比、压缩和解压速度以及算法复杂度等多个数据压缩性能,提出了综合性能较好的LZW编码作为数据压缩的核心算法并通过软件仿真确认其效果和压缩算法的执行速度;利用主控芯片FPGA完成对压缩数据的高精度采集,对研制的数据采集压缩系统进行整体测试,测试结果表明,该系统完成了6路速变参数的实时采集与压缩,压缩比达到1.8∶1以上,各项指标满足了设计要求.     

面向XPath执行的XML数据流压缩方法

由于XML(extensible markup language)本身是自描述的,所以XML数据流中存在大量冗余的结构信息.如何压缩XML数据流,使得在减少网络传输代价的同时有效支持压缩数据流上的查询处理,成为一个新的研究领域.目前已有的XML数据压缩技术,都需要扫描数据多遍,或者不支持数据流之上的实时查询处理.提出了一种XML数据流的压缩技术XSC(XML stream compression),实时完成XML数据流的压缩和解压缩,XSC动态构建XML元素事件序列字典并输出相关索引,能够根据XML数据流所遵从的DTD,产生XML元素事件序列图,在压缩扫描之前,产生更加合理的结构序列编码.压缩的XML数据流能够直接解压缩用于XPath的执行.实验表明,在XML数据流环境中,XSC在数据压缩率和压缩时间上要优于传统算法.同时,在压缩数据之上查询的执行代价是可以接受的.     

基于DSP的存储测试系统设计

针对武器动态测试中的数据参数进行研究,设计了基于TMS320F2812 DSP的数据采集与处理系统.在深入了解信号特征的基础上,结合当今数据压缩发展的前沿技术,设计、改进得到一种可应用于实际情况、能够满足实际需求的LZW和游程混合压缩算法.对数据压缩效果进行了测试,试验证明采用该算法能实时、高效地对AD采集到的数据进行压缩.     

数据采集存储系统无损压缩算法的设计与实现

介绍了几种常用的压缩算法,通过比较分析它们各自原理优点和不足,并结合高速大容量数据采集存储系统的特点,设计改进一种基于字典编码混合编码方法,该压缩方法是一种实时编码的自适应算法,能够适应不同的数据流建立字符串表,实现动态数据实时压缩;实验证明该数据压缩算法移植到硬件电路中,用硬件方法实现数据的实时无损压缩将高速信号变成缓变信号进行传输,降低通信的信道容量,其数据压缩具有实时性,压缩效率高,对数据具有较好的压缩效果,对某些数据的最高压缩比能达到10:1.     

基于多实体的矢量数据压缩改进算法

矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。根据动态规划算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一条带形成最小误差搜索范围,同时条带宽度可自适应调整。并将单一实体的优化压缩算法扩展为基于多实体的压缩算法,解决了图层压缩的全局优化问题。实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差。     

基于小波神经网络的心电数据压缩方法研究

本文在研究心电信号特征的基础上提出了动态心电数据的小波神经网络压缩算法.本算法对原始心电数据实行实时分桢;采用最速梯度下降法优化网络参数.对MIT-BIH数据库中的几组数据进行压缩,给出压缩/重建的实验结果并分析讨论.研究表明:该算法具有参数收敛速度快、数据压缩性能良好的特点.     

基于伪相关反馈模型的领域词典生成算法

本文提出了一种基于伪相关反馈模型的领域词典自动生成算法。将领域词典生成过程视为领域术语的检索过程假设初始检索出来的前若干个字符串与领域相关,将这些字符串加到领域词典中,重新检索,如此迭代,直到生成的领域词典达到预先设定的规模。实验表明,本算法经过若干次迭代后生成的领域词典准确率高于已有领域词典生成算法。     

几种常用无损数据压缩算法研究

随着网络承载的信息量的飞速增长,数据压缩必然会备受人们重视。数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩。文中主要介绍目前用得最多和技术最成熟的无损数据压缩技术,按照无损压缩方法采用的压缩技术的不同,从基于统计的压缩思想和基于字典的压缩思想两个方面对其中最具有代表性的无损数据压缩方法进行了详细的分类讨论和优缺点比较,并对基于字典压缩算法的一些成熟的改进算法进行了汇总介绍,便于对无损数据压缩技术感兴趣的同志学习参考。     

远程故障诊断系统通信数据压缩技术研究与验证

根据远程故障诊断的测试数据的网络传输特点,在详细分析和比较了多种数据压缩算法的基础上,针对LZW算法字典列表长度有限、查找时间长等问题,利用加入了动态延伸列表长度、根据压缩比例调整已有的字典内容和哈希函数查找等方法,对LZW算法提出了改进措施;同时,引入MPEG帧间压缩的思想,设计了一种新的"周期性差值压缩方法",将改进的LZW数据压缩算法与"周期性差值压缩方法"相结合,构成了更有效的级联数据压缩方法,有效地提高了数据压缩比率和效率,并且该算法的处理速度能够满足远程故障诊断系统对通信的要求。     

基于统计的纠错建议给出算法及其实现

介绍了为自动校对系统检测出的错误字串提供有效纠错建议的算法。该算法针对音同、音近、形似或编码键位相近的错误产生特点，构造了字驱动的双向词典和近似字词典，并利用模糊匹配算法为错误字串提供纠错建议，然后对所有建议根据上下文信息和统计频率进行排序。通过在Windows环境下所实现的系统试验，表明正确建议的召回率达到91．8％，而前5选建议的正确率为76．4％。     

稀疏表达的运动数据压缩

随着运动数据越来越多地被应用于动画制作和科研领域,高效的运动数据压缩技术也逐渐成为一个热门的研究课题.基于稀疏表达提出一种新的运动数据有损压缩方法.首先对输入的运动数据进行分析生成稀疏表达字典;然后基于稀疏表达字典对运动数据中的每一帧进行稀疏线性表达;最后用K-SVD算法对字典和稀疏表示进行迭代优化.实验结果表明,本文方法可以达到较高的压缩比(50倍左右),同时保持原始运动数据的完整性,还原后可控制重建误差在肉眼不易分辨的范围内(平均RMS误差2.0以下),并且本文方法特别适用于对较短运动数据的压缩.     

中文文本压缩的LZW算法

结合中文文本中的汉字编码方式、大字符集以及重复字串不长三个不同于英文文本的结构特点对LZW算法从读取数据方式、基本码集和字典码值输出方式三方面进行了修改。改进后的算法对中文文本的压缩比平均比LZW19提高了19%且压缩和解压速度与后者相当,其对较长的中文文本的平均压缩比已接近或者超过了压缩软件WinRAR。     

Improved Dynamic Dictionary Matching

In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.     

一种基于信息熵的中文高频词抽取算法

为扩展分词词典,提高分词的准确率,本文提出了一种基于信息熵的中文高频词抽取算法,其结果可以用来识别未登录词并扩充现有词典。我们首先对文本进行预处理,将文本中的噪音字和非中文字符转化为分隔符,这样文本就可以被视为用分隔符分开的中文字符串的集合,然后统计这些中文字符串的所有子串的相关频次信息,最后根据这些频次信息计算每一个子串的信息熵来判断其是否为词。实验证明,该算法不仅简单易行,而且可以比较有效地从文本中抽取高频词,可接受率可达到91.68%。     

Unified Compression-Based Acceleration of Edit-Distance Computation

The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic programming solution for this problem computes the edit-distance between a pair of strings of total length O(N) in O(N ²) time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well under a particular compression scheme. The basic idea is to first compress the strings, and then to compute the edit distance between the compressed strings. As it turns out, practically all known o(N ²) edit-distance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single edit-distance algorithm that works for strings which are compressed under any compression scheme. A rephrasing of this question is to ask whether a single algorithm can exploit the compressibility properties of strings under any compression method, even if each string is compressed using a different compression. In this paper we set out to answer this question by using straight line programs. These provide a generic platform for representing many popular compression schemes including the LZ-family, Run-Length Encoding, Byte-Pair Encoding, and dictionary methods. For two strings of total length N having straight-line program representations of total size n, we present an algorithm running in O(nNlg(N/n)) time for computing the edit-distance of these two strings under any rational scoring function, and an O(n ^2/3 N ^4/3) time algorithm for arbitrary scoring functions. Our new result, while providing a speed up for compressible strings, does not surpass the quadratic time bound even in the worst case scenario.