我们来做一个简单的输入:
A B C A B A B C A B
0 1 2 3 4 5 6 7 8 9
据我理解,算法是这样工作的:
0,0,A - distance 0, length 0, value A
0,0,B - distance 0, length 0, value B
0,0,C - distance 0, length 0, value C
2,2,A - distance 2(from position of 4th A, we're going back 3 steps but we count from 0, so 3-1=2,
length 2 (because its AB), value A
4,3,B - distance 4(5 steps, but we count from 0 so 5-1=4), length 3( we take BCA because we're almost
at the end of the file so we need the last character to stop)
Decoding:
0,0,A => A
0,0,B => AB
0,0,C => ABC
2,2,A => ABCABA ( from C we count backwards so 0, 1, 2 => we end up on A and the length is 2 => we got AB and we finish with A
4,3,B => ABCABABCAB
现在我在代码(C#):
for (int i = 0; i <BytesRead.Length; i++)
{
if(i == 0) mytoken.Add(new Token() { dist = 0, leng = 0, val = BytesRead[i]});
else
{
while (compare(BytesRead, i, 0) != 0)
mytoken.Add(new Token() { dist =d, leng = l-1, val = BytesRead[i+1] });
}
}
和我的比较函数:
byte compare(byte[] b, int i, int j)
{
int z = i;
if (z == j) return 0; // if j==i we stop
if (BytesRead[i]==BytesRead[j]) {l++; } //if i!=j we count the length
if (b[i] == b[j]) // if we found a match we:
{
d = 0;
int x = i;
while(x>0)
{
x--;
d++; //calculate the distance
}
}
return compare(b, i, j + 1); //go to next byte
}
我如何使算法工作?我说对了吗?我真的很难在代码中转置算法。纸面上是别的东西。我正在寻找最容易实现的版本,我不想要任何花哨的东西。
您不需要在每个距离/长度对后面都加上一个文字。可以对相同的序列进行编码:
A B C(3 2)(5 5)
匹配的位置(距离长度)。距离是从下一个要压缩的字节开始计算的,因此总是1或更多。
最直截了当的实现是在前面的数据中搜索当前序列的最长匹配。
任何实现都会有一个最大距离,它决定了滑动窗口所需的内存。还定义了一个最大长度,其中该长度和最大距离都用于定义它们在压缩数据中的编码方式。通常也会有一个大于1的最小长度,低于这个长度您最好只发送文本而不是匹配对。比如2或3。
要找到最长的匹配,从后退的最大距离开始,向前一步到等于最小长度的距离。对于其中的每一个,将窗口中的内容与当前的字节序列进行比较,以压缩到最大长度。记住那些大于最小长度的最长的一个。如果沿途遇到一个长度等于到目前为止最长的匹配项,那么就用较近的一个替换它,因为较短的距离编码的比特数会更少。
如果您找到了最小长度或更长的匹配项,那么就发出其中最长的一个,并在数据中向前推进那么多字节。如果不是,那么发出一个字节作为文字,并向前一步。
那个算法会相当慢,而且贪婪的方法不会总是压缩最好的。但这只是个开始。