Быстрая проверка, является ли набор надмножеством сохраненных наборов

Question

проблема

Мне дано N массивов C логических значений. Я хочу организовать их в структуру данных, которая позволит мне выполнить следующую операцию как можно быстрее: для нового массива вернуть true, если этот массив является «надмножеством» любого из сохраненных массивов. Под надмножеством я имею в виду следующее: A является надмножеством B, если A [i] истинно для каждого i, где B [i] истинно. Если B [i] ложно, то A [i] может быть чем угодно.

Или в терминах наборов вместо массивов:

Храните N наборов (каждый с C возможными элементами) в структуре данных, чтобы вы могли быстро найти, является ли данный набор надмножеством любого из сохраненных наборов.

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

Некоторый контекст

Я думаю, что это интересная проблема сама по себе, но для вещи, которую я действительно пытаюсь решить, вы можете предположить следующее:

• N = 10000
• C = 1000
• Хранимых массивов мало
• Найденные массивы являются случайными (поэтому не редкими)

Что я придумала до сих пор

1. Для поиска O (NC) : Просто выполнить итерацию всех массивов. Хотя это слишком медленно.

2. Для поиска 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, и посмотрю, какая из двух сработает лучше.

Но тем временем эта проблема не возникает чаще? У него нет имени? Разве не было предыдущего исследования? Такое ощущение, что я заново изобретаю колесо.

Answer 1

Просто чтобы добавить некоторую справочную информацию к решению префикс , недавно я нашел следующую статью:

I.Savnik: Структура данных индекса для быстрых запросов подмножеств и подмножеств. CD-ARES, IFIP LNCS, 2013.

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

Для любых пользователей python , заинтересованных в реальной реализации, я пришелс пакетом python3, основанным частично на вышеупомянутой статье.Он содержит основанный на tree контейнер наборов, а также контейнер сопоставления, в котором установлены ключи.Вы можете найти его на github .

Answer 2

Я думаю, префикс trie - отличное начало.

Поскольку ваши массивы редки, я бы дополнительно протестировал их оптом.Если (B1 ∪ B2) ⊂ A, оба включены.Таким образом, идея состоит в том, чтобы упаковать массивы по парам и повторять до тех пор, пока не будет только один «корневой» массив (это займет всего вдвое больше места).Это позволяет ответить «Да» на ваш вопрос ранее, что в основном полезно , если вам не нужно знать, что массив фактически содержится .

Независимо, вы можете подать заявку на каждый массивхеш-функция, сохраняющая порядок.

Т.е.: B ⊂ A ⇒ h(B) ≺ h(A)

OR-биты вместе - это такая функция, но вы также можете считать каждый 1-бит в соответствующих разделах массива.Здесь вы можете быстрее исключать кандидатов (отвечая «Нет» для определенного массива).

Answer 3

Вы можете упростить задачу, сначала сократив список наборов до «минимальных» наборов: оставьте только те наборы, которые не являются надмножествами других.Проблема остается той же, потому что если некоторый входной набор A является надмножеством некоторого набора B, который вы удалили, то он также является надмножеством хотя бы одного "минимального" подмножества C из B, которое не было удалено,Преимущество этого состоит в том, что вы склонны устранять большие наборы, что делает проблему менее дорогой.

Оттуда я бы использовал какой-нибудь алгоритм ID3 или C4.5 .