C # Сжатие большого количества блоков данных быстро / эффективно

Question

У меня около 270 тыс. Пар блоков данных, каждая пара состоит из одного 32-килобайтного блока и одного 16-килобайтного блока.

Когда я сохраняю их в один файл, я, конечно, получаю очень большой файл.Но данные легко сжимаются.
После сжатия файла 5.48GiB с помощью WinRAR с сильным сжатием размер получаемого файла составляет 37.4MiB.

Но мне нужен произвольный доступ к каждому отдельному блоку, поэтому я могу сжимать только блоки по отдельности.
Для этого я использовал класс Deflate, предоставленный .NET, который уменьшил размер файла до 382 МБ (который яможет жить с).
Но скорость не достаточно хорошая.

Большая потеря скорости, вероятно, из-за постоянного создания нового экземпляра MemoryStream и Deflate для каждого блока.Но кажется, что они не предназначены для повторного использования.

И я думаю (намного?) Лучшее сжатие может быть достигнуто, когда вместо этого используется «глобальный» словарь, имеющий один для каждого блока.

Существует ли реализация алгоритма сжатия (предпочтительно в C #), который подходит для этой задачи?

Следующая ссылка содержит процент, с которым встречается каждый номер байта, разделенный на три типа блоков (только блоки 32 КБ),Первый и третий тип блока имеют встречаемость 37,5%, а второй 25%. Проценты типа блока

Длинный рассказ: Тип1 состоит в основном из единиц.Тип2 состоит в основном из нулей и единиц Тип3 состоит в основном из нулей Значения больше 128 не встречаются (пока).

Блок 16 КБ почти всегда состоит из нулей

Answer 1

Если вы хотите попробовать другое сжатие, вы можете начать с RLE, который должен подходить для ваших данных - http://en.wikipedia.org/wiki/Run-length_encoding - это будет невероятно быстро даже в самой простой реализации.Связанная http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms содержит больше ссылок для запуска по другому алгоритму, если вы хотите свернуть свою собственную или найти чью-то реализацию.

Случайный комментарий: "... Вероятно, потеря скорости очень высока... "это не способ решить проблему производительности.Измерьте и посмотрите, действительно ли это так.

Answer 2

Gzip, как известно, «в порядке», что означает, что степень сжатия в порядке, а скорость хорошая.Если вы хотите больше сжатия, существуют другие альтернативы, такие как 7z.

Если вы хотите больше скорости, что кажется вашей целью, более быстрая альтернатива обеспечит значительное преимущество в скорости за счет некоторой эффективности сжатия.«Значительный» переводится во много раз быстрее, например, 5x-10x.Такие алгоритмы предпочтительны для сценариев сжатия «в памяти», таких как ваш, поскольку они делают доступ к сжатому блоку практически безболезненным.

Например, Clayton Stangeland только что выпустил LZ4 для C #.Исходный код доступен здесь под лицензией BSD: https://github.com/stangelandcl/LZ4Sharp

На домашней странице проекта есть несколько метрик сравнения с gzip, например:

i5 memcpy 1658 MB/s
i5 Lz4 Compression 270 MB/s Decompression 1184 MB/s  
i5 LZ4C# Compression 207 MB/s Decompression 758 MB/s 49%
i5 LZ4C# whole corpus Compression 267 MB/s Decompression 838 MB/s Ratio 47%
i5 gzip whole corpus Compression 48 MB/s Decompression 266 MB/s Ratio 33%

Надеюсь, это поможет.

Answer 3

Вы не можете иметь произвольный доступ к потоку Deflate, независимо от того, как сильно вы пытаетесь (если только вы не утратите партию LZ77, но это то, что в основном отвечает за повышение степени сжатия прямо сейчас - и даже тогда, есть хитрые вопросы, чтобы обойти). Это связано с тем, что одной части сжатых данных разрешено ссылаться на предыдущую часть длиной до 32 Кбайт, что может также относиться к другой части по очереди и т. Д., И в конечном итоге вам придется начинать декодирование потока с самого начала, чтобы получить данные, которые вы хотите, даже если вы точно знаете, где они находятся в сжатом потоке (чего в настоящее время нет).

Но то, что вы могли бы сделать, это сжать много (но не все) блоков вместе, используя один поток. Тогда вы получите довольно хорошую скорость и сжатие, но вам не придется распаковывать все блоки, чтобы получить тот, который вы хотели; только конкретный блок, в котором находится ваш блок. Вам нужен дополнительный индекс, который отслеживает, где каждый сжатый блок блоков начинается в файле, но это довольно низкие накладные расходы. Думайте об этом как о компромиссе между сжатием всего вместе (что отлично подходит для сжатия, но отстой для произвольного доступа) и сжатием каждого куска по отдельности (что отлично подходит для произвольного доступа, но отстой для сжатия и скорости).