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

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

0 голосов
/ 01 октября 2018

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

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

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

Я полагаю, что это может быть гораздо быстрее.

Это, в основном, вариант скользящего окна Lz77.

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

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

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

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

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

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

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

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

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

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

1 Ответ

0 голосов
/ 01 октября 2018

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

Map<Byte, List<Integer>>

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

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

Точно так же, List<Integer> подразумевает автобокс при запуске с 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.

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

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

...