Ищу алгоритм для сжатия массива упорядоченных целых чисел

http://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-se...

https://github.com/lemire/SIMDCompressionAndIntersection

This library can decode at least 4 billions of compressed integers per second on most desktop or laptop processors. That is, it can decompress data at a rate of 15 GB/s. This is significantly faster than generic codecs like gzip, LZO, Snappy or LZ4.

Неплохо так.

Поэтому я и привёл эту ссылку. Надеюсь тебе пригодится.

Самый простой вариант сделать последовательность разностей, закодированную с переменной длиной и сжать RLE потом. После этого можно убрать остальную избыточность через deflate или xz.

Я бы вообще deflate сжимал (38% дает запросто), но он медленно распаковывается.

Я бы вообще deflate сжимал (38% дает запросто), но он медленно распаковывается.

А если взять последовательность разностей и RLE?

Попробовал snappy на последовательности разностей - вообще отлично: коэффициент сжатия 50% и время распаковки в 5-6 раз меньше, чем у стандартных gzip/deflate/lzw/zlib.

http://ipv6.lurkmo.re/Алексей_Бабушкин, же.

А годную реализацию RLE на гитхабе фиг найдешь, надо свою писать.

Плохо жмет RLE такие данные. Где snappy сжимает наполовину, RLE (простая реализация с гистограммой) - всего на 1%, в то время как скорость у snappy всего на чуточку меньше.

Попробовал snappy на последовательности разностей

можно не строить последовательность разниц - результат snappy не будет существенно отличаться, такими вычислениями вы не изменяете избыточность.

сугубо академично: вопрос у вас скорее не о сжатии данных, а о наиболее компактном представлении множества. Если знать больше о данных (вероятность дублировании значений, типичные длины выборок и прочее) то тут могут накидать идей/методов по «сжатию» в разы и на порядки, а не на жалкие 30-40%

Попробовал snappy на последовательности разностей...

А если транспонировать? Жать не оригинальную последовательность, а сначала старшие байты, потом помладше итд?

Ха. Тоже к этому пришел - еще до прочтения ответа. Результат значительно улучшается, да.

Значения уникальные, не повторяются.

Собственно, это набор ID-шников - от 1 до N, с пропусками.