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

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

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

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

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

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

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

Сравнение структур данных: Массивы и объекты в Javascript
Сравнение структур данных: Массивы и объекты в Javascript
Итак, вы изучили основы JavaScript и хотите перейти к изучению структур данных. Мотивация для изучения/понимания Структур данных может быть разной,...
8
0
3 233
7
Перейти к ответу Данный вопрос помечен как решенный

Ответы 7

Ответ принят как подходящий

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

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

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

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

I GIVE CRAP ANSWERS 05.10.2008 19:16

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

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

Предположим, у вас есть произвольное подмножество 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 бит. Просто оно того не стоит.

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

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

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

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

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

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

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

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

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

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

Спасибо, Антей, я на самом деле уже изучал кодирование диапазона, так как принятый ответ цитирует кодирование Хаффмана как всего лишь один пример сжатия без потерь. Однако Хаффмана легко реализовать и он хорошо работает с умеренно асимметричным вводом. Для сильно асимметричного ввода хороши методы длин серий.

erickson 18.09.2008 09:02

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

Спасибо, Билл. Я помню, как слышал о массивах Джуди раньше, но совершенно забыл о них. Я еще раз посмотрю на них.

erickson 17.06.2009 22:03

Другие вопросы по теме