|
|
|
|
知识路径： > 多媒体数据压缩编码技术基础 > 统计编码 > 字典编码 > 字典编码 >
|
|
|
被考次数：1次
|
|
|
被考频率：
低频率
|
|
|
总体答错率：
47%
|
|
知识难度系数：
|
|
|
考试要求：
熟悉
|
|
|
相关知识点：2个
|
|
|
|
|
隐式字典的典型压缩算法有LZ77和LZSS。显式字典的典型压缩算法有LZ78和LZW。下面介绍LZ77算法和LZSS算法。
|
|
|
|
|
|
为了更好地说明LZ77算法的原理，首先介绍该算法中的几个术语。
|
|
|
|
|
|
|
|
. 编码位置：输入流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。
|
|
|
|
. 前向缓存：存放从编码位置到输入流结束的字符序列。
|
|
|
|
. 窗口：包含W个字符的窗口，字符是从编码位置开始往后数的，也就是最后处理的字符数。
|
|
|
|
|
|
LZ77算法的核心是查找从前向缓冲存储器开始的最长的匹配串。该算法的具体执行步骤如下。
|
|
|
|
|
|
|
|
步骤3：以（Pointer, Length）Characters的格式输出。其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓存中不匹配的第1个字符。
|
|
|
|
步骤4:如果前向缓冲存储器不是空的，则把编码位置和窗口向前移（Length+1）个字符，然后返回步骤2。
|
|
|
|
|
|
LZSS算法通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这种解决方案包含冗余信息，冗余信息表现在两个方面：一是编码器的输出可能包含空指针；二是编码器可能输出额外字符，即可能包含下一个匹配串中的字符。LZSS算法以比较有效的方法解决了这个问题，它的思想是如果匹配串的长度比指针本身的长度长，就输出指针，否则就输出真实字符。由于输出数据流中包含指针和字符本身，因此为了区分它们就需要有额外的标志位，即ID位。
|
|
|
|
|
|
|
|
步骤2:在前向缓冲存储器中查找窗口中最长的匹配串。
|
|
|
|
|
|
|
|
步骤3:判断匹配串长度Length是否大于或等于最小匹配串长度（Length≥MIN_ LENGTH）。
|
|
|
|
是：输出指针，然后把编码位置向前移动Length个字符。
|
|
|
|
否：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动1个字符。
|
|
|
|
步骤4：如果前向缓冲存储器不是空的，则返回步骤2。
|
|
|
|
在相同的计算环境下，LZSS算法比LZ77可获得更高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想，如PKZip、ARJ、LHArc和ZOO等，其差别仅仅是指针的长短和窗口的大小有所不同。
|
|
|
|
LZSS同样可以和熵编码联合使用，如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。
|
|
|
