题库 信息学奥赛题库 题目列表 LZW 编码是一种自适应词典编码。在编码的过程中,开始...
填空题

LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码词典,

如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用于后继信息的编码。


举例说明,考虑一个待编码的信息串:

xyx yy yy xyx。初始词典只有 3 个条目,第一个为 x,编码为 1 ;第二个为 y,编码为 

2;第三个为空格,编码为 3;于是串 xyx 的编码为 1-2-1(其中 - 为编码分隔符),加上后面的一个空格就是 1-2-1-3。

但由于有了一个空格,我们就知道前面的 xyx 是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到词典里,

编码为 4,然后按照新的词典对后继信息进行编码,以此类推。于是,最后得到编码:

1-2-1-3-2-2-3-5-3-4。


现在已知初始词典的 3 个条目如上述,则信息串 yyxy xx yyxy xyx xx xyx 的编码是_________。

题目信息
2010年 初赛
-
正确率
0
评论
48
点击