第四次作业

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

<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，4>	rat
<2，8，2>	ratatatatatb	<3，1，2>	ratatatatatbab
<0，0，3>	ratatatatatbabr	<6，4，4>	ratatatatatbabratbat
<9，5，4>	ratatatatatbabratbatbabrat	<0，0，1>	ra

因为窗口的大小为20，先行缓冲区的大小为10。

所以得到序列：rataaaaaaaaaraaaatt

8. 给定以下初始词典和接收序列，构建一个LZW词典，并对所发送的序列进行解码。

接收序列：4，5，3，1，2，8，2，7，9，7，4

　　初始词典：

解：

对序列4,5,3,1,2,8,7,9,7,4进行解码得到：

THIS IS HIS HIT。