Сжатие последовательности уникальных отсортированных чисел

Question

Я проект, над которым я работаю, у меня есть последовательность чисел (около 2 миллиардов). Каждое число составляет 4 байта и уникально. Числа сортируются. Моя цель - прочитать их в RAM как можно скорее в несжатом формате. Это не касается места на жестком диске.

Если я храню их несжатыми, мне нужно 2 миллиарда * 4 байта = 8 ГБ. Это займет около 100 секунд для чтения. Я могу хранить данные как последовательность бит, и для этого потребуется 2 миллиарда/8 = 250 МБ. Это займет около 3 секунд для чтения.

Мне нужно прочитать и распаковать их примерно на 0,1-0,5 секунды (если возможно) с помощью обычного жесткого диска. Мне все равно, сколько времени потребуется для сжатия данных, но мне очень важно, сколько времени потребуется для их распаковки, и мне нужно, чтобы это было сделано за несколько миллисекунд.

Случайность чисел неизвестна.

Вопрос:: Какой алгоритм сжатия может сжать номера примерно до 20-30 МБ с временем декомпрессии 100-200 миллисекунд с использованием процессора i3-i5?

EDIT: Максимальное количество в последовательности будет 2 миллиарда. Вот почему я могу хранить его на бит-массиве размером 250 МБ. Размер последовательности не всегда составляет 2 миллиарда. Он может содержать от 1 до 2.000.000.000 номеров.

Answer 1

Здесь возможны два подхода:

1. автор вопроса предлагает хранить последовательность чисел в виде битовой строки. Например: если номер i находится в последовательности, то бит битовой строки устанавливается в единицу, в противном случае - ноль. i^th бит битовой строки установлен в единицу. Естественным первым делом попробовать - применить стандартные алгоритмы сжатия к этой битовой строке и посмотреть, что произойдет.

2. Из формулировки вопроса кажется, что мы можем обрабатывать числа в последовательности как 4-байтовые int. Таким образом, сохраняемая последовательность представляет собой около 2 * 10 из возможных 2 ints. Это означает, что средняя разница между любыми двумя последовательными числами не может превышать ~ 2.147 = 2/(2 * 10). Таким образом, возможно, вычисляя последовательность различий и попытайтесь сжать это. Поскольку я ожидал бы, что большая часть последовательных различий будет 1 и 2, я подозреваю, что эта последовательность может быть очень сжимаемой.

Answer 2

Вашего подход, чтобы сохранить его в виде последовательности бит будет работать так же, как можно было бы ожидать, но это заняло бы 512 МиБа иметь немного для каждого четыре-байтового целого числа, а не 250 МБ.

Схема дельта-кодирования будет работать лучше для менее плотного набора, но не этого (как описано в исходном вопросе, который был случайным выбором половины возможных 32-битных целых чисел). Здесь дельта 1 будет происходить примерно в половину времени, дельта 2 - четверть времени и т. Д. Это привело бы к 2 + 2х2 + 3х2 + ... = 2 бит. То же, что и бит-векторный подход.

Схема оптимального сжатия будет принимать логарифм по основанию 2 2 выбрать 2 бит. Это также оказывается 2 бит. (На самом деле, 2 -16 бит, поэтому можно было бы сохранить колоссальные 16 бит из четырех миллиардов.)

Итак, бит-бит так же хорош, как и он.

Обновленный вопрос совершенно другой. Теперь вопрос имеет широкий диапазон значений от одного до всех 31-битных целых чисел и спрашивает, как сжать это до 20 MiB до 30 MiB.

Эти сжатые размеры устанавливают ограничение на размер набора. Учитывая размер набора, можно просто подсчитать количество возможных подмножеств 31-битовых целых чисел такого размера, назовем его n. Это число возможных подмножеств равно 2 n. "choose" is the binomial coefficient. Логарифмической базой 2 этого числа возможных подмножеств является теоретический минимум сжатого размера конкретного подмножества в битах, предполагая, что все такие подмножества одинаково вероятны.

Итак, теперь мы можем вычислить максимально возможный размер, который может сжиматься до 20 MiB до 30 MiB. Это составляет от 21 до 34 миллионов. Вы также можете сжать подмножества размера 2 минус 21-34 миллиона, поскольку вы можете думать о тех, которые идентифицируются по отсутствующим значениям, а не по отношению к значениям, которые там есть. Все, что находится между ними, займет более 30 мегабайт для представления в теоретически оптимальной схеме сжатия. В обновленном вопросе рассматривается весь спектр возможных подмножеств, подавляющее большинство из которых составляет от 34 до 2,1 миллиарда.

Итак, в нижней строке, это невозможно, чтобы сжать описанные последовательности в любом месте, как указано в обновленном вопросе.