|
- UID
- 1029342
- 性别
- 男
|
2 算法的选择无损压缩就是对信源信息进行压缩编码后在解压缩时能够完全恢复，也即在压缩和解压缩过程中对信源信息没有丝毫损失。常用的无损压缩方法有Shannon- Fano编码、Huffman编码、游程(Run-length)编码、LZW(Lempel-Ziv-Welch)编码和算术编码(ARC)等。对许多信息而言，没必要完全保留全部特征。在允许一定精度损失的情况下，可以获得更高的压缩编码效率。这类压缩编码方法成为有损压缩。本设计采用无损压缩，不再讨论有损压缩。
无损数据压缩算法可以分为统计方法和词典编码方法。统计方法当以Huffman编码和算术编码(ARC)为代表。这种方法需要统计信源符号的概率分布情况，并根据统计结果产生压缩码。算术编码是一种高效清除字串冗余的算法。仙侬信息论把字符aj出现的自信息量定义为I(aj)=-logpj I(aj)亦称自信息函数，其含义实际是随机变量X取值为aj时所携带信息的度量。自信息量的概率平均值，即随机变量I(aj) 的数学期望值，称做信息熵或简称熵。算术编码从全序列出发，采用递推形式连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入符号序列映射为实数轴上[0，1)区间内的一个小区间，其长度等于该序列的概率，再在该小区间内选择一个有代表性的二进制小数，而且是一个介于0和1之间的二进制小数作为实际的编码输出，从而达到了高效编码的目的。例如算术编码对某条信息的输出为1010001111，它表示小数0.1010001111，也即十进制数 0.64。不论是否为二元信源，也不论数据的概率分布如何，其平均码长均能逼近信源的熵。算术编码的过程实际上也就是信源编码试图将任意的信息流与0、1 之间的间隔建立一一对应关系的过程。这样要表示的信息流越长，则表示它的间隔就越小，用于表示这一间隔所需的二进制位就越多。
算术编码在编码前要求预先统计各信源符号概率，但无须排序，只要编、解码端使用相同的符号顺序即可。建立合理的信源概率模型是进行算术编码的关键。信源概率模型的建立方法一般有两种：一种是自适应的模型，是在不断输入信源的过程中对信源符号出现的概率进行统计，模型是在编码过程中逐步建立起来并不断更新；另一种是事先统计的模型，是在编码前就对所有输入信源符号的出现频率进行事先统计，而编码过程中模型不再改变。基于两种模型算法的不同之处：事先统计模型在编码之前就己经建立，编码过程中不再更新，故压缩效率与输入字节数关系不大；而自适应模型是在编码过程中建立并不断更新，当输入信源的数据量较大时，出现概率大的字符编码位数较少的优越性才能得以体现。在复杂度上，由于后者需要不断对模型进行更新，故运算量较大。
词典编码方法则是基于数据中许多结构频繁重复再现这一事实，人们可以对相同符号串分配同一码字、通过索引或者其他诸如此类的方法编码。LZW算法可以在对数据统计特性一无所知的前提下，使压缩率接近己知统计特性时所能够达到的压缩率，其运算速度快。LZW算法压缩的原理在于用字典中词条的编码代替被压缩数据中的字符串。字典中的词条越长越多，压缩率就越高。所以加大字典的容量可以提高压缩率。但从字典中查找词条是算法中最费时的工作，其字典的容量受到计算机内存限制，且字典也存在被填满的可能。当字典不能再加入新词条后，过老的字典就不能保证高的压缩率。
不同的压缩算法有不同的优点和缺点，不同算法的复杂性对空间的要求及压缩率也不同。压缩算法不仅仅依赖于压缩方法本身，也依赖于被压缩文本的特点。在本文中，由于是对实时数据的压缩，对压缩过程的时间性能要求高，所以采用事先统计模型的ARC。实验证明，采用事先统计模型的ARC，其运算速度与LZW算法速度相近。而ARC算法在压缩速度和压缩去除率上都优于LZW算法。
3 实验与结果
在比较字典编码LZW与算术编码ARC时，从压缩速度和压缩去除率上进行比较。前端以27Kb/s的速度实时采集8位的数据，数据压缩后通过发送模块以18Kb/s的速度数据传到外界。对原始数据以2 048B作为分组长度考察其压缩去除率及压缩时间。
压缩去除率＝(原始数据量－压缩后数据量)/原始数据量
这是从空间角度衡量。实际上，对压缩效率而言还必须关注其时间效率，本文采用“压缩速度”的概念，定义如下：
压缩速度＝原始数据量/压缩所需要的时间以2 048B的数据分组进行分析：
1)从压缩速度方面：完成2 048B的某噪声数据，ARC算法需要5.64ms来完成，而LZW算法需要6.6ms，可见ARC算法的压缩速度比较快。
(2)从压缩效率方面：将某数据按照2 048B的长度进行分组并压缩，从表1中可知ARC算法针对不同分组段的数据压缩去除率恒定在78%左右，而LZW算法，在该分组段压缩去除率仅为71%。可见该段数据ARC压缩算法压缩去除率比较高。
采用ARC算法后，通过大量的实验数据的平均压缩去除率为79%，满足系统所要求的数据压缩去除率大于50%的要求。用ARC算法压缩2 048B的数据需要5.64ms左右。数据不同，压缩时间会有所不同。通过对控制软件读取的数据进行解包、解压，证明还原出来的数据与原始数据完全一致，实现了实时数据的无损压缩。 |
|
