Быстрая проверка, является ли набор надмножеством сохраненных наборов
Проблема
Мне дано N массивов логических значений C. Я хочу организовать их в структуру данных, которая позволяет мне выполнять следующую операцию как можно быстрее: учитывая новый массив, вернуть true, если этот массив является «надмножеством» любого из сохраненных массивов. Под надмножеством я подразумеваю следующее: A является надмножеством B, если A [i] истинно для каждого i, где B [i] истинно. Если B [i] ложно, то A [i] может быть любым.
Или в терминах наборов вместо массивов:
Сохраните N наборов (каждый с C возможными элементами) в структуре данных, чтобы вы могли быстро найти, является ли данный набор надмножеством любого из сохраненных наборов.
Создание структуры данных может занять максимально много времени, но поиск должен быть максимально эффективным, а структура данных не может занимать слишком много места.
Некоторый контекст
Я думаю, что это интересная проблема сама по себе, но для того, что я действительно пытаюсь решить, вы можете предположить следующее:
- N = 10000
- C = 1000
- Сохраненные массивы разрежены
- Исследуемые массивы случайны (поэтому не являются разреженными)
То, что я придумал до сих пор
Для поиска O (NC) : Просто повторите все массивы. Но это слишком медленно.
Для поиска O (C) : у меня здесь было длинное описание, но, как указал Амит в комментариях, это был в основном BDD .Хотя у него отличная скорость поиска, у него экспоненциальное количество узлов. С такими большими N и C это занимает слишком много места.
Я надеюсь, что между этим решением O (N * C) и O (C), возможно, найдется решение O (log (N) * C), которое не требует экспоненциального количества места.
РЕДАКТИРОВАТЬ: Я придумал новую идею
Для поиска O (sqrt (N) C) : хранить массивы как префиксное дерево . При поиске массива A перейдите к соответствующему поддереву, если A [i] = 0, но посетите оба поддерева, если A [i] = 1.
Моя интуиция подсказывает мне, что это должно сделать (среднюю) сложность поиска равной O (sqrt (N) C), если вы предполагаете, что хранимые массивы случайны. Но: 1. Это не так, массивы редкие. И 2. Это всего лишь интуиция, я не могу этого доказать.
Я опробую и эту новую идею, и метод BDD, и посмотрю, какой из двух сработает лучше всего.
А пока разве эта проблема не возникает чаще? У него нет названия? Разве не было предыдущего исследования? Такое ощущение, что я изобретаю велосипед здесь заново.