DEEFALT中的LZ77应该算其一个简单的变种,LZ77算法比较简单,因此其编码原理这里也不多重复了,应该都能很快写出来
简略概括就是后面的数据可能是前面数据的重复,因此,要还原后面的数据:
1.存储其在前面那个位置开始
2.存储其重复的长度
就可以还原出之后的数据了,举个栗子,例如下面的序列:
[1,2,3,a,b,c,a,b,c,a,b]
我们从左往右边扫描,直到这个位置:
[1,2,3,a,b,c | a,b,c,a,b ]
我们发现,分割符|右边的a,b,c和左边的重复了,因此上面序列可以等价为
[1,2,3,a,b,c | (重复长度为3,位置在前3个字母),a,b ]
其中,"重复长度"顾名思义
而"位置在前3个字母"是描述位置的信息,综合上述,我们其实可以更进一步,如果我们定义(重复长度是5,位置在前3个字母)如何
显然的,因为a,b,c,a,b后面的两个独立的a,b仍然在a,b,c,a,b,c,a....的循环嵌套内,因此长度比距离大,这种描述仍然能够正确工作,因此,我们可以把上面的序列编码为下面的表达方式
[1,2,3,a,b,c,(5,3)];
是不是很方便.