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

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

• в памяти
• очень мало памяти
• скорость

Вот моя «проблема»: мне нужно хранить , в памяти, огромное количество очень разреженных битовых массивов. Эти битовые наборы предназначены только для добавления и должны использоваться в основном для пересечений. Под огромным я подразумеваю массивы размером до 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 следующих бит (всегда 5) говорят, сколько бит нам нужно сказать, сколько бит мы пропустим 22 бита говорят перейти к 3098137 один бит сказать, что теперь мы не пропускаем биты 5 следующих бит (всегда 5) говорят, сколько бит мы прочитаем "как есть" 6 бит: off, off, off, on, off, on означает, что 3098141 и 3098143 включены и т. д.

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

  Итак, используя эту кодировку, я взял свои образцы данных и вычислил «наихудший» сценарий (я еще не написал алгоритм, я бы предпочел сначала получить несколько исходных данных отсюда): в основном я считал, что не только "оптимизация размера" никогда не сработает, а также то, что 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 МБ, и это нормально.

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

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

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

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

  Итак, у меня есть много битовых массивов одинакового размера, которые все очень разрежены (

  ---

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

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