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

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

10 голосов
/ 05 марта 2011

Я пытаюсь построить структуру данных для решателя словесных игр.

Мне нужно хранить около 150000 наборов в форме {A, A, D, E, I, L, P, T, V, Y}. (Это нормализованные английские слова, т.е. отсортированные символы. Обратите внимание, что это multiset , который может содержать одну и ту же букву дважды.)

Необходимо эффективно получить ответ «да / нет» на следующий вид запроса: есть ли наборы с данным подмножеством? Например, содержит ли какое-либо из известных слов множество {D, E, I, L, L, P}?

Требования:

  • Запросы должны быть быстрыми
  • Структура данных должна занимать достаточное количество места (например, <50 МБ) </li>
  • Структура данных не обязательно должна быть построена в реальном времени; это предварительно вычислено.

Существует ли какая-либо структура данных, которая бы хорошо соответствовала этой потребности? Это немного отличается от других подходящих наборов вопросов по StackOverflow тем, что целевые наборы на самом деле являются мультимножественными.

Ответы [ 3 ]

3 голосов
/ 05 марта 2011

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

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

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

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

            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"

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

Итак, что вы делаете, у вас есть структура (я кодирую на c ++), например: 

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

Когда вы создаете узел, вам нужно инициализировать все его дочерние элементы как NULL. Вы можете сделать это через конструктор (в c ++) или функцию 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
};

В начале дерево - это просто корень 

NODE* root = new NODE;

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

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

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

2 голосов
/ 05 марта 2011

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

Смежной темой для изучения будет поиск / запрос многомерного диапазона.Я сам этим не пользовался, но надеюсь, что вы сможете найти что-то полезное, прочитав литературу по этой теме.

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

0 голосов
/ 05 марта 2011

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

'Trie' на самом деле был задуман для структуры данных с возможностью повторного использования и во многом похож на обычное дерево, но имеет узлы с различными перестановками, например: 

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

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

Найти больше здесь

...