Estructura de datos para consultar si existe un subconjunto dado en una colección de conjuntos

Question

Estoy intentando construir una estructura de datos para un solucionador de juegos de palabras.

Necesito almacenar alrededor de 150,000 juegos de la forma {A, A, D, E, I, L, P, T, V, Y}. (Son palabras en inglés normalizados, es decir, caracteres ordenados Tenga en cuenta que este es un conjunto múltiple que puede contener la misma letra dos veces..)

necesita para obtener de manera eficiente un sí/no hay respuesta a los siguientes tipos de consulta: ¿hay alguna establece con el subconjunto dado? Por ejemplo, ¿alguna de las palabras conocidas contiene el conjunto {D, E, I, L, L, P}?

Requisitos:

• Las consultas deben ser rápidos
• La estructura de datos debe caber en una cantidad razonable de espacio (por ejemplo < 50 MB)
• La estructura de datos no tiene por qué ser construyeron en bienes hora; está precalculado

¿Existe alguna estructura de datos que satisfaga esta necesidad? Esto es un poco diferente de las preguntas otherset matching en StackOverflow porque los conjuntos de objetivos son realmente multisectos.

Answer 1

Esto me recuerda a un prefijo mutado tree/trie que hice una vez. Ligeramente diferente, pero podría funcionar. Puede no funcionar si tiene límites grandes/sin límites o si no puede convertirlo a su idioma (código I en C++).

Así que, básicamente, en un trie usualmente almacena niños correspondientes a la siguiente letra, pero lo que hice fue almacenar niños correspondientes a la frecuencia de cada letra.

En esencia, la pregunta (desde mi punto de vista) es: "¿Hay juegos que tengan la misma o más letras que en el subconjunto?"Por ejemplo, si el subconjunto es {A, D, E, E}, entonces necesita encontrar si hay un conjunto con al menos una A, una D y dos E.

Entonces, para el trie que tiene algo como esto

  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" 

Básicamente toda la ... 's representan un montón de cosas que sería largo para mostrar la /, |. y \ representar relación padre-hijo y MAX representa la frecuencia máxima de una carta

Así que lo que haces, es que tiene una estructura (I código en C++) de algún tipo como:

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

Cuando crea un nodo, debe inicializar todos sus elementos secundarios a NULL. Usted puede hacer ya sea esto a través de un constructor (en C++) o una función makeNode() como

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 
}; 

Al comienzo, el trie es sólo una raíz

NODE* root = new NODE; 

Cuando se agrega un conjunto de la trie, obtienes la frecuencia de cada letra y pasas por el trie. Si en un nodo particular, el niño que corresponde a la siguiente letra es NULO, simplemente crea un nuevo NODO.

Cuando busca en el trie, busca todos los elementos secundarios de cada nodo que corresponda a la frecuencia de la letra en el subconjunto o superior. Por ejemplo, si el subconjunto tiene 3 A, busca todas las opciones root-> child [3] luego root-> child [4] luego ... luego root-> child [MAX].

Es probable que sea demasiado complicado y confuso por lo que 1) Si usted piensa que no estoy loca, por favor, comentar sobre lo que es confuso y 2) Es posible/probable que desee simplemente encontrar un método más simple

Answer 2

Probablemente pueda usar un trie e insertar cada conjunto en el trie, atravesando el trie de forma iterativa utilizando su subconjunto de destino para averiguar si tiene un subconjunto coincidente. Al menos así es como creo que lo haría.

El 'trie' fue en realidad concebida para una estructura de datos recuperables, y es muy parecido a un árbol normal, pero tiene nodos con diferentes permutaciones, por ejemplo:

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

En el ejemplo anterior, se puede vea que esto probablemente sea útil para su caso, ya que ANN y ANNA se pueden recuperar como un conjunto. Es posible que desee utilizar algún código de permutación, junto con este tipo de ADT (tipo de datos abstracto).

Encuentra más here

Answer 3

parece que se podría tratar de usar KD-Trees o una variante.

Un tema relacionado a explorar sería la búsqueda/consulta de rango multidimensional.

Advertencia: No las he usado, pero espero que pueda encontrar algo útil leyendo literatura sobre el tema anterior.

Espero que ayude.