第四次作业

参考书《数据压缩导论（第4版）》 Page 121

答：由题意知W=20，S=10

解码：<0,0,3>

增加一个r，得：|r

解码：<0,0,1>

增加一个a，得：r|a

解码：<0,0,4>

增加一个t，得：ra|t

解码：<2,8,2>

从第二个字母a开始拷贝两个字母，得：rat|at

再拷贝两个字母，得：rat|atat

再拷贝两个字母，得：rat|atatat

再解码2，此时序列为：rat|atatatb //b表示空格，对应2

解码：<3,1,2>

从第八个字母a开始拷贝一个字母，得：|ratatatatb|a

再解码2，增加一个b，此时序列为： ratatatatb|ab //b表示空格，对应2

解码结束，得到序列 ratatatatbabratbatbabrat //b表示空格，对应2

对所得序列ratatatatbabratbatbabrat进行编码过程如下：

W=20，S=10

|ratatatatbabratbatbabrat

对于r，没有匹配的字符串

发送<0,0,3>

r|atatatatbabratbatbabrat

对于a，没有匹配的字符串

发送<0,0,1>

ra|tatatatbabratbatbabrat

对于t，没有匹配的字符串

发送<0,0,4>

rat|atatatbabratbatbabrat

发送<2,8,2>

ratatatatb|abratbatbabrat

发送<3,1,2>

ra|tatatatbab|ratbatbabrat

对于r，没有匹配的字符串

发送<0,0,3>

rat|atatatbabr|atbatbabrat

发送<6,4,4>

ratatata|tbabratbat|babrat

发送<9,5,4>

编码完成

答：由初始词典和接收序列知（注：B表示空格，对应第2项）：

索引值4对应字母T，所以序列第1个元素为T

索引值5对应字母H，所以序列第2个元素为H

将T、H串接在一起，组成模式TH，由于模式TH不在词典中，故将TH添加到词典中作为第6项

索引值3对应字母I，所以序列第3个元素为S

将H、I串接在一起，组成模式HI，由于模式HI不在词典中，故将HI添加到词典中作为第7项

索引值1对应字母S，所以序列第4个元素为I

将I、S串接在一起，组成模式IS，由于模式IS不在词典中，故将IS添加到词典中作为第8项

索引值2对应字母B，所以序列第5个元素为B

将S、B串接在一起，组成模式SB，由于模式SB不在词典中，故将SB添加到词典中作为第9项

索引值8对应字母IS，所以序列第6、7个元素为I、S

将B、I串接在一起，组成模式BI，由于模式BI不在词典中，故将BI添加到词典中作为第10项

索引值2对应字母B，所以序列第8个元素为B

将IS、B串接在一起，组成模式ISB，由于模式ISB不在词典中，故将ISB添加到词典中作为第11项

索引值7对应字母HI，所以序列第9、10个元素为H、I

将B、H串接在一起，组成模式BH，由于模式BH不在词典中，故将BH添加到词典中作为第12项

索引值9对应字母SB，所以序列第11、12个元素为S、B

将HI、S串接在一起，组成模式HIS，由于模式HIS不在词典中，故将HIS添加到词典中作为第13项

索引值7对应字母HI，所以序列第13、14个元素为H、I

将SB、H串接在一起，组成模式SBH，由于模式SBH不在词典中，故将SBH添加到词典中作为第14项

索引值4对应字母T，所以序列第15个元素为T

将HI、T串接在一起，组成模式HIT，由于模式HIT不在词典中，故将HIT添加到词典中作为第15项

综上得到完整词典如下：

索引	项	输出
1	S
2	B
3	I
4	T
5	H
6	TH	4
7	HI	5
8	IS	3
9	SB	1
10	BI	2
11	ISB	8
12	BH	2
13	HIS	7
14	SBH	9
15	HIT	7
16		4

由词典对发送序列45312827974

解码得到原始序列为：THISBISBHISBHIT