NOIP 提高 2010 第一轮 第 21 题：LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的

题目

LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。

举例说明，考虑一个待编码的信息串：$\texttt{xyx yy yy xyx}$。初始词典只有 $3$ 个条目，第一个为 $\texttt x$，编码为 $1$ ；第二个为 $\texttt y$，编码为 $2$；第三个为空格，编码为 $3$；于是串 $\texttt{xyx}$ 的编码为 $\texttt{1-2-1}$（其中 $\texttt -$ 为编码分隔符），加上后面的一个空格就是 $\texttt {1-2-1-3}$。但由于有了一个空格，我们就知道前面的 $\texttt{xyx}$ 是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为 $4$，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：$\texttt{1-2-1-3-2-2-3-5-3-4}$。

我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的 $3$ 个条目如上述，接收端收到的编码信息为 $\texttt{2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6}$，则解码后的信息串是“ ”。

答案

yyxy xxyyxyxyx xxxyx

题解

考点定位

本题考「LZW 解码模拟」,对应大纲 4.2.1 编码模拟（难度【4】）。

解题过程

已知编码串，按 LZW 逆向恢复原文。词典初始 x=1,y=2,␣=3。解码时每读一个码输出对应词条，并把「上一词条+当前词条首字符」入典：

按编码逐码恢复（模拟过程），得到原文：

yyxy xxyyxyxyx xxxyx

易错提醒

① 解码的特殊性：新词条「词+下一词首字符」需要在读到下一个码后补全——紧邻码之间的关系要理清；② 与普及组同题的编码方向对照练习，正逆都熟练。