La mejor estructura de datos para la búsqueda de crucigramas

Question

Tengo una gran base de datos para resolver crucigramas, que consisten en una palabra y una descripción. Mi aplicación permite buscar palabras de una longitud y caracteres específicos en posiciones específicas (esto se hace de la manera difícil ... revise todas las palabras y verifique cada una). Más una búsqueda por descripción (si es necesario)

Por ejemplo, busque palabra _ _ a _ _ b (palabra de 6 letras, tercer carácter a y último b)

Me gustaría indexar las palabras de tal manera que la búsqueda sería realmente rápida. Mi primera idea fue usar una estructura de árbol equilibrada, ¿alguna otra sugerencia?

Answer 1

Bien, voy a proponer algo extraño, pero venga de C++ he estado usando Boost durante mucho tiempo y he venido a ver el MultiIndex biblioteca.

La idea de esta biblioteca es crear una colección, pero tener muchas formas diferentes de consultarla. Podría modelar, de hecho, una base de datos.

Entonces, pongamos nuestras palabras en una tabla y pongamos los índices necesarios en su lugar:

word                     |length|c0|c1|c2| ... |c26|
-------------------------|------|--|--|--| ... |---|
Singapour                |9     |S |i |n | ... |0  |

Ahora la consulta se verá como:

Select word From table Where length=9 And c2='n' And c8='u';

¿Es bastante fácil?

Para la máxima eficiencia, la tabla debe dividirse en la longitud, y los índices (uno por columna CX) deben ser locales para la partición.

Para una solución en memoria, tendría un contenedor por longitud, que contiene tantos índices como la longitud, cada índice es una tabla hash que apunta a una lista ordenada (fusión más fácil)

Aquí hay una descripción de Python:

class Dictionary:
  def __init__(self, length):
    self.length = length
    self.words = set([])
    self.indexes = collections.defaultdict(set)

  def add(self, word):
    if len(word) != self.length:
      raise RuntimeException(word + ' is not ' + `self.length` + ' characters long')

    if word in self.words:
      raise RuntimeException(word + ' is already in the dictionary')

    self.words.add(word)

    for i in range(0,length):
      self.indexes[(i,word[i])].add(word)

  def search(self, list):
    """list: list of tuples (position,character)
    """
    def compare(lhs,rhs): return cmp(len(lhs),len(rhs))

    sets = [self.indexes[elem] for elem in list]
    sets.sort(compare)
    return reduce(intersection, sets)

He proporcionado voluntariamente el length argumento, para minimizar el tamaño de los hashes y, por lo tanto, mejorar la búsqueda. Además, los conjuntos se clasifican por longitud para que el cálculo de la intersección sea mejor :)

Sigue adelante y pruébelo con otras soluciones si lo desea :)

Answer 2

Esta pregunta: ¿Buen algoritmo y estructura de datos para buscar palabras con letras faltantes? Comenzó exactamente como el que está preguntando, pero luego fue editado a algo bastante diferente y más fácil. Aún así, puedes encontrar algunas ideas allí.

En resumen, todos recomiendan cargar todo el diccionario en la memoria y dividir las palabras en grupos en función de su longitud. A partir de ahí, puedes seguir muchas direcciones diferentes. Cuanta más memoria esté dispuesta a usar, más rápido podrá ir.

Una buena sugerencia es mantener una tabla hash de listas de palabras de una longitud dada que tienen una letra dada en una posición determinada. Puedes construirlo así (en Python):

# Build a whole lot of sorted word lists
wordlists = collections.defaultdict(list)
for word in sorted(all_words):
    for position, letter in enumerate(word):
        wordlists[len(word), position, letter].append(word)

Ahora, si necesita una palabra de 6 letras que termina en B, puede pedir wordlists[6, 5, 'B'] Y tienes la lista completa. Cuando sabes más de una carta, como en ..A..B, puede elegir la lista más corta y probar cada palabra contra el patrón deseado. El diccionario de mi computadora solo tiene 21 palabras de seis letras que terminan con B, de las cuales solo los escarabajos coinciden.

Answer 3

Como usa una base de datos, cree una tabla de sufijos.
Por ejemplo :

  Suffix          |   WordID   | SN
  ----------------+------------+----   
  StackOverflow           10      1
  tackOverflow            10      2
  ackOverflow             10      3
  ckOverflow              10      4
  kOverflow               10      5
  ...

Con esa tabla es fácil obtener todas las palabras que contienen un char en particular en una posición específica,
como esto:

SELECT WordID FROM suffixes
WHERE suffix >= 't' AND suffix < 'u' AND SN = 2

Obtenga todas las palabras que contienen 't' en la posición 2.

Actualizar: Si desea ahorrar espacio y sacrificar un poco de velocidad, puede usar un matriz de sufijo.

Puedes almacenar todas las palabras en una línea (matriz) con un separador entre ellas, es decir, el $, y crear una matriz de sufijo que tendrá punteros a los caracteres. Ahora, dado un carbón c Puede encontrar todas las instancias de palabras que lo contienen bastante rápido. Aún así, tendrá que examinar si está en la posición correcta.
(revisando qué tan lejos está del $s)

Probablemente con lo anterior técnica La búsqueda será X10 más rápida que buscar todas las palabras en su programa original.

Actualización 2: He usado el enfoque de la base de datos en una de mis utilidades donde necesitaba localizar sufijos como "NE", por ejemplo, y olvidé ajustarlo (optimizarlo) para este problema específico.

Puedes almacenar un solo char como sufijo:

  Suffix   |   WordID   | SN
  ---------+------------+----   
  S                10      1
  t                10      2
  a                10      3
  c                10      4
  k                10      5
  ...

que ahorra mucho espacio. Ahora, la consulta se convierte en

SELECT WordID FROM suffixes
WHERE suffix = 't' AND SN = 2

Answer 4

Puedes usar un Árbol sufijo, o un trie.

Answer 5

Podría almacenar su información en un trie de algún tipo (tal vez un árbol de búsqueda ternario). En la sección 6 de la búsqueda parcial se describe un algoritmo para la búsqueda parcial utilizando un trie este papel por Sedgewick y Bentley. Por supuesto, usted quiere tener diferentes intentos por las diversas palabras. El documento dice que el algoritmo de búsqueda parcial requiere un tiempo de o (n^((ks)/k)) para que las letras se especifiquen en un trie de palabras n k.