词典编码dictionaryencoding技术.docx
《词典编码dictionaryencoding技术.docx》由会员分享，可在线阅读，更多相关《词典编码dictionaryencoding技术.docx（10页珍藏版）》请在冰点文库上搜索。
词典编码dictionaryencoding技术
词典编码（DictionaryEncoding）技术
词典编码（DictionaryEncoding）技术属于无损压缩技术。
词典编码的思想
词典编码（dictionaryencoding）的根据是数据本身包含有重复代码
这个特性。
例如文本文件和光栅图像就具有这种特性。
词典编码法的
种类很多，归纳起来大致有两类。
第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。
这种编码概念如图所示。
第一类词典法编码概念
这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。
这类编码中的所有算法都是以AbrahamLempel和
JakobZiv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。
第二类算法的想法是企图从输入的数据中创建一个“短语词典
（dictionaryofthephrases”，这种短语不一定是像“严谨勤奋求实创
新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语,它可以是任意字符的组合。
编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。
这个概念如图所示。
J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。
在他们的研究基础上，TerryA.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW（Lempel-ZivWalch）
压缩编码，首先在高速硬盘控制器上应用了这种算法。
LZ77算法
LZSS算法
LZ78算法
LZW算法
在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个
术语一前缀根（Root），它是由单个字符串组成的缀-符串（String）。
在编
码原理上，LZW与LZ78相比有如下差别：
①LZW只输出代表词典中的缀-符串（String）的码字（codeword）。
这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根
（Root）。
②由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀（one-characterprefix）,因此在词典中搜索的第1个缀-符串有两个字符。
现将LZW编码算法和译码算法介绍如下。
1.编码算法
LZW编码是围绕称为词典的转换表来完成的。
这张转换表用来存放称为前缀（Prefix）的字符序列，并且为每个表项分配一个码字（Codeword），或者叫做序号，如表下所示。
这张转换表实际上是把8
位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。
扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。
Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀
（Prefix）。
词典
码字（Codeword）
前缀（Prefix）
1
—
・・・
193
A
—
194
B
・・・
255
—
・・・
1305
abcdefxyF01234
—
…
LZW编码器（软件编码器或硬件编码器）就是通过管理这个词典
完成输入与输出之间的转换。
LZW编码器的输入是字符流（Charstream,字符流可以是用8位ASCII字符组成的字符串，而输出是用n位（例如12位）表示的码字流（Codestream，码字代表单个字符或多个字符组成的字符串。
LZW编码器使用了一种很实用的分析（parsing）算法，称为贪婪分
析算法（greedyparsingalgorithm）,在贪婪分析算法中，每一次分析都要串行地检查来自字符流（Charstream的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀（Prefix）。
用已知的前缀（Prefix）加上下一个输入字符C也就是当前字符（Currentcharacter作为该前缀的扩展字符，形成新的扩展字符串缀-符串
（String）:
Prefix.C。
这个新的缀-符串（String）是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。
如果有，那么这个缀-符串（String）就变成前缀（Prefix），继续输入新的字符，否则就把这个
缀-符串（String）写到词典中生成一个新的前缀（Prefix）,并给一个代码
LZW编码算法的具体执行步骤如下:
步骤1:
开始时的词典包含所有可能的根（Root），而当前前缀P
是空的;
步骤2:
当前字符（C）:
二字符流中的下一个字符；
步骤3:
判断缀-符串P+C是否在词典中
（1）如果“是”：
P:
=P+C//（用C扩展P）；
⑵如果“否”
1把代表当前前缀P的码字输出到码字流；
2把缀-符串P+C添加到词典；
3令P:
=C//（现在的P仅包含一个字符C）;
步骤4：
判断码字流中是否还有码字要译
（1）如果“是”，就返回到步骤2；
⑵如果“否”
1把代表当前前缀P的码字输出到码字流；
2结束。
LZW编码算法可用伪码表示。
开始时假设编码词典包含若干个
已经定义的单个码字。
例如，256个字符的码字，用伪码可以表示成:
Dictionary[j]Jallnsingle-character;j=1,2,…，n
jJn+1
PrefixJreadfirstCharacterinCharstream
while（（CJnextCharacter）!
二NULL）
Begin
IfPrefix.CisinDictionary
PrefixJPrefix.C
else
CodestreamJcWforPrefix
Dictionary[j]JPrefix.C
jJn+1
PrefixJC
end
CodestreamJcWforPrefix
2•译码算法
LZW译码算法中还用到另外两个术语：
①当前码字（Currentcodeword）:
指当前正在处理的码字，用cW表示，用string.cW表示当前
缀-符串；②先前码字（Previouscodeword）：
指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。
LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根（roots）。
LZW算法在译码过程中会记住先前码字（pW），从码字流中读当前码字（cW）之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典
中。
LZW译码算法的具体执行步骤如下：
步骤1：
在开始译码时词典包含所有可能的前缀根（Root）。
步骤2：
cW：
=码字流中的第一个码字。
步骤3：
输出当前缀-符串string.cW到码字流。
步骤4：
先前码字pW：
=当前码字cW。
步骤5：
当前码字cW：
=码字流中的下一个码字。
步骤6：
判断先前缀-符串string.pW是否在词典中
（1）如果“是”，则：
1把先前缀-符串string.pW输出到字符流。
2当前前缀P：
=先前缀-符串string.pW。
3当前字符C：
=当前前缀-符串string.cW的第一个字符
4把缀-符串P+C添加到词典。
（2）如果“否”，则：
①当前前缀P：
=先前缀-符串string.pW。
②当前字符C：
=当前缀-符串string.cW的第一个字符。
3输出缀-符串P+C到字符流，然后把它添加到词典中。
步骤7：
判断码字流中是否还有码字要译
（1）如果“是”，就返回到步骤4。
（2）如果“否”,结束。
LZW译码算法可用伪码表示如下：
Dictionary[j]Jallnsingle-characte,j=1,2,…，n
jJn+1
cWJfirstcodefromCodestream
CharstreamJDictionary[cW]
pWJcW
While（（cWJnextCodeword）!
二NULL）
Begin
IfcWisinDictionary
CharstreamJDictionary[cW]
PrefixJDictionary[pW]
cWJfirstCharacterofDictionary[cW]
Dictionary[j]JPrefix.cW
jJn+1
pWJcW
else
PrefixJDictionary[pW]
cWJfirstCharacterofPrefix
CharstreamJPrefix.cW
Dictionary[j]JPrefix.C
pWJcWjJn+1
［例4.7］编码字符串如表下所示，编码过程如表4-17所示。
现说明如下：
（1）“步骤”栏表示编码步骤；
（2）“位置”栏表示在输入数据中的当前位置；
（3）“词典”栏表示添加到词典中的缀-符串，它的索引在括号中；
（4）“输出”栏表示码字输出。
被编码的字符串
位置
1
2
3
4
5
6
7
8
9
字符
A
B
B
A
B
A
B
A
C
LZW的编码过程
步骤
位置
词典
输出
（1）
A
⑵
B
⑶
C
1
1
⑷
AB
（1）
2
2
（5）
BB
（2）
3
3
（6）
BA
（2）
4
4
⑺
ABA
（4）
5
6
（8）
ABAC
（7）
6
--
--
--
（3）
下表解释了译码过程。
每个译码步骤译码器读一个码字，输出相
应的缀-符串，并把它添加到词典中。
例如，在步骤4中，先前码字
（2）存储在先前码字（pW）中，当前码字（cW）是（4），当前缀-符串string.cW是输出（“AB”），先前缀-符串string.pW（"B"）是用当前缀-符串string.cW（"A"）的第一个字符，其结果（"BA"）添加到词典中，它的索引号是（6）
LZW的译码过程
步骤
代码
词典
输出
（1）
A
⑵
B
⑶
C
1
（1）
--
--
A
2
（2）
⑷
AB
B
3
（2）
（5）
BB
B
4
⑷
（6）
BA
AB
5
（7）
⑺
ABA
ABA
6
⑶
（8）
ABAC
C
LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。
对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。
在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的
LZW算法。
LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司一Unisys（优利系统公司），除了商业软件生产公司之外，可以免费使用LZW算法。
升级会员 