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

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

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

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

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

По сути, это вариант с раздвижным окном Lz77.

Настоящим узким местом является поиск существующего экземпляра для сжатия. Прямо сейчас я использую Map<Byte, List<Integer>> (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]);
}

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