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

Проблема

Мне даны 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), которое не требует экспоненциального объема пространства.

EDIT: новая идея, которую я придумал

  • Для поиска O (sqrt (N) C): Храните массивы в качестве префикса . При поиске массива A перейдите к соответствующему поддереву, если A [i] = 0, но посетите оба поддеревья, если A [i] = 1.

    Моя интуиция подсказывает мне, что это должно сделать (среднюю) сложность поиска O (sqrt (N) C), если вы считаете, что сохраненные массивы случайны. Но: 1. Это не так, массивы редки. И 2. это только интуиция, я не могу это доказать.

Я попробую и эту новую идею, и метод BDD, и посмотрю, какая из двух из них лучше всего подходит.

Но пока эта проблема чаще возникает? Разве это не имя? Не было ли ранее проведенных исследований? Мне действительно кажется, что я изобретаю колесо здесь.

Ответы

Ответ 1

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

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

В документе предлагается структура данных (контейнер) set-trie, которая обеспечивает поддержку эффективного хранения и запросов наборов множеств с использованием структуры trie data​​strong > , поддерживая операции, такие как поиск всех надмножеств/подмножеств заданное множество из набора множеств.

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

Ответ 2

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

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

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

Ie: B ⊂ A ⇒ h(B) ≺ h(A)

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

Ответ 3

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

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