Быстрая проверка, является ли набор надмножеством сохраненных наборов
Мне дано N массивов C логических значений. Я хочу организовать их в структуру данных, которая позволит мне выполнить следующую операцию как можно быстрее: для нового массива вернуть true, если этот массив является «надмножеством» любого из сохраненных массивов. Под надмножеством я имею в виду следующее: A является надмножеством B, если A [i] истинно для каждого i, где B [i] истинно. Если B [i] ложно, то A [i] может быть чем угодно.
Или с точки зрения наборов вместо массивов:
Сохраните N наборов (каждый с C возможными элементами) в структуре данных, чтобы вы могли быстро найти, является ли данный набор надмножеством любого из сохраненных наборов.
Создание структуры данных может занять как можно больше времени, но поиск должен быть максимально эффективным, и структура данных не должна занимать слишком много места.
Некоторый контекстЯ думаю, что это интересная проблема сама по себе, но для вещи, которую я действительно пытаюсь решить, вы можете предположить следующее:
N = 10000C = 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, и посмотрю, какая из двух сработает лучше всего.
Но тем временем эта проблема не возникает чаще? У него нет имени? Разве не было предыдущего исследования? Такое ощущение, что я заново изобретаю колесо.