Как компрессировать упорядоченный массив уникальных натуральных чисел огр. диапазона?

Question

[Сергей Соколов]

Веб приложение сравнивает попарно наборы целых положительных чисел.

Каждый набор не содержит внутри себя повторов, любое из чисел не больше 210 млн. (28 бит).

В наборе их может быть от 1 до 5 млн.


Сравнивая наборы A и B надо получить наборы «уникальные для A», «уникальные для B» и «общее ядро». В частности, просто отвечать на вопросы «Есть ли в наборе S число N?»


Реализация, увы, на php и пока на shared hosting. Наскоро реализовал, нагрузив хостинговый MySQL: под каждый сет временная таблица с единственной колонкой-индексом. В большинстве случае таблицы превышают размер, который помещается в engine=Memory, и на дисковых таблицах это совсем небыстро, но работает.


Как эффективно держать такой набор, чтобы сравнение двух сетов выполнялось быстро, занимя минимальный footprint по памяти?


Пришло в голову записать каждый набор битовой маской длиной в 2^28 бит (32Mb). Из 210 млн бит всего 5 млн единиц, остальные 0: их можно записывать числом нулей подряд, например. Очень похоже на велосипед. Подскажите всем, кроме меня, известный алгоритм, эффективный для компрессии бинарных данных в частном случае «много нулей подряд»?


Про Huffman coding читал, похоже, он будет неэффективен для поиска каждого из 5 млн. чисел второго сета внутри первого.

Comments

[weirdan]

А каков размер, в среднем, «общего ядра» по сравнению с размером наборов?

[Сергей Соколов]

95% в одном случае (измеряется изменение множества за небольшое время), и от 0 до 99% в другом (сравниваются два разных множества).

Answer 1

[MikhailEdoshin]

Вообще это run-length encoding. Находить пересечение и разность можно без распаковки, просматривая параллельно оба набора, а вот проверку произвольного числа можно будет сделать тоже только просмотром, не очень эффективно.

Answer 2

[weirdan]

Для ускорения сравнения в случае с предположительно малым общим ядром можно из каждого набора сделать Bloom Filter (для которого можно балансировать точность/потребление памяти). Тогда придется проверять вхождение только для тех элементов, для которых проверка по фильтру вернет «in set».

Answer 3

[MikhailEdoshin]

Учитывая, что чисел мало, проще хранить их в отсортированном массиве — 5 млн 32-битовых чисел займут 19 МБ, пересечение и разность находятся так же параллельным просмотром за O(N + M), проверка вхождения элемента двоичным поиском — O(log N).

Comments

[Сергей Соколов]

нет 19Мб. Тем более, в PHP памяти потребуется раза в два больше. Сейчас так «в лоб» и храню — в БД, индексированная колонка 32-битных целых. Там же сравниваю. Уникальность частного случая в отсутствии повторов, непринципиальности порядка и известном диапазоне. Из этих трёх частностей хочется выжать ацки эффективную компрессию, скорость и малую требуемую память.

[MikhailEdoshin]

Чтобы сжать последовательность нулевых битов нужна метка, что дальше идут не данные, а число, а затем — это число. Допустим, эти числа у вас будут фиксированного размера в 32 бита — вам тогда потребуются те же самые пять миллионов 32-битных чисел для обозначения сжатых участков. Можно, наверное, как-то извратиться и использовать числа переменной длины, но это еще усложнит код, а он и так уже нарисовывается непростой. Отсортированный же массив можно хранить в простом файле и считывать его по частям (правда, заполнить такой массив будет потруднее). Кстати, раз числа не 32-битные, можно использовать верхние биты для служебной информации — например, создать один массив, а в верхних битах отмечать, к каким наборам это число относится.

[Сергей Соколов]

от фикс. длины «слов» точно надо отойти: только поток битов. Нашёл описание Golomb кодирования, похоже — то, что мне нужно.

[MikhailEdoshin]

Да, Golomb, пожалуй, подойдет, судя по описанию, должен довольно эффективно сжимать.