lz78算法
lz78算法
LZ77 算法针对过去的数据进行处理，而 LZ78 算法却是针对后来的数据进行处理。LZ78 通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据，并且将结果数据添加到字典中。
尽管在最初得到流行，但是后来 LZ78 的普及逐渐衰减，这可能是由于在刚 LZ78 出现的一些年份，一部分 LZ78 算法获得了美国专利保护。最流行的 LZ78 压缩形式是 LZW 算法，这个算法是 Terry Welch 所开发的一个 LZ78 变体。
在算法中用到的几个术语和符号：
(1) 字符流(Charstream)：要被编码的数据序列。
(2) 字符(Character)：字符流中的基本数据单元。
(3) 前缀(Prefix)： 在一个字符之前的字符序列。
(4) 缀-符串(String)：前缀＋字符。
(5) 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。
(6) 码字流(Codestream)： 码字和字符组成的序列，是编码器的输出。
(7) 词典(Dictionary)： 缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。
(8) 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。
(9) 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。
(10) 当前码字(Current code word)： 在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。
1. 编码算法
LZ78的编码思想是不断地从字符流中提取新的缀-符串(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)，然后添加到词典中。LZ78编码的具体算法如下：
步骤1： 在开始时，词典和当前前缀P都是空的。
步骤2： 当前字符C ：=字符流中的下一个字符。
步骤3： 判断P+C是否在词典中：
(1) 如果“是”：用C扩展P，让P ：= P+C ；
(2) 如果“否”：
① 输出与当前前缀P相对应的码字和当前字符C；
② 把字符串P+C 添加到词典中。
③ 令P ：=空值。
(3) 判断字符流中是否还有字符需要编码
① 如果“是”：返回到步骤2。
② 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。
2. 译码算法
在译码开始时译码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到词典中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码的具体算法如下：
步骤1： 在开始时词典是空的。
步骤2： 当前码字W ：=码字流中的下一个码字。
步骤3： 当前字符C ：= 紧随码字之后的字符。
步骤4： 把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C。
步骤5： 把string.W+C添加到词典中。
步骤6： 判断码字流中是否还有码字要译
(1) 如果“是”，就返回到步骤2。
(2) 如果“否”，则结束。
[例4.6] 编码字符串如表4-13所示，编码过程如表4-14所示。现说明如下：
(1) “步骤”栏表示编码步骤。
(2) “位置”栏表示在输入数据中的当前位置。
(3) “词典”栏表示添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号。
(4) “输出”栏以(当前码字W, 当前字符C)简化为(W, C)的形式输出。
表：编码字符串
位置 1 2 3 4 5 6 7 8 9
字符 A B B C B C A B A
表：编码过程
步骤 位置 词典 输出
1 1 A (0,A)
2 2 B (0,B)
3 3 BC (2,C)
4 5 BCA (3,A)
5 8 BA (2,A)
与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。