Экономичный способ хранения мультимножества / неупорядоченного списка

Question

Мне нужно хранить большое количество целых чисел в файле. Порядок целых чисел не имеет значения, поэтому общее содержание информации должно быть ниже, чем в упорядоченном списке. Есть ли более эффективный способ хранения чисел, чем в произвольно упорядоченном массиве?

Редактировать: я предполагаю, что целые числа совершенно случайно. Я действительно ищу универсальный способ выжать лишнюю информацию, которая вводится путем исправления перестановки.

Answer 1

Чтобы сжимать, вам на самом деле нужен более высокий информационный контент. Вы не можете вообще сжать случайность. К счастью для вас, ваша спецификация проблемы позволяет вам изменить порядок данных. Поэтому вы можете сортировать данные, тем самым увеличивая их информационное содержание. Затем, вместо того, чтобы хранить список целых чисел, вам нужно хранить только самые маленькие и последовательность первых разностей. Первые различия будут меньше самих чисел, поэтому должны умещаться в меньшее количество разрядов.

Сортированная случайным образом сгенерированная последовательность

sorted seq     (173 218 257 490 618 638 715 815 856 929 932 996)
number of bits (  6   6   6   7   7   7   7   7   7   7   7   7)

может быть сохранен как

first diff     (173 45 39 233 128 20 77 100 41 73 3 64)
number of bits (  6  4  4   6   5  3  5   5  4  5 2  5)

Где, например, 45 - это разница между 173 и 218, первым и вторым элементами. Эти цифры требуют 54 бит против 81 выше. Если числа достаточно плотны в диапазоне, из которого они взяты, вы можете увидеть, что максимальные биты для первого различия будут меньше, чем данные, позволяющие вам использовать меньшую фиксированную битовую длину. Если вы не используете фиксированный размер, вы также должны хранить разделители или использовать другую адаптивную схему, чтобы вы могли определить, где одно число заканчивается, а другое начинается. Если ваши данные имеют большое количество дубликатов, как это происходит, если ваши числа выбираются случайным образом из относительно небольшого диапазона, вы также можете посмотреть на длину прогона, кодирующую нули в первых различиях.

Answer 2

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

Answer 3

Эта статья делает именно это.

Сжатие мультимножеств с большими алфавитами

Бумага: https://arxiv.org/abs/2107.09202

Код: https://github.com/facebookresearch/multiset-compression

Резюме: https://twitter.com/_dsevero/status/1419661190750425102