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

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

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

填写答案