与用于序列数据压缩的Ziv-Lempel和Welch型算法相关的几种改进型方法

摘要

本文介绍与现用的几种重要信源编码算法相关的几种数据压缩算法，包括Ziv-Lempel码,Rissanen的上下文法以及Welch的LZW法等。首先，提出了一种介于Ziv-Lempel这两种通用数据压缩方法之间的中间算法，该算法与以递增语法分析为基础的著名方法一样，具有相同的渐近最优性。然后将所提出的算法，在收集方向和收集频率方面与上下文收集算法“上下文法”进行比较。结果表明：当所提出的算法与“上下文法”具有相同的收集频率时，它们的上下文收集方向相反。同时还考虑了几种实用的变型。将所提出的算法与Welch的方案结合在一起时，可以获得两种实用的数据压缩方法。这两种方法与Welch的LZW方法一样，开始时使用一个小的符号串表，在压缩和解压期时再建立码表。在我们的这些实用方法中，通过码表的加速增长而可获得较高的压缩效率。