常用数据无损压缩算法分析

因为字典的前256项被占用，因此字典指针必须高于8位。由于LZW算法的字典中的字符串每次仅增加一个字符。因此，要获得长字符串则需较长时间，这样才能较好地压缩．IZW编码能够适应输入数据。

LZW算法与其他算法相比具有自适应的特点，即可以根据压缩内容不同来建立不同字典，以减少冗余度，提高压缩比；并且解压时这个字典无需与压缩代码同时传送，而是在解压过程中逐步建立与压缩时完全相同的字典，从而完整、准确地恢复被压缩内容。因此，LZW算法是一种解码速度与压缩性能较好的压缩算法。

实现LZW算法需要考虑以下几点：

(1)字典建立(数据结构与字典大小) LZW字典的数据结构是一棵多叉树。字典越大，代替的子串越多。但应用中字典容量则受一定限制，要权衡利弊选择合适的字典。

(2)字典维护与更新 字典指针由哈希函数生成。正确选择哈希函数非常重要，这将影响执行效率。正确的哈希函数所产生的重复值极少，这样检索字符串所需比较次数也较少，从而可有效提高代码的执行效率。

当字典满时，字典的维护和更新对压缩率也是至关重要的。可重新从初始状态建立字典；也可监测压缩率，当压缩率变坏时全部或部分清除字典。

(3)压缩数据代码长度 压缩时，输入数据一般是8位。但压缩后的输出是转化的字符串代码，其中0～255为8位码，256为9位码，25l～512为10位码，l 024为11位码。解压则相反，需要位操作。因此，输出可以从9位码开始，随着字典内容的增加，码字也逐渐增加。这样可提高执行效率，但在译码时需考虑不等长码的识别，可通过设置标志位来解决。

3．3 基于哈夫曼编码原理的压缩算法

哈夫曼算法的过程为：统计原始数据中各字符出现的频率；所有字符按频率降序排列；建立哈夫曼树：将哈夫曼树存入结果数据；重新编码原始数据到结果数据。哈夫曼算法实现流程如图3所示。

哈夫曼算法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码。实用中．符号的出现频率不能预知，需要统计和编码两次处理，所以速度较慢，无法实用。而自适应(或动态)哈夫曼算法取消了统计，可在压缩数据时动态调整哈夫曼树，这样可提高速度。因此，哈夫曼编码效率高，运算速度快，实现方式灵活。

采用哈夫曼编码时需注意的问题：

(1)哈夫曼码无错误保护功能，译码时，码串若无错就能正确译码；若码串有错应考虑增加编码，提高可靠性。

(2)哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。

(3)哈夫曼树的实现和更新方法对设计非常关键。

3．4 基于算术编码的压缩算法

算术编码压缩也是一种根据字符出现概率重新编码的压缩方案。该思想和哈夫曼编码有些相似，但哈夫曼编码的每个字符需用整数个位表示。而算术编码方法则无这一限制，它是将输入流视为整体进行编码。虽然算术编码压缩率高．但运算复杂，速度慢。

4 结语

游程编码和LZW编码属于基于字典模型的压缩算法，而哈夫曼编码和算术编码属于基于统计模型的压缩算法，前者与原始数据的排列次序有关而与其出现频率无关，后者则正好相反。这两类压缩方法算法思想各有所长，相互补充。许多压缩软件结合了这两类算法。例如WINRAR就采用了字典编码和哈夫曼编码算法。这几种数据无损压缩算法应用广泛，设计人员可以根据具体应用中的数据流特点来改进算法从而开发适用的软硬件压缩器。

作者：李雷定 马铁华 尤文斌 来源：国外电子元器件