java - 如何优化 Lz77 滑动窗口压缩机？

Question

我为一种 super 晦涩的压缩格式编写了一个 Java 压缩器。 (它主要用于 20 世纪 90 年代的 Amiga 计算机)。

有大量关于如何解压缩文件格式的文档，但没有关于实际如何压缩它的文档。

所以，我尝试自己做。它有效，但有一个问题。在“低强度设置”下，我花了 42 秒来压缩所有我想要压缩的文件。在较高强度设置下，大约需要 10 倍的时间。

我相信它可以比这快得多。

它基本上是 Lz77 滑动窗口变体。

真正的瓶颈是寻找现有的压缩对象。 现在，我正在使用 Map<Byte, List<Integer>> (List<Integer> 是该字节所在的所有索引。)

要找到潜在的匹配项，它的作用是:

它获取正在压缩的文件的当前索引。 它得到List<Integer>从 Map 中获取当前索引处的字节。

它通过使用该列表找到文件中已出现的最长字节子列表，并仅检查它们匹配的长度。

我认为更好的数据结构可以显着加快速度，但我陷入了这一点。

由于该程序的用途，我必须遵守的限制之一是我需要严格遵守这种古老的压缩格式。

如何优化压缩而不降低打包数据的效率？

主要瓶颈代码:

private static int search(byte[] data, int bufferEnd, List<Byte> target, Map<Byte, List<Integer>> dictionary) {
    int minIndex = Math.max(0, bufferEnd - getMaximumOffset(target.size())); // There's a certain point at which data will not be compressed. By calculating it here, it saves a lot of overheard, and prevents this from becoming O(n^2)

    byte test = target.get(0);
    if (!dictionary.containsKey(test))
        return -1; // No results found.

    List<Integer> possibleResults = dictionary.get(test);

    for (int i = possibleResults.size() - 1; i >= 0; i--) {
        int testIndex = possibleResults.get(i);
        if (minIndex > testIndex)
            break; // We've gone too far.

        // Test this
        boolean pass = true;
        for (int j = 1; j < target.size(); j++) {
            if (target.get(j) != data[j + testIndex]) {
                pass = false;
                break; // Break from the j for loop.
            }
        }

        if (pass) // A match has been found. Return it.
            return testIndex;
    }

    return -1;
}

调用者:

while ((tempIndex = search(data, i, searchList, dictionary)) >= 0) { // Find the longest compressable bunch of characters.
    if (data.length - 1 == readIndex) // If we've reached the end of the data, exit.
        break;

    searchList.add(data[++readIndex]);
}

完整代码 here为任何需要它的人。

Answer 1

您缺少大量优化，尤其是低级别的优化。

Map<Byte, List<Integer>>

这是非常低效的。

实际上，一个Map速度相当快，但比数组慢得多。而不是map.get(someByte) ，它执行自动装箱和映射查找(一些索引计算和一些数组访问)，您可以使用 array[someByte & 0xFF] 进行单个数组访问。 ，获得大约一个数量级的加速。

同样，List<Integer>当您从 int 开始时意味着自动装箱s。自动装箱通常是可以接受的，但当它是要求严格的算法的核心时就不行了。您可以编写一个自己的类，其行为类似于 List<int>或者谷歌搜索(有一些很好的库)。

---

if (!dictionary.containsKey(test))
    return -1; // No results found.

List<Integer> possibleResults = dictionary.get(test);

这是不必要的双重查找。除非您使用 null值，可以写为

List<Integer> possibleResults = dictionary.get(test);

if (possibleResults == null)
    return -1; // No results found.

速度是原来的两倍，但正如我所写，您应该在此处使用数组。

---

关于高级优化，我真的不知道如何有效地压缩，但我确信，有很多技巧。如果没有压缩方面的资源，我会从滚动哈希开始。但首先要了解一般的压缩。