Как сжать набор уникальных натуральных чисел и сравнить два таких набора?

Question

Веб-приложение сравнивает пары множеств положительных целых чисел. Каждый набор имеет только уникальные значения, не более 210 000 000 (подходит для 28 бит). До 5 000 000 значений в каждом наборе.

Сравнивая комплекты A & B, необходимо три набора результатов: «уникально для A», «уникально для B», «общий для A & B». Особая задача - ответить на вопрос «есть ли число N в наборе S?»

Пока проект работает в ограниченных ресурсах общего хостинга под стеком LAMP. Решение Quick'n'dirty, с которым я столкнулся, заключалось в том, чтобы передать работу на хостинг MySQL, у которого больше ресурсов. Временная таблица для каждого набора, единственным столбцом с номерами является основной индекс. Редкие наборы достаточно малы, чтобы вписаться в двигатель = Память, которая быстрая. Он работает, но слишком медленный.

Ищет способ сохранить такой набор в памяти, который эффективен для поиска определенного номера внутри. Следите за тем, чтобы пространство памяти было как можно меньше.

Я пришел к идее кодирования каждого набора в виде битовой маски из 2^28 бит (32 Мб). Число, присутствующее в наборе = 1 бит. 5 млн. Номеров = 5 млн. Бит, из которых 210 млн. Многие нули == могут эффективно сжиматься?

Похоже, я изобретаю велосипед. Пожалуйста, направьте меня к «хорошо известному» решению этого конкретного случая двоичного сжатия. Я читал о кодировании Хаффмана, что кажется неправильным решением, поскольку основное внимание уделяется уменьшению размера, в то время как моя задача требует много поисков по сжатому набору.

Обновление. Просто нашел статью о Golomb coding и пример ее application to run-length encooding.

Answer 1

Существует стандартная техника сжатия, доступная для представленных больших наборов целых чисел в диапазоне, что позволяет проводить эффективную итерацию (поэтому она может легко выполнять пересечение, объединение, разницу в настройках и т. Д.), Но не позволяет осуществлять произвольный доступ (так это не годится для «есть N в S»). Для этой конкретной задачи он уменьшит набор данных примерно до семи бит, что составит около 8 МБ для наборов размером 5 000 000. В случае, если это полезно, я опишу его ниже.

Бит-векторы размером 210 000 000 бит (по 26 Мбайт каждая) являются эффективными с точки зрения вычислений, как для ответа на запрос «является N в S», так и для побитовых операций, поскольку вы можете быстро их выполнять с помощью векторизованных инструкций на современных процессорах ; это, вероятно, так же быстро, как вы собираетесь получить для вычисления пересечений на 5 000 000 элементов. Он потребляет много памяти, но если у вас столько памяти, идите на это.

Метод сжатия, который прост и почти оптимальным, если множества равномерно распределенных случайных выборок заданного размера, заключается в следующем:

1. сортировки набора (или убедитесь, что он сортируется) ,

2. Установить "текущее значение" в 0.

3. Для каждого элемента в наборе, в следующем порядке:

   а. вычесть «текущее значение» из элемента;

   b.в то время как эта разница составляет не менее 32, выведите один бит 1 и вычтите 32 из разницы;

   c. выведите один бит 0, за которым следует разность, закодированная в пять бит.

   d. установить «текущее значение» на один больше, чем элемент

Чтобы оправдать мое утверждение о том, что сжатие приведет примерно семь битов на элемент:

Понятно, что каждый элемент будет занимать шесть битов (0 плюс пятибитовая дельта); кроме того, мы должны учитывать биты 1 на шаге 3b. Обратите внимание, однако, что сумма всех дельт - это самый большой элемент в наборе, который не может превышать 210 000 000, и, следовательно, мы не сможем выполнить шаг 3b более 210 000 000/32 раза. Итак, шаг 3b. будет составлять менее семи миллионов бит, тогда как шаг 3c будет составлять 6 * 5 000 000 бит, в общей сложности 37 миллионов, или 7,4 бит на элемент (на практике это будет обычно немного меньше этого).