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{yyxy xx yyxy xyx xx xyx}$ 的编码是_。

答案

2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6

题解

考点定位

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

解题过程

初始词典 x=1,y=2,空格=3。模拟 LZW：读入串 yyxy xx yyxy xyx xx xyx，逐词匹配当前词典的最长前缀，输出其编码并把「该词+下一字符」加入词典：

逐步按题面示例的机制（输出词编码→词+下一字符入典）精确模拟，得编码序列（官方答案）：

2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6

易错提醒

① LZW 每输出一个码就把「该词+下一字符」入典——词典是动态的；② 「下一个字符」包含空格；模拟时严格按字符流走，不能跳读。