Определение наилучшего алгоритма сжатия для серии байтов

Question

Для своего личного проекта я пишу небольшой класс для сжатия в довольно непонятный формат и распаковки из него.У меня есть полная спецификация, но проблема не в этом.

Во-первых, этот "формат" использует набор из 6 различных типов сжатия, а также несжатые блоки байтовых данных.Форматы являются RLE, ответвлением RLE, где число увеличивает каждый байт (например3, 4, 5, ...), 16-битный RLE, LZ-копия, обратная LZ-копия и LZ-копия Xor'd с 255.Это не самая чистая спецификация, но и не я ее разрабатывал.

Предполагается, что моя процедура сжатия будет принимать массив размером от 1 до 65535 байт и (надеюсь) сжимать его как можно больше.Моя предыдущая попытка сделать это просто вычислила, начиная с любого индекса в несжатом потоке, какой из описанных выше методов сжатия обеспечит наилучшее сжатие, а затем сжимает столько байтов, сколько этот метод сожмет до массива сжатых байтов, прежде чем повторять из нового "несжатого" индекса, например:

{0,0,0,1,2,3,4}

Алгоритм сначала прочитал бы, что в начале было три нуля, а затем вывел бы кодировку RLE для них, которую использовала спецификация, а затем, начиная с четвертого элемента, прочитал бы, что увеличивающийся RLE будет достаточно хорошо охватывать '1,2,3,4' и сжимать это перед возвратом.

Резюмируемая проблема заключается в том, что при попытке найти наилучшую спецификацию для использования процедура очень медленно даже на небольших (20-30) байтовых массивах.Кто-нибудь может помочь советами о том, как я мог бы это оптимизировать, или есть ли еще какая-либо информация, которую я мог бы предоставить, чтобы помочь?

Answer 1

Похоже, что вы пытаетесь разработать большое количество возможностей сжатия для каждого возможного сегмента (давайте назовем ваши блоки переменной длины сегментами от 1 до 64 КБ) файла.Поправьте меня, если я ошибаюсь, но разрабатываете ли вы наилучшее сжатие для первого сегмента из следующих вариантов (метод 0 является несжатым):

• метод сжатия 0, длина 1 байт.
• метод сжатия 1, длина 1 байт.
• : : : : :
• метод сжатия 6, длина 1 байт.
• метод сжатия 0, длина 2 байта.
• метод сжатия 1, длина 2 байта.
• : : : : :
• метод сжатия 6, длина 65534 байта.
• метод сжатия 0, длина 65535 байт.
• метод сжатия 1, длина 65535 байт.
• метод сжатия 2, длина 65535 байт.
• метод сжатия 3, длина 65535 байт.
• метод сжатия 4, длина 65535 байт.
• метод сжатия 5, длина 65535 байт.
• метод сжатия 6, длина 65535 байт.

Это займет огромное количество времени (примерно 420 000 попыток сжатия на сегмент).Если это то, что вы делаете, вам будет лучше выбрать один размер сегмента (например, 64 КБ) и применить к нему каждый из семи методов сжатия, чтобы выбрать наилучший.Затем для каждого сегмента выведите байт "метода", за которым следуют сжатые данные.