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{2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6}$，则解码后的信息串是“ ____”。

这题考 LZW 解码。拿到一串编码，核心心法是‘边读边还’：每读出一个码，先把它对应的字符串拼出来输出，再把这个码对应的字符串与下一个码对应的字符串拼一起，作为新词条追加到词典里，供后面用。

最容易栽跟头的地方是以为 LZW 解码和编码一样要‘先查词典再输出’，结果遇到新词条时词典还没更新，直接报错或乱输出；还有把空格当成普通字符处理，忘了初始词典里空格是 3，导致中间断句错位；另外在遇到 4、5、6 这种新码时，容易只输出一次就把下一个码丢了，忘记把‘当前码+下一码’拼成新词条加进词典，这样后面解码全乱套。

LZW 解码

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

接收编码：2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6

逐步解码： 2→y, 2→y, 1→x, 2→y → "yyxy" 3→空格 → "yyxy " 1→x, 1→x → "xx" 3→空格 → "xx " 4→(新词条xy) → "yyxy " 3→空格 1→x, 2→y, 1→x → "xyx" 3→空格 5→(新词条xx) → "xx " 3→空格 6→(新词条xyx) → "xyx"

结果：yyxy xx yyxy xyx xx xyx

命题视角

命题人爱考 LZW 解码的‘动态扩充’细节：它不像普通解码那样只查表，而是每输出一个码，就要把‘当前码+下一码’拼成新词条放进词典。这步很多人会漏，导致后面遇到 4、5、6 时词典里没有对应项，直接卡死或输出错误。空格作为初始词典里的第三个条目，常被忽略，结果把一串字符拆成错误的片段。

考频与趋势

字符串哈希相关题目在题库中共出现过 2 次，覆盖 2010 和 2024 两届，NOIP 提高组初赛曾考过 1 题。LZW 虽然不直接属于哈希，但同属‘自适应词典压缩’范畴，命题人喜欢在基础数据结构题里穿插这类编码解码的小陷阱。

预测

暂无足够依据预测未来具体怎么考，但可以合理推测：如果继续考压缩/编码类题目，很可能会换一种编码方式（如霍夫曼、算术编码）或者在 LZW 基础上增加一层‘词典冲突’或‘编码溢出’的变式，考察对动态更新机制的深入理解。