提问者:小点点

我理解LZ77算法,但我不能使它在代码中工作[关闭]


我们来做一个简单的输入:

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
        }

我如何使算法工作?我说对了吗?我真的很难在代码中转置算法。纸面上是别的东西。我正在寻找最容易实现的版本,我不想要任何花哨的东西。


共1个答案

匿名用户

您不需要在每个距离/长度对后面都加上一个文字。可以对相同的序列进行编码:

A B C(3 2)(5 5)

匹配的位置(距离长度)。距离是从下一个要压缩的字节开始计算的,因此总是1或更多。

最直截了当的实现是在前面的数据中搜索当前序列的最长匹配。

任何实现都会有一个最大距离,它决定了滑动窗口所需的内存。还定义了一个最大长度,其中该长度和最大距离都用于定义它们在压缩数据中的编码方式。通常也会有一个大于1的最小长度,低于这个长度您最好只发送文本而不是匹配对。比如2或3。

要找到最长的匹配,从后退的最大距离开始,向前一步到等于最小长度的距离。对于其中的每一个,将窗口中的内容与当前的字节序列进行比较,以压缩到最大长度。记住那些大于最小长度的最长的一个。如果沿途遇到一个长度等于到目前为止最长的匹配项,那么就用较近的一个替换它,因为较短的距离编码的比特数会更少。

如果您找到了最小长度或更长的匹配项,那么就发出其中最长的一个,并在数据中向前推进那么多字节。如果不是,那么发出一个字节作为文字,并向前一步。

那个算法会相当慢,而且贪婪的方法不会总是压缩最好的。但这只是个开始。