Структура данных для запроса того, существует ли данное подмножество в наборе множеств

Ответ 1

Это напоминает мне мутированный префикс tree/trie, который я сделал один раз. Немного отличается, но это может сработать. Он может не работать, если у вас большие/нет ограничений или если вы не можете преобразовать его на свой язык (код на С++).

Итак, в принципе, вы обычно храните детей, соответствующих следующей букве, но я сделал, что я хранил детей, соответствующих частоте каждой буквы.

В основном вопрос (с моей точки зрения) заключается в следующем: "Существуют ли какие-либо множества, которые имеют одну или более букв, чем в подмножестве?" Например, если подмножество {A, D, E, E}, то вам нужно найти, есть ли набор с хотя бы одним A, одним D и двумя E.

Итак, для trie у вас есть что-то вроде этого

            Root
           / | \
          / /|\ \
         / / | \ \
        1 2  ... MAX <-- This represents the frequency of "A"
       /|\ ..... /|\
      1..MAX    1..MAX <-- Frequency of "B"
      ...............
      ...............
      ...............
     1 ... ... ... MAX <-- Frequency of "Y"
    /|\ .... .... / | \
   1..MAX ...... 1 .. MAX <-- Frequency of "Z"

В основном все... представляют множество вещей, которые слишком долго будут отображаться. /, | и\представляют дочерние отношения родителей, а MAX представляют максимальную частоту буквы

Итак, что вы делаете, есть у вас структура (код я в С++) вроде:

struct NODE {
    NODE *child[MAX + 1]; // Pointers to other NODE that represents
                          // the frequency of the next letter
};

При создании node вам нужно инициализировать все его дочерние элементы до NULL. Вы можете сделать это через конструктор (в С++) или функцию makeNode(), например

NODE* makeNode() {
    NODE* n = new NODE;         // Create a NODE
    for(int i = 0;i <= MAX;i++) // For each child
        n->child[i] = NULL;     // Initialize to NULL
};

В начале, trie - это просто корень

NODE* root = new NODE;

Когда вы добавляете набор в trie, вы получаете частоту каждой буквы и проходите через trie. Если в определенном node дочерний элемент, соответствующий следующей букве, равен NULL, вы просто создаете новый NODE.

Когда вы выполняете поиск в trie, вы выполняете поиск всех дочерних элементов каждого node, который соответствует частоте буквы в подмножестве или больше. Например, если подмножество имеет 3 A, вы выполняете поиск по всему корню- > дочернему [3], затем root- > child [4], затем... затем root- > child [MAX].

Это, вероятно, слишком сложно и запутанно, так что 1) Если вы думаете, что я не сумасшедший, пожалуйста, прокомментируйте, что сбивает с толку, и 2) Вы можете/возможно хотите просто найти более простой метод

Ответ 2

Похоже, вы можете попробовать использовать KD-Trees или вариант.

Связанная тема для изучения будет многомерным поиском/запросом диапазона.

Предостережение: я не использовал их сам, но надеюсь, что вы сможете найти что-то полезное, прочитав некоторую литературу по вышеуказанной теме.

Надеюсь, что это поможет.

Ответ 3

Вероятно, вы можете использовать trie и вставить каждый набор в trie, пройдя через итерационно, используя целевое подмножество, чтобы узнать, есть ли у вас соответствующее подмножество. По крайней мере, как я думаю, что я это сделаю.

"trie" фактически был задуман для структуры данных reTRIEvable и почти похож на обычное дерево, но имеет узлы с различными перестановками, например:

     A
    / \
   AT AN
     / | \
    |  |  AND
   ANN ANY
    |
  ANNA

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

Найдите здесь