|
|
知识路径： > 多媒体数据压缩编码技术基础 > 统计编码 > 字典编码 >
|
被考次数：2次
被考频率：低频率
总体答错率：42%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：熟悉
相关知识点：6个
|
|
|
|
|
字典编码的基本思想是用符号代替一串字符，这一串字符可以是有意义的，也可以是无意义的。
|
|
|
|
图像数据实际上是由字符串组成的，在对一幅图像数据进行编码之前，首先要设置一个编码码表，这个码表可以是由已知的256个字符组成的码表，表的每一栏可看成是由单个字符组成的字符串，并且给每一栏都编一个号码。
|
|
|
|
在编码图像数据过程中，每读一个字符，就与以前读入的字符串拼接起来成为一个新的字符串，并且查看码表中是否已经有相同的字符串，如果有，就用码表中的字符串的号码代替这个字符；如果没有，就把这个新的字符放到码表中，并且给它编上一个新的号码。在数据存储或传输时，只存储或传输号码，而不存储或传输码表本身。在解码时，按照编码时的规则一边生成码表一边还原图像数据。
|
|
|
|
|
|
|
|
|
|
查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。
|
|
|
|
|
|
在输入的数据中创建一个“短语字典”，编码数据过程中，当遇到已经在字典中出现过的“短语”时，编码器就输出这个字典中的短语的“索引号”。
|
|
|
|
|
|
隐式字典的典型压缩算法有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联用，它的后续版本也采用霍夫曼编码。
|
|
|
