¿Qué algoritmos y estructuras de datos se pueden usar para encontrar anagramas?

Creo que el método de tabla hash es el mejor método para encontrar todos los anagramas directos de una palabra específica. Sin embargo, si desea encontrar todos los “subanagramas” de una palabra (palabras que usan algunas de las letras de la palabra), podría haber una mejor manera. No estoy seguro de si es mejor, pero ciertamente es bastante bonito.

La solución está en usar un árbol de recuperación de prefijos, o trie ( http://en.wikipedia.org/wiki/Trie ). Si te sientes realmente ambicioso, puedes usar un DAWG que es un trie más eficiente en memoria ( http://en.wikipedia.org/wiki/Dir …).

Un trie funciona de la siguiente manera. Cada nodo en el trie representa un prefijo, el nodo raíz representa el prefijo vacío. De cada nodo hay hasta 27 nodos secundarios. El borde del nodo secundario representa la letra que se utiliza para llegar a ese nodo. El borde 27 puede conducir a un nodo de final de palabra, lo que indica que el prefijo representado por el nodo es una palabra distinta. Usando esta estructura, puede implementar el siguiente algoritmo (dado en pseudocódigo):

  // Entradas:
 // prefijo: el prefijo que se está creando
 // letras: las letras restantes que se pueden usar en la palabra
 // anagramas - el conjunto de sub anagramas
 // dawgRoot: el nodo actual del DAWG para buscar
 getSubAnagrams (prefijo, letras, anagramas, dawgRoot):
     si dawgRoot es el fin de la palabra:
         anagrams.add (prefijo)

     para índice en 0 a tamaño (letras):
         if index! = 0 y letras [index] == letras [index - 1]:
             continuar

         if dawgRoot.hasChild (letras [índice]):
             getSubAnagrams (prefijo + letras [índice],
                 letras [0: índice] + letras [índice + 1: fin],
                 anagramas,
                 dawgRoot.getChild (letras [índice]))

Además del método de hash señalado por Leo Polovets, puede resolver esto usando Tries . Ver: Trie

Digamos que tiene todas las palabras del diccionario guardadas en forma de una serie de cadenas. Lo que esencialmente necesita hacer es atravesar la matriz e insertar la forma ordenada de la palabra en el Trie. Entonces, por ejemplo, la palabra es “verde azulado”, insertará “aelt” en el Trie. El Trie está diseñado de manera que cada nodo sea capaz de almacenar una lista vinculada. Y, para cada ruta (versión ordenada de cualquier palabra), este es esencialmente el último vértice de esa ruta. En el ejemplo, la ‘t’ en “aelt” contiene una lista vinculada que almacena los índices (índice de esa palabra en particular en la matriz) de “verde azulado”, “cuento”, “tarde”.

Ahora, cuando se le da cualquier palabra, ordena la palabra y recorre el Trie de acuerdo con la versión ordenada de la palabra. El último nodo le dará una lista vinculada que tiene los índices de todos sus anagramas que están en el diccionario.

Complejidad:
Digamos que tienes m palabras con una longitud promedio n.
Ordenar una palabra sería [math] O (nlgn) [/ math]. Y la inserción en el Trie toma [matemáticas] O (n) [/ matemáticas]. La inserción del índice en la lista vinculada tomaría [math] O (m) [/ math]. Entonces, la complejidad total para insertar una palabra sería [matemática] O (nlgn + n + m) [/ matemática] es decir [matemática] O (nlgn + m) [/ matemática]. Y para m palabras, esto sería [matemáticas] O (mnlgn + m ^ 2) [/ matemáticas].

Similar a lo que Leo sugirió, podría usar una tabla hash. El valor al que se asigna una cadena depende de la frecuencia de aparición de cada letra y es independiente de sus posiciones.

Ahora, puede almacenar todas las palabras en la tabla hash de antemano. Al obtener una palabra de consulta, simplemente necesita encontrar su asignación y verificar las palabras almacenadas en la entrada de la tabla correspondiente.

Puede haber un enfoque: generar un código hash único de una palabra que sea igual para todo su anagrama. Entonces puedes decir fácilmente 2 palabras como anagrama simplemente equiparándolas. Aquí se centraría más en generar un código hash único de un conjunto de caracteres.

Su mejor apuesta es un Gaddag, sobre el que puede leer más aquí:

Estructura de datos de Gaddag