对LWZ的研究——一个基于字典压缩的算法

2022-10-28

字典压缩算法是利用许多数据类型都含有重复的代码序列这一特性。在文本文件中其代码字代表字符，而在光栅图像中代码字代表象素。在编码时将有霞复的内容一次性地记录在一个数据串表中，这个表就仿佛是字典，当译码是利用指针号或索引号就可以找到原输入数据流中相应的内容，LZ的几种算法都属于基于字典的压缩算法。

基于字典压缩算法的分类

1、LZ77、LZSS算法

LZ77、LZSS算法的思想是：在数据压缩过程中。寻找当前等待进行压缩处理的数据串中是否在已经处理过的数据串中出现过，如果确实曾经出现过，则利用指向该已经进行处理数据串的指针代替当前等待进行压缩的数据串。

2、LZ78、LZW算法

（1）编码算法

LZw编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀的字符序列，并且为每个表项分配一个码字。LZW编码器使用了一种很实用的分析算法，称为贪婪分析算法。在贪婪分析算法中，每一次分析都要串行地检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀。用已知的前缀加上下一个输入字符ｃ也就是当前字符作为该前缀的扩展字符，形成新的扩展字符串缀一符串：Prefix.c.这个新的缀一符串是否要加到词典中，还要看词典中是否存有和它相同的缀一符串String。如果有，那么这个缀一符串就变成前缀（Prefix），继续输入新的字符，否则就把这个缀一符串写到词典中生成一个新的前缀（Prefix），并给一个代码。

（2）译码算法

LZW译码算法中还用到另外两个术语：①当前码字：指当前正在处理的码字，用cw表示，用String.cw表示当前缀一符串；②先前码字：指先于当前码字的码字，用ｐｗ表示。用String.pw表示先前缀一符串。LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根（rotts）。Ｌｚｗ算法在译码过程中会记住先前码字（ｐｗ）。从码字流中读当前码字String.cw之后输出当前缀一符串，然后把用String.cw的第一个字符扩展的先前缀一符串String.cw添加到词典中。

改进的U州算法

1、实现零搜索

如何才能使根据字头码和字尾码建立的索引值不重复，其办法是以其本身的值合成内存地址，依靠指针进行定位，从而不再需要查找过程。在32位操作系统下，其寻址能力可达4GB，再加上硬件设施大大提高，物理内存空间一般达到了128G，技术上虚拟内存町达4GB，使得上述方法成为可能。

2、动态编码

使用动态编码长度进一步提高了算法效率。这种方法允许压缩代码长度的更改，即利用不固定长度的代码存储压缩数据。LZW算法一般从9位开始编码，这时存储代码也是9位，直到编码增加到10位时，存储代码才增加到10位。传统的Lzw算法是直接存储最人编码位的，这样做导致非编码数据也要存储这样大的位数，浪费了完全没有用处的几个高位。

编码流程圈

对LWZ的研究——一个基于字典压缩的算法