Как я могу оптимизировать мой компрессор сдвижного окна Lz77?

Question

Я написал Java-компрессор для очень непонятного формата сжатия. (В основном он использовался на Amiga Computers в 1990-х годах).

Существует довольно много документации о том, как распаковать формат файла, но не о том, как на самом деле сжать его.

Итак, я попытался сделать это сам. Это работает, но есть одна проблема. У меня уходит 42 секунды на сжатие всех файлов, которые я хочу сжать, на "настройках низкой интенсивности". Это займет примерно в 10 раз больше времени при более высоких настройках интенсивности.

Я считаю, что это может быть намного быстрее, чем это.

Это в основном вариант с раздвижными окнами Lz77.

Настоящим узким местом является поиск существующего источника для сжатия. Прямо сейчас я использую Map<Byte, List<Integer>> (The List<Integer> это все индексы, в которых присутствует байт.)

Чтобы найти потенциальное совпадение, он делает следующее:

Он принимает текущий индекс файла, который сжимается. Это получает List<Integer> с карты с байтом в текущем индексе.

Он находит самый длинный подсписок байтов, который уже содержится в файле, используя этот список, и просто проверяя, как долго они совпадают.

Я думаю, что лучшая структура данных могла бы значительно ускорить это, но я застрял на этом этапе.

Одно из ограничений, с которыми мне приходится работать, заключается в том, что мне необходимо строго придерживаться этого древнего формата сжатия, в зависимости от характера этой программы.

Как я могу оптимизировать сжатие, не делая его менее эффективным при упаковке данных?

Основной код узкого места:

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]);
}

Полный код здесь для всех, кому это нужно.

Answer 1

Вам не хватает кучу оптимизаций, особенно низкоуровневых.

Map<Byte, List<Integer>>

Это очень неэффективно.

На самом деле, Map довольно быстро, но гораздо медленнее, чем массив. Вместо map.get(someByte), что делает автобокс и поиск карты (некоторые вычисления индекса и несколько обращений к массиву), вы можете сделать один доступ к массиву, используя array[someByte & 0xFF], получая примерно на порядок ускорение.

Так же, List<Integer> подразумевает автобокс, как вы начинаете с ints. Автобокс обычно приемлем, но не тогда, когда он лежит в основе требовательного алгоритма. Вы можете написать собственный класс, ведущий себя как 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.

Это в два раза быстрее, но, как я уже писал, вы должны использовать массив здесь.

---

Что касается высокоуровневых оптимизаций, я не знаю, как эффективно сжимать, но я уверен, что есть немало хитростей. Если бы не было ресурсов на сжатие, я бы начал со скользящего хэша. Но сначала прочитайте о сжатии.