LZ77优化

Question

我有一个用于LZ77压缩算法的代码。小文件工作正常。但是，如果我要压缩100 kB和更大的文件，则需要很多时间。

我认为，这完全是因为这部分：

do { // searchin for longest mathcing
                j++;
                i++;
                if(!lookBuffer[i]) fread(&lookBuffer[i], 1, 1, from);

                if (j == strlen(searchBuffer) && lookBuffer[addJ] == lookBuffer[i]) {
                    do {
                        i++;
                        j++;
                        if(!lookBuffer[i]) fread(&lookBuffer[i], 1, 1, from);
                        addJ++;
                    } while (lookBuffer[addJ] == lookBuffer[i] && i < lookLen);
                }
            } while (searchBuffer[j] == lookBuffer[i] && i < lookLen);

此部分搜索搜索缓冲区和超前缓冲区之间的最长匹配项。

所以，有没有更快的方法来找到此匹配项？

LZ77压缩的完整代码：

 void lz77(char *fileName, FILE *from, FILE *path, long long size) {

char *searchBuffer = (char*)malloc((searchLen) * sizeof(char)); // search array
memset(searchBuffer, 0x00, searchLen);

long i = 0, j = 0, length = 0, offset = 0, isMatching = 0, iForSearchBuff = 0, iForLookBuff = 0;
int isFirst = 1, n = 0;
unsigned char symbol;

while(!feof(from)) {
    isMatching = 0;
    length = 0;
    iForSearchBuff = 0;
    iForLookBuff = 0;
    offset = strlen(searchBuffer);
    if (isFirst) { // first symbol
        fread(searchBuffer, 1, 1, from); 
        writeBit(0, 0, *searchBuffer, tmpFile); // writing(0, 0, symbol)
        isFirst = 0;
    } else {
        char *lookBuffer = (char*)malloc((lookLen) * sizeof(char)); // look array
        memset(lookBuffer, 0x00, lookLen);

        fread(lookBuffer, 1, 1, from);

        for (j = 0; j <= strlen(searchBuffer); j++) {

            i = 0;
            if (searchBuffer[j] == lookBuffer[i]) { // MATCHING
                isMatching = 1;
                long fixJ = j, fixI = i, addJ = 0;

                do { // searchin for longest mathcing
                    j++;
                    i++;
                    if(!lookBuffer[i]) fread(&lookBuffer[i], 1, 1, from);

                    if (j == strlen(searchBuffer) && lookBuffer[addJ] == lookBuffer[i]) {
                        do {
                            i++;
                            j++;
                            if(!lookBuffer[i]) fread(&lookBuffer[i], 1, 1, from);
                            addJ++;
                        } while (lookBuffer[addJ] == lookBuffer[i] && i < lookLen);
                    }
                } while (searchBuffer[j] == lookBuffer[i] && i < lookLen);

                if (((strlen(searchBuffer) - fixJ) <= offset) && ((i - fixI) >= length)) { 
                    length = i - fixI;
                    offset = strlen(searchBuffer) - fixJ;
                    iForSearchBuff = fixI;
                    iForLookBuff = i;
                }

                j = fixJ;

            } else if (j >= (strlen(searchBuffer))) {
                if (isMatching) {
                    if (lookBuffer[iForLookBuff] == '\0') { writeBit(offset, length, ' ', tmpFile);}
                    else {
                        writeBit(offset, length, lookBuffer[iForLookBuff], tmpFile);
                        searchBuffer = insertIntoBuffer(searchBuffer, length + 1, &lookBuffer[iForSearchBuff]);
                    } 

                    isMatching = 0;
                    break;
                } else {
                    writeBit(0, 0, lookBuffer[i], tmpFile);

                    searchBuffer = insertIntoBuffer(searchBuffer, 1, &lookBuffer[i]);
                    break;
                }
            }

        }
    }
}

}

Answer 1

保留一个由窗口中每个字符串的前'n'个字节索引的表-其中'n'是您想要的最小长度匹配（可能为2）。您可能有多个以相同的“ n”个字节开头的字符串，因此此表中的条目是字符串列表，每个字符串在窗口中的偏移量。您可能希望以距离窗口末端最小的距离进行最长匹​​配。专门处理以相同字节长距离开头的字符串可能是值得的。向前移动窗口时，需要从表中删除字符串并添加新的字符串。

Answer 2

我不是专家，但是聪明的人已经设计出了可以在此处应用的高效搜索算法。例如，检查Knuth–Morris–Pratt算法https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm