冯娟的第四次作业

参考书习题：

7、使用LZ77算法对一个序列进行编码。给定C(a)=1,C(b)=2,C(r)=3,C(t)=5,对一下三元组序列进行解码：

     <0,0,3><0,0,1><0,0,4><2,8,2><3,1,2><0,0,3><6,4,4><9,5,4>

     假定窗口的大小为20，先行缓冲区的大小为10.对解码所得到的序列进行编码，确保得到相同的三元组序列。

     解：

           

序列	输出
<0,0,3>	r
<0,0,1>	ra
<0,0,4>	rat
<2,8,2>	ratatatatatb
<3,1,2>	ratatatatatbab
<0,0,3>	ratatatatatbabr
<6,4,4,>	ratatatatatbabratbat
<9,5,4>	ratatatatatbabratbatbabrat

    

编码过程：

    输入序列：rat atatatatbabratbatbabrat

输入	输出
r  _atatatatatbabratbatbabrat	<0,0,3>
ra_ tatatatatbabratbatbabrat	<0,0,1>
rat _ atatatatbabratbatbabrat	<0,0,4>
r _atatatatatb_ abratbatbabrat	<2,8,2>
rat_ atatatatba _ bratbatbabrat	<3,1,2>
rata _ tatatatbab _ ratbatbabrat	<0,0,3>
ratatatatatbabratbatbabrat	<6,4,4,>
ratatatatatbabratbatbabrat	<9,5,4>

8、给定以下初始词典和接受序列，构建一个LZW词典，并对多发送的序列进行解码。接受序列：4，5，3，1，2，8，2，7，9，7，4

初始词典：

索引	项
1	S
2	P
3	I
4	T
5	H

解：

    1）输入4,5,3,1,2,8,2,7,9,7,4

索引	条目
1	S
2	_
3	I
4	T
5	H

     

                     

 

 

 

     解码的序列为：T

   2）输入4,5,3,1,2,8,2,7,9,7,4

索引	条目
1	S
2	-
3	I
4	T
5	H

 

                     

 

 

    解码的序列为：TH

    3）输入4,5,3,1,2,8,2,7,9,7,4

索引	条目
1	S
2	_
3	I
4	T
5	H
6	TH

 

                     

 

 

 

    解码的序列为：THI

    10）输入4,5,3,1,2,8,2,7,9,7,4

索引	条目
1	S
2	_
3	I
4	T
5	H
6	TH
7	HI
8	IS
9	S_
10	_I
11	IS_
12	_H
13	HIS

 

                                 

 

 

 

 

 

 

 

 

    解码的序列为：THIS IS HIS HI 

    11）输入4,5,3,1,2,8,2,7,9,7,4

索引	条目
1	S
2	_
3	I
4	T
5	H
6	TH
7	HI
8	IS
9	S_
10	_I
11	IS_
12	_H
13	HIS
14	S_H

 

                                  

 

 

 

 

 

 

 

 

 

    解码的序列为：THIS IS HIS HIT    

    最后解码序列为：THIS IS HIS HIT