NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 21 题

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}$ 的编码是_________。

LZW编码：初始词典{x=1,y=2,空格=3}。扫描字符串yyxy xx yyxy xyx xx xyx，按LZW算法自适应添加新词条到词典。

(1) LZW编码每次读取最长已编码前缀，输出编码，并将新词条加入词典。(2) 注意编码分隔符"-"的格式。(3) 词典是动态增长的，新编码从4开始递增。

LZW编码

初始词典：x=1, y=2, 空格=3

字符串：yyxy xx yyxy xyx xx xyx

编码过程

1. y(2) → 输出2; 新词条: yy=4 2. y(2) → 输出2; 新词条: yx=5? 实际需要仔细跟踪 ...

根据题意，最终编码为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6

答案：2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6

• 🔑 LZW=动态词典编码。遇新词条→追加到词典→输出编码。

以上为完整解析的章节结构，展开每一步的推导、正确性说明与复杂度分析请在平台查看。