Какие есть альтернативы битовому массиву?

Question

У меня есть приложение для поиска информации, которое создает битовые массивы порядка десятков миллионов битов. Количество «установленных» битов в массиве варьируется в широких пределах, от всех понятных до всех установленных. В настоящее время я использую прямой битовый массив (java.util.BitSet), поэтому каждый из моих битовых массивов занимает несколько мегабайт.

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

• Какие структуры могут быть хорошими в каждой крайности?
• Есть ли кто-нибудь посередине?

Вот несколько ограничений или подсказок:

1. Биты устанавливаются только один раз и в порядке индекса.
2. Мне нужна 100% точность, поэтому что-то вроде фильтра Блума недостаточно хорошо.
3. После того, как набор собран, мне нужно иметь возможность эффективно перебирать биты "набора".
4. Биты распределены случайным образом, поэтому алгоритмы кодирования по длине прогона вряд ли будут намного лучше, чем простой список битовых индексов.
5. Я пытаюсь оптимизировать использование памяти, но скорость все еще несет некоторый вес.

Что-то с реализацией Java с открытым исходным кодом полезно, но не обязательно. Меня больше интересуют основы.

Answer 1

Если данные не являются действительно случайными и имеют симметричное распределение 1/0, то это просто становится проблемой сжатия данных без потерь и очень похоже на сжатие CCITT Group 3, используемое для черно-белые (т.е. двоичные) факсимильные изображения. CCITT Group 3 использует схему кодирования Хаффмана. В случае факса они используют фиксированный набор кодов Хаффмана, но для данного набора данных вы можете сгенерировать определенный набор кодов для каждого набора данных, чтобы улучшить достигнутую степень сжатия. Пока вам нужен только последовательный доступ к битам, как вы и предполагали, это будет довольно эффективный подход. Произвольный доступ создаст некоторые дополнительные проблемы, но вы, вероятно, сможете сгенерировать индекс бинарного дерева поиска для различных точек смещения в массиве, что позволит вам приблизиться к нужному местоположению, а затем войти оттуда.

Примечание : схема Хаффмана по-прежнему работает хорошо, даже если данные случайные, если распределение 1/0 не является идеально ровным. То есть чем меньше равномерное распределение, тем лучше степень сжатия.

Наконец, если биты действительно случайны с равномерным распределением, тогда, согласно Мистер. Клод Шеннон , вы не сможете сжать его сколько-нибудь значительно, используя любую схему.

Answer 2

Я бы настоятельно рекомендовал использовать кодирование диапазона вместо кодирования Хаффмана. В общем, кодирование по дальности может использовать асимметрию более эффективно, чем кодирование по Хаффману, но это особенно актуально, когда размер алфавита очень мал. На самом деле, когда «родной алфавит» - это просто 0 и 1, единственный способ, которым Хаффман может вообще сжимать любое сжатие, - это объединение этих символов - это именно то, что будет делать кодирование диапазона более эффективно.

Answer 3

Может быть, слишком поздно для вас, но есть очень быстрая и эффективная библиотека памяти для разреженных битовых массивов (без потерь) и других типов данных, основанных на попытках. Посмотрите на массивы Джуди

Answer 4

Еще одна мысль о сжатии:

Если битовый массив не слишком длинный, вы можете попробовать применить преобразование Барроуза-Уилера перед использованием любой кодировки повторения, такой как Хаффман. Наивная реализация потребовала бы O (n ^ 2) памяти во время (де) сжатия и O (n ^ 2 log n) времени для распаковки - почти наверняка есть и ярлыки. Но если в ваших данных есть какая-либо последовательная структура, это действительно должно помочь в кодировании Хаффмана.

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

Answer 5

Спасибо за ответы. Вот что я собираюсь попробовать для динамического выбора правильного метода:

Я соберу все первые N хитов в обычном битовом массиве и выберу один из трех методов, основанных на симметрии этого образца.

• Если образец сильно асимметричный, Я просто сохраню индексы в установить биты (или, возможно, расстояние до следующий бит) в списке.
• Если образец очень симметричный, Я буду продолжать использовать обычный бит массив.
• Если образец умеренно симметричный, я буду использовать без потерь метод сжатия, как Хаффман кодировка предложенная InSciTekJeff .

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

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

Answer 6

Быстрое комбинаторное доказательство того, что вы не можете сэкономить много места:

Предположим, у вас есть произвольное подмножество из n / 2 битов, равное 1 из n всех битов. У вас есть (n выбрать n / 2) возможностей. Используя формулу Стирлинга , это примерно 2 ^ n / sqrt (n) * sqrt (2 / pi). Если каждая возможность одинаково вероятна, то нет более вероятного выбора более коротких представлений. Таким образом, нам нужно log_2 (n выбирать n / 2) битов, что составляет около n - (1/2) log (n) битов.

Это не очень хорошая экономия памяти. Например, если вы работаете с n = 2 ^ 20 (1 мегабайт), вы можете сохранить только около 10 бит. Это просто не стоит.

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

Answer 7

Прямое сжатие без потерь - путь. Чтобы сделать его доступным для поиска, вам придется сжать относительно небольшие блоки и создать индекс в массив блоков. Этот индекс может содержать битовое смещение начального бита в каждом блоке.