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

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

Когда я сохраняю их в один файл, я, конечно, получаю очень большой файл. Но данные легко сжимаются.
После сжатия файла размером 5,48 ГиБ с помощью WinRAR при сильном сжатии результирующий размер файла составляет 37,4 МиБ.

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

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

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

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

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

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

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


c# compression block
person Arokh    schedule 19.11.2011    source источник
comment
Фактически, в deflate размер словаря ограничен 32 КБ (скользящее окно, в котором самый старый байт удаляется по мере добавления каждого входного байта).   -  person Cameron    schedule 19.11.2011
comment
Готовы ли вы написать свой собственный компрессор/декомпрессор?   -  person Cameron    schedule 19.11.2011

Ответы (3)


arrow_upward
5
arrow_downward

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

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

person Alexei Levenkov    schedule 19.11.2011
comment
+1 за RLE и комментарий по бенчмаркингу. Кодирование RLE + Хаффмана, вероятно, обеспечило бы достаточно хорошее сжатие, и было бы быстрее, чем обычная дефляция. Конечно, кодирование Хаффмана немного сложнее. - person Cameron; 19.11.2011
comment
RLE, кажется, нашла золото. После некоторой модификации структуры данных для оптимизации ее для RLE теперь она легко конкурирует с deflate. Тогда как RLE лишь немного больше по размеру, и у меня есть некоторые идеи по его дальнейшей оптимизации. - person Arokh; 19.11.2011

arrow_upward
4
arrow_downward

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

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

Например, 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%

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

person Cyan    schedule 19.11.2011

arrow_upward
2
arrow_downward

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

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

person Cameron    schedule 19.11.2011