最近由于课程设计需要做解压缩算法
特此来考察字典编码
许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。因此,人们提出了许许多多的数据压缩方法,企图用来对这些数据进行压缩编码,在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。 字典编码(dictionary encoding)技术(以下简称DE)就是属于这一类,这种技术属于无损压缩技术。
数据本身包含有重复代码
这个特性
例如文本文件和光栅图像就具有这种特性种类很多,归纳起来大致有两类
用已经出现过的字符串替代重复部分,输出仅仅是指向之前出现过的字符串的“指针”
abraham lempel
和jakob ziv
在1977年研究发表的称为lz77
算法为基础这种短语不一定是像“好好学习天天向上”和“你个糟老头子坏得很我信你个鬼”这类具有具体含义的短语,它可以是任意字符的组合
编码数据过程中当遇到已经在字典中出现的“短语”时,编码器就输出这个字典中的短语的“索引号”,而不是短语本身。
j.ziv
和a.lempel
在1978年首次发表了这种编码方法的文章
在他们的研究基础上,terry a.weltch
在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为LZW(lempel-ziv walch)
压缩编码,首先在高速硬盘控制器上应用了这种算法
核心是查找从前向缓冲存储器开始的最长的匹配串
1.把编码位置设置到输入数据流的起始位
2.查找窗口中最长的匹配串
3.以“(Pointer, Length) Characters”的格式输出
其中Pointer是指向窗口中匹配串的指针,Length表示匹配字符的长度,Characters是前向缓冲存储器中的不匹配的第1个字符。
4.如果前向缓冲存储器不是空的,则把编码位置和窗口向前移(Length+1)
个字符,然后返回到步骤2
Back_chars
个字符然后拷贝Chars_length
个字符到输出编码过程
的输出(5,2) C
告诉译码器回退5个字符,然后拷贝2个字符“AB”但wikipedia认为,粗体字理解成
从编码位置开始往回数Back_chars个字符,从该字符开始数起的字符串与接下来的Chars_length个字符完全相同
不断从字符流中提取新的缀-符串(String),通俗地理解为新“词条”,然后用“代号”也就是码字(Code word)表示这个“词条” 这样一来,对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream),生成码字流(Codestream),从而达到压缩数据的目的
在编码开始时字典是空的,不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C,并把这个字符C添加到字典中作为一个由一个字符组成的缀-符串(string)。在编码过程中,如果出现类似的情况,也照此办理。在字典中已经包含某些缀-符串(String)之后,如果“当前前缀P +当前字符C”已经在字典中,就用字符C来扩展这个前缀,这样的扩展操作一直重复到获得一个在字典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C,并把P+C添加到字典中作为前缀(Prefix),然后开始处理字符流(Charstream)中的下一个前缀。
LZ78编码器的输出是码字-字符(W,C)对,每次输出一对到码字流中,与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String),然后添加到字典中
在开始时,字典和当前前缀P都是空的
当前字符C:=字符流中的下一个字符
P+C 是否在字典中 (1) “是” 用C扩展P,让P := P+C (2) “否” ① 输出与当前前缀P相对应的码字和当前字符C ② 把字符串P+C 添加到字典中 ③ 令P:=空值 (3) 字符流中是否还有字符需要编码 ① “是” 返回到步骤2 ② “否” 若当前前缀P非空,输出相应于当前前缀P的码字,然后结束编码
在译码开始时译码字典为空,它将在译码过程中从码字流中形成 每当从码字流中读入一对码字-字符(W,C)对时,码字就参考已经在字典中的缀-符串,然后把当前码字的缀-符串string W 和字符C输出到字符流(Charstream),而把当前缀-符串(string.W+C)添加到字典中。在译码结束之后,重构的字典与编码时生成的字典完全相同
开始时字典空
当前码字W :=码字流中的下一个码字
当前字符C := 紧随码字之后的字符。
把当前码字的缀-符串(string.W)输出到字符流(Charstream),然后输出字符C
把string.W+C添加到字典中
判断码字流中是否还有码字要译 (1) “是” 返回到步骤2 (2) “否” 结束
●“步骤” 编码步骤 ●“位置” 在输入数据中的当前位置 ●“字典” 添加到字典中的缀-符串,缀-符串的索引等于“步骤”序号 ●“输出” 以(当前码字W, 当前字符C)简化为(W, C)的形式输出
与LZ77相比,LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目,而压缩率与LZ77类似
使用的术语与LZ78的类似,仅增加了一个术语—前缀根(Root),它是由单个字符串组成的缀-符串(String)
LZW编码是围绕称为字典的转换表
来完成的
这张转换表用来存放称为前缀(Prefix)的字符序列,并且为每个表项分配一个码字(Code word),或者叫做序号
这张转换表实际上是把8位ASCII字符集进行扩充,增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串 扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示 Welch的论文中用了12位,12位可以有4096个不同的12位代码,这就是说,转换表有4096个表项,其中256个表项用来存放已定义的字符,剩下3840个表项用来存放前缀(Prefix)
LZW编码器就是通过管理这个字典完成输入/输出的转换
LZW编码器使用了一种很实用的分析(parsing)算法,称为贪婪分析算法(greedy parsing algorithm) 在贪婪分析算法中,每一次分析都要串行地检查来自字符流(Charstream)的字符串,从中分解出已经识别的最长的字符串,也就是已经在字典中出现的最长的前缀(Prefix) 用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符,形成新的扩展字符串——缀-符串(String):Prefix.C 这个新的缀-符串(String)是否要加到字典中,还要看字典中是否存有和它相同的缀-符串String
开始时的字典包含所有可能的根(Root),而当前前缀P是空的
当前字符© :=字符流中的下一个字符
判断缀-符串P+C是否在字典中 (1) “是” :P := P+C (2) “否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到字典; ③ 令P := C
码字流中是否还有码字要译 (1) “是” 回到步骤2 (2) “否” ① 把代表当前前缀P的码字输出到码字流 ② 结束
LZW编码算法可用伪码表示 开始时假设编码字典包含若干个已经定义的单个码字
算法开始时,译码字典与编码字典相同,包含所有可能的前缀根(roots) 在译码过程中会记住先前码字(pW),从码字流中读当前码字(cW)之后输出当前缀-符串string.cW,然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到字典中。
步骤1:在开始译码时字典包含所有可能的前缀根(Root)。 步骤2:cW :=码字流中的第一个码字。 步骤3:输出当前缀-符串string.cW到码字流。 步骤4: 先前码字pW := 当前码字cW。 步骤5: 当前码字cW := 码字流中的下一个码字。 步骤6: 判断先前缀-符串string.pW是否在字典中 (1) 如果“是”,则: ① 把先前缀-符串string.pW输出到字符流。 ② 当前前缀P :=先前缀-符串string.pW。 ③ 当前字符C :=当前前缀-符串string.cW的第一个字符。 ④ 把缀-符串P+C添加到字典。 (2) 如果“否”,则: ① 当前前缀P :=先前缀-符串string.pW。 ② 当前字符C :=当前缀-符串string.cW的第一个字符。 ③ 输出缀-符串P+C到字符流,然后把它添加到字典中。 步骤7: 判断码字流中是否还有码字要译 (1) 如果“是”,就返回到步骤4。 (2) 如果“否”, 结束。
每个译码步骤译码器读一个码字,输出相应的缀-符串,并把它添加到字典中 例如,在步骤4中,先前码字(2)存储在先前码字(pW)中,当前码字(cW)是(4),当前缀-符串string.cW是输出(“A B”),先前缀-符串string.pW (“B”)是用当前缀-符串string.cW (“A”)的第一个字符,其结果(“B A”) 添加到字典中,它的索引号是(6)
LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作 对LZW算法进一步的改进是增加可变的码字长度,以及在字典中删除老的缀-符串 在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法