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

Question

У меня особая потребность, и самые важные проблемы:

• в памяти
• очень низкий объем памяти
• скорость

Вот моя «проблема»: мне нужно хранить в памяти огромное количество очень редких битовых массивов.Эти наборы битов «только для добавления» и должны использоваться в основном для пересечений.Под огромным я подразумеваю до 200 000 битовых массивов.

Диапазон должен быть между [0 ... 16 000 000] для каждого набора битов.

Я провел предварительное тестирование с«только» 10 673-битных массивов, содержащих некоторые реальные данные, которые я получил и получил следующие результаты:

  1% of the bit arrays (  106 bit arrays) Hamming weight: at most     1 bit  set
  5% of the bit arrays (  534 bit arrays) Hamming weight: at most     4 bits set
 10% of the bit arrays ( 1068 bit arrays) Hamming weight: at most     8 bits set
 15% of the bit arrays ( 1603 bit arrays) Hamming weight: at most    12 bits set
 20% of the bit arrays ( 2137 bit arrays) Hamming weight: at most    17 bits set
 25% of the bit arrays ( 2671 bit arrays) Hamming weight: at most    22 bits set
 30% of the bit arrays ( 3206 bit arrays) Hamming weight: at most    28 bits set
 35% of the bit arrays ( 3740 bit arrays) Hamming weight: at most    35 bits set
 40% of the bit arrays ( 4274 bit arrays) Hamming weight: at most    44 bits set
 45% of the bit arrays ( 4809 bit arrays) Hamming weight: at most    55 bits set
 50% of the bit arrays ( 5343 bit arrays) Hamming weight: at most    67 bits set
 55% of the bit arrays ( 5877 bit arrays) Hamming weight: at most    83 bits set
 60% of the bit arrays ( 6412 bit arrays) Hamming weight: at most   103 bits set
 65% of the bit arrays ( 6946 bit arrays) Hamming weight: at most   128 bits set
 70% of the bit arrays ( 7480 bit arrays) Hamming weight: at most   161 bits set
 75% of the bit arrays ( 8015 bit arrays) Hamming weight: at most   206 bits set
 80% of the bit arrays ( 8549 bit arrays) Hamming weight: at most   275 bits set
 85% of the bit arrays ( 9083 bit arrays) Hamming weight: at most   395 bits set
 90% of the bit arrays ( 9618 bit arrays) Hamming weight: at most   640 bits set
 95% of the bit arrays (10152 bit arrays) Hamming weight: at most  1453 bits set
 96% of the bit arrays (10259 bit arrays) Hamming weight: at most  1843 bits set
 97% of the bit arrays (10366 bit arrays) Hamming weight: at most  2601 bits set
 98% of the bit arrays (10473 bit arrays) Hamming weight: at most  3544 bits set
 99% of the bit arrays (10580 bit arrays) Hamming weight: at most  4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set

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

Включенные биты битового массива сгруппированы, но не полностью.Таким образом, вы будете иметь тенденцию включать несколько битов в одной и той же области (но обычно не один за другим, что делает RLE не очень хорошим для включенных битов).

Мой вопрос: какой тип сжатия использовать?

Теперь я не знаю, должен ли я изложить здесь свой первый подход или ответить на свой вопрос.

По сути, я представил себе сценарий «наихудшего случая» с использованием очень тупой кодировки:

• 1 бит: если он включен, следующие 5 бит определяют, сколько бит необходимо длявычислить «пропустить», если выключено, оптимизацию: следующие 5 битов определяют, сколько битов тоже нужно брать буквально (то есть «включено» или «выключено», без пропуска) [это будет переключено только на значение, определенное как большееэффективнее, чем другое представление, поэтому, когда оно включается, оно всегда должно быть оптимизацией (по размеру)]

• 5 битов: сколько бит мы можем пропустить до следующего бита на

• x бит: пропустить

Вот пример: битовый массив имеет 3 бита, первый бит равен 3 098 137,второй в 3 098 141 и третий в 3 098 143.

                               +-- now we won't skip
                               |
                               |     +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
                               |     |    +--- 3 098 141 is on
  22    3 098 137              |     3    | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc. 

Первый бит указывает, что мы собираемся пропустить биты.5 следующих битов (всегда 5) говорит, сколько бит нам нужно, чтобы указать, сколько бит мы пропустим 22 бита, что говорит о пропуске до 3 098 137, один бит не говорит о том, что мы не пропускаем биты, 5 следующих бит (всегда 5) говорятсколько бит мы будем читать «как есть» 6 битов: выкл, выкл, выкл, вкл, выкл, в значении 3 098 141 и 3 098 143 включены и т. д.

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

Таким образом, используя эту кодировку, я взял свои примерные данные и вычислил сценарий «наихудшего случая» (я еще не написал алгоритм, я предпочел бы сначала получить несколько исходных данных): в основном я рассмотрелчто не только «оптимизация размера» никогда не включится, а также, что 5 битов всегда будут установлены на их максимальное значение (24 бита), что, конечно, не может произойти.

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

Я был очень приятно удивлен:

Worst case scenario: 

108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)

Данные являются фактическими данными, а все данные похожиЯ знаю, что если хуже станет хуже, я смогу хранить свои 200 000 битных массивов примерно в 240 МБ, и это хорошо.

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

Любые намеки / идеи относительно того, как сделать это более эффективным по размеру (если вспомнить, что это супер разреженные битовые массивы, их должно быть сотни тысяч, что они должны быть в памяти, и что они должныбыть "только для добавления")?

О моем случае "только для добавления"

В основном у меня есть один растущий "простор" (диапазон, но "простор" - фактический термин, насколько я понимаю) и множество битовых массивов, которые имеютнесколько битовКогда диапазон изменяется, скажем, от 0 до 1 000 000, все битовые массивы переходят от 0 до 1 000 000.Когда диапазон увеличивается до 1 000 001, то все битовые массивы тоже растут, все на один бит.Но к большинству этих битовых массивов будет добавлен «0» в конце, а около 4–8 битовых массивов будет иметь «1» в конце.Однако я не могу заранее предсказать, какой из битовых массивов будет иметь добавленные 0 или 1.

Так что у меня есть много битовых массивов одинакового размера, которые очень редки (<0,5% их битов установлены), и все они "растут" по мере увеличения диапазона (поэтому они все всегда растут с одинаковой скоростью). </p>

---

массивы Джуди отличный.Но я читал о них несколько лет назад, и все это было «над моей головой».Массивы Judy - это библиотека C-only 20KLOC, и я определенно не буду реализовывать это заново.Но они удивительны.

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

Answer 1

Вы не сказали, какой язык программирования вы хотите использовать.Похоже, вы не хотите, чтобы Джуди, потому что это "только для C" ... если вы используете C #, то вы могли бы вместо этого использовать мой Compact Patricia Trie .Is почти 4500 LOC (прокомментировано) и использует идеи, подобные Джуди, но размер и скорость каждого дерева не идеальны из-за ограничений .NET.Он также не оптимизирован для вычисления пересечений, но такой алгоритм может быть добавлен.В статье о CP Tries этот момент не подчеркивается, но он может хранить наборы (разреженные битовые массивы) гораздо компактнее, чем словари (графики в статье показывают размер и скорость словарей, а не наборов).

В лучшем случае это плотный кластер битов.При заполненности 50% (каждый второй установленный бит) требуется менее 8 бит на ключ (менее 4 бит на целое число).(исправление: менее 8 бит, не более.)

Если вам нужно только приблизительное представление данных, используйте фильтр Блума .

Кстати,что вы подразумеваете под «только добавление»?Означает ли это, что вы добавляете только ключи, или что каждый добавляемый вами ключ больше, чем ключи, которые вы добавили ранее?

Обновление : поскольку вы добавляете только ключи большего размера, вероятно, следует разработатьспециальный алгоритм только для вашего случая.ИМО, при разработке собственного алгоритма вы должны сделать его максимально простым.Итак, вот моя идея, которая предполагает, что ключи разных битовых наборов некоррелированы (поэтому нет смысла пытаться сжимать данные между разными битовыми наборами):

Битовый набор представлен отсортированным массивом из 32-битных слотов.Поскольку он отсортирован, вы можете использовать бинарный поиск, чтобы найти ключи.Каждый слот состоит из 24-битного «префикса» и 8 битов «флагов».Каждый слот представляет область из 8 клавиш.«Флаги» сообщают вам, какой из 8 ключей в области присутствует в наборе битов, а «префикс» указывает вам, о какой области мы говорим, указав биты с 3 по 26 ключа.Например, если следующие биты равны «1» в наборе битов:

1, 3, 4, 1094, 8001, 8002, 8007, 8009

... тогда набор битов представлен массивом из 4 слотов (16 байтов):

Prefix:     0,  136, 1000, 1001
 Flags:  0x15, 0x40, 0x86, 0x02

Первый слот представляет 1, 3, 4 (обратите внимание, что биты 1, 3 и 4 установлены в число 0x15);второй слот представляет 1094 (136 * 8 + 6);третий слот представляет 8001, 8002 и 8007;четвертый слот представляет 8009. Это имеет смысл?

Я не знаю, насколько это компактно, как ваша идея.Но я думаю, что вы получите более быстрые запросы и более быстрые модификации, и это будет довольно легко реализовать.

Answer 2

Вы можете посмотреть сжатые растровые изображения.Обычной стратегией является использование выровненного по длине слова кодирования.

Реализация C ++:

https://github.com/lemire/EWAHBoolArray

Реализация Java:

https://github.com/lemire/javaewah

Ссылка:

Даниэль Лемир, Оуэн Казер, Камель Ауиш, Сортировка улучшают растровые индексы с выравниванием по словам.Инженерия данных и знаний 69 (1), стр. 3-28, 2010. http://arxiv.org/abs/0901.3751

Answer 3

Вы можете использовать двоичное дерево для битового массива.Скажем, у вас есть массив с диапазоном [M..N].Сохраните его таким образом:

Выберите кодировку чисел для [0 ... размер оперативной памяти], например, код Фибоначчи, Голомба или Райса (вы можете выбрать наиболее подходящее представление после профилирования вашей программы с фактическими данными).

1. Если массив пуст (биты не установлены), сохраните его как число 0.
2. Если массив заполнен (все биты установлены), сохраните его как номер 1.
3. Остальное разделить на две части: A в [M .. (M + N) / 2-1] и B в [(M + N) /2..N]
4. Создатьпредставления P0 и P1, использующие этот алгоритм рекурсивно.
5. Получите длину P0 (в битах или других единицах длина может быть целым числом) и сохраните ее как число (вам может потребоваться добавить 1, если длина может быть1, например, вы храните 0 как один бит 0).
6. Сохраните P0, затем P1.

В этом случае, если ограничения являются общими, операции пересечения с объединением являются тривиальными рекурсиями:

Пересечение:

1. Если массив A пуст, сохранить 0.
2. Если массив A заполнен, сохранить копию B
3. ElРазделите массивы se, сделайте пересечения обеих половин, сохраните длину первой половины, затем обеих половин.

Этот алгоритм может работать с битами (если они должны быть максимально компактными) и байтами / словами (если битовые операции слишком медленные).

Также вы можете добавить специальные кодировки для массивов с одним битовым набором, все массивы которых имеют размер меньше некоторого предела (например, 8 элементов), чтобы уменьшить уровень рекурсии.

Недостатком является то, что без некоторых хаков добавление / удаление элемента в / из массива является сложной операцией (такой же сложной, как операции пересечения / объединения).

Например, массив с одним установленным битом 0xAB должен храниться в массиве0..0xFF as (псевдокод для):

0  1      2   3  4      5  6  7      8  9  10     11 12     13    14     15     16
1, EMPTY, 13, 1, EMPTY, 9, 1, EMPTY, 5, 1, EMPTY, 1, EMPTY, FULL, EMPTY, EMPTY, EMPTY
                                                   |  AA  | AB  |
                                         |A8..A9| AA    ..   AB |
                                      | A8         ..        AB |AC..AF|
                            |A0..A7| A8             ..              AF |
                         | A0                 ..                    AF |B0..BF|
               |80..9F| A0                        ..                       BF |
            | 80                                 ..                        BF |C0..FF|
 | 0..7F| 80                                          ..                          FF |       

EMPTY и FULL - коды для пустых и полных массивов, числа - это длины в элементах (должны быть заменены фактическими длинами в байтах, битах или около того)

Если вам не нужна быстрая проверка одного бита, вы можете использовать самый простой подход: просто сохраняйте расстояния между установленными битами, используя коды: fibonacci,рис, голомб, левенштейн, элиас и т. д. или изобрести другой.Обратите внимание, что для получения минимальной длины кода вы должны использовать код с длинами кода, максимально приближенными к -log p / log 2, где p - вероятность этого кода.Для этого вы можете использовать код Хаффмана.

Например, использовать гамма-код elias, поэтому массив должен выглядеть так:

0 1 0000 1 1 000 1 0 1 000000000000000000 1 000000000000000000 
2     5   1   4    2         19                   18           (distance)

Должен быть закодирован как:

010 00101 1 00100 010 000010011 000010010
 2    5   1   4    2     19        18     (distance code explained)

И в основном компактным для массива с равномерным распределением битов будет арифметическое кодирование, но это очень отнимает время ЦП.Потому что вам придется читать и записывать такие массивы постепенно, без быстрого пропуска.

Answer 4

Даже если они не совсем то, что вы ищете, стоит проверить Джуди деревья . Judy - сильно оптимизированная библиотека для упорядоченных карт, и одна конфигурация специально разработана как набор битов, а не карта. Я не думаю, что пересечение - это одна из операций, изначально оптимизированных для ...

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

Во всяком случае, это всегда хорошая идея украсть у лучших!

Answer 5

Возможно, вас заинтересуют двоичные диаграммы принятия решений (BDD) и, точнее, двоичная диаграмма принятия решений (ZBDD).

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

Answer 6

Учитывая, что вы все равно проведете кучу тестов пересечений, возможно, вам следует попробовать сохранить все битовые векторы параллельно. Один редкий, 16М входной список. Каждая запись в этом списке содержит список, у которого из 200k входных битовых векторов есть «1» в этом месте. Похоже, вы ожидаете, что на каждый входной вектор будет установлено всего около 5 бит или 1М всего записей? Принимая реализацию связанного со списком соломенного человека для верхнего уровня и сегментов, и наихудший случай отсутствия пересечений вообще (например, 1M сегментов с 1 элементом в каждом), вы можете хранить все это в 32МБ.