0

我为超级晦涩的压缩格式编写了一个 Java 压缩器。（它主要用于 1990 年代的 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]);
}

完整代码在这里供任何需要它的人使用。

4

1 回答 1

0

你错过了一堆优化，尤其是低级优化。

Map<Byte, List<Integer>>

这是非常低效的。

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

同样，List<Integer>当您从 s 开始时，意味着自动装箱int。自动装箱通常是可以接受的，但当它位于要求苛刻的算法的核心时则不行。您可以为它编写一个行为类似List<int>或 google 的自己的类（有一些很好的库）。

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.

这是两倍快，但正如我写的，你应该在这里使用一个数组。

关于高级优化，我真的不知道如何有效地压缩，但我敢肯定，有很多技巧。如果没有压缩资源，我会从滚动哈希开始。但首先阅读一般的压缩。

于 2018-10-01T09:27:27.903 回答