Algoritmo para generar anagtwigs

Cuál sería la mejor estrategia para generar anagtwigs.

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; ex. 
  • Once más dos es un anagtwig de Doce más uno
  • Un punto decimal es un anagtwig de Soy un punto en su lugar
  • Los astrónomos son anagtwigs de los observadores de la Luna

Al principio, parece sencillo, simplemente revolver las letras y generar todas las combinaciones posibles. Pero, ¿cuál sería el enfoque eficiente para generar solo las palabras en el diccionario?

Encontré esta página, Resolviendo anagtwigs en Ruby .

Pero, ¿cuáles son tus ideas?

La mayoría de estas respuestas son terriblemente ineficientes y / o solo darán soluciones de una palabra (sin espacios). Mi solución manejará cualquier número de palabras y es muy eficiente.

Lo que quieres es una estructura de datos trie. Aquí hay una implementación completa de Python. Solo necesita una lista de palabras guardada en un archivo llamado words.txt . Puede probar la lista de palabras del diccionario de Scrabble aquí:

http://www.isc.ro/lists/twl06.zip

 MIN_WORD_SIZE = 4 # min size of a word in the output class Node(object): def __init__(self, letter='', final=False, depth=0): self.letter = letter self.final = final self.depth = depth self.children = {} def add(self, letters): node = self for index, letter in enumerate(letters): if letter not in node.children: node.children[letter] = Node(letter, index==len(letters)-1, index+1) node = node.children[letter] def anagram(self, letters): tiles = {} for letter in letters: tiles[letter] = tiles.get(letter, 0) + 1 min_length = len(letters) return self._anagram(tiles, [], self, min_length) def _anagram(self, tiles, path, root, min_length): if self.final and self.depth >= MIN_WORD_SIZE: word = ''.join(path) length = len(word.replace(' ', '')) if length >= min_length: yield word path.append(' ') for word in root._anagram(tiles, path, root, min_length): yield word path.pop() for letter, node in self.children.iteritems(): count = tiles.get(letter, 0) if count == 0: continue tiles[letter] = count - 1 path.append(letter) for word in node._anagram(tiles, path, root, min_length): yield word path.pop() tiles[letter] = count def load_dictionary(path): result = Node() for line in open(path, 'r'): word = line.strip().lower() result.add(word) return result def main(): print 'Loading word list.' words = load_dictionary('words.txt') while True: letters = raw_input('Enter letters: ') letters = letters.lower() letters = letters.replace(' ', '') if not letters: break count = 0 for word in words.anagram(letters): print word count += 1 print '%d results.' % count if __name__ == '__main__': main() 

Cuando ejecuta el progtwig, las palabras se cargan en un trie en la memoria. Después de eso, simplemente escriba las letras con las que desea buscar e imprimirá los resultados. Solo mostrará los resultados que usan todas las letras de entrada, nada más corto.

Filtra palabras cortas de la salida, de lo contrario, la cantidad de resultados es enorme. Siéntase libre de modificar la configuración MIN_WORD_SIZE . Tenga en cuenta que solo usa “astrónomos” ya que la entrada da 233,549 resultados si MIN_WORD_SIZE es 1. Quizás pueda encontrar una lista de palabras más corta que solo contenga palabras en inglés más comunes.

Además, la contracción “Yo soy” (de uno de sus ejemplos) no se mostrará en los resultados a menos que agregue “im” al diccionario y establezca MIN_WORD_SIZE en 2.

El truco para obtener varias palabras es volver al nodo raíz en el trie siempre que encuentre una palabra completa en la búsqueda. Luego sigues atravesando el trie hasta que se hayan utilizado todas las letras.

Para cada palabra en el diccionario, ordena las letras alfabéticamente. Entonces “foobar” se convierte en “abfoor”.

Luego, cuando ingrese el anagtwig de entrada, ordene sus letras también, luego búsquelo. ¡Es tan rápido como una búsqueda de hashtable!

Para palabras múltiples, puede hacer combinaciones de letras ordenadas, ordenando sobre la marcha. Aún mucho más rápido que generar todas las combinaciones.

(ver comentarios para más optimizaciones y detalles)

Vea esta tarea del departamento de CSE de la Universidad de Washington.

Básicamente, tienes una estructura de datos que solo tiene los recuentos de cada letra en una palabra (una matriz funciona para ascii, actualiza a un mapa si quieres compatibilidad con Unicode). Puedes restar dos de estos conjuntos de letras; si un recuento es negativo, usted sabe que una palabra no puede ser un anagtwig de otra.

Preproceso:

Construya un trie con cada hoja como una palabra conocida, en orden alfabético.

En el tiempo de búsqueda:

Considere la cadena de entrada como un conjunto múltiple. Encuentre la primera palabra secundaria atravesando el índice trie como en una búsqueda en profundidad. En cada sucursal puede preguntar: ¿está la letra x en el rest de mi entrada? Si tiene una buena representación de múltiples conjuntos, esta debería ser una consulta de tiempo constante (básicamente).

Una vez que tenga la primera palabra secundaria, puede mantener el rest en forma múltiple y tratarlo como una nueva entrada para encontrar el rest de ese anagtwig (si existe).

Aumente este procedimiento con memoialización para consultas más rápidas en multiempaturas de rest común.

Esto es bastante rápido: cada trie transversal está garantizado para dar una subpalabra real, y cada recorrido toma un tiempo lineal en la longitud de la subpalabra (y las subwords generalmente son bastante pequeñas, según los estándares de encoding). Sin embargo, si realmente quieres algo aún más rápido, podrías incluir todos los n-grams en tu proceso previo, donde un n-gram es cualquier cadena de n palabras seguidas. Por supuesto, si W = #words, pasará del tamaño de índice O (W) a O (W ^ n). Quizás n = 2 es realista, dependiendo del tamaño de tu diccionario.

Uno de los trabajos fundamentales sobre anagtwigs programáticos fue realizado por Michael Morton (Sr. Machine Tool), utilizando una herramienta llamada Ars Magna. Aquí hay un artículo ligero basado en su trabajo.

Así que aquí está la solución de trabajo, en Java, que Jason Cohen sugirió y funciona un poco mejor que la que usa trie. A continuación se encuentran algunos de los puntos principales:

  • Solo cargue el diccionario con las palabras que son subconjuntos del conjunto de palabras dado
  • El diccionario será un hash de palabras ordenadas como clave y un conjunto de palabras reales como valores (como lo sugirió Jason)
  • Itere a través de cada palabra de la clave del diccionario y realice una búsqueda recursiva hacia adelante para ver si se encuentra un anagtwig válido para esa clave
  • Solo haga la búsqueda directa porque ya se han encontrado anagtwigs para todas las palabras que ya han sido atravesadas.
  • Fusiona todas las palabras asociadas a las teclas para, por ejemplo, si ‘alista’ es la palabra para la cual se encuentran los anagtwigs y uno de los conjuntos para fusionar es [ins] y [elt], y las palabras reales para la tecla [ins ] es [sin] y [ins], y para la clave [elt] es [let], entonces el conjunto final de palabras de fusión sería [sin, let] y [ins, let], que formarán parte de nuestra lista final de anagtwigs
  • Además, para tener en cuenta que, esta lógica solo mostrará un conjunto único de palabras, es decir, “once más dos” y “dos más once” serían iguales y solo uno de ellos se enumeraría en la salida

A continuación se muestra el código recursivo principal que encuentra el conjunto de claves de anagtwig:

 // recursive function to find all the anagrams for charInventory characters // starting with the word at dictionaryIndex in dictionary keyList private Set> findAnagrams(int dictionaryIndex, char[] charInventory, List keyList) { // terminating condition if no words are found if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) { return null; } String searchWord = keyList.get(dictionaryIndex); char[] searchWordChars = searchWord.toCharArray(); // this is where you find the anagrams for whole word if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) { Set> anagramsSet = new HashSet>(); Set anagramSet = new HashSet(); anagramSet.add(searchWord); anagramsSet.add(anagramSet); return anagramsSet; } // this is where you find the anagrams with multiple words if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) { // update charInventory by removing the characters of the search // word as it is subset of characters for the anagram search word char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars); if (newCharInventory.length >= minWordSize) { Set> anagramsSet = new HashSet>(); for (int index = dictionaryIndex + 1; index < keyList.size(); index++) { Set> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList); if (searchWordAnagramsKeysSet != null) { Set> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet); anagramsSet.addAll(mergedSets); } } return anagramsSet.isEmpty() ? null : anagramsSet; } } // no anagrams found for current word return null; } 

Puede bifurcar el repository desde aquí y jugar con él. Hay muchas optimizaciones que podría haber perdido. Pero el código funciona y encuentra todos los anagtwigs.

Y aquí está mi solución novedosa.

El libro de Jon Bentley Programming Pearls contiene un problema para encontrar anagtwigs de palabras. La statement:

Dado un diccionario de palabras en inglés, encuentre todos los conjuntos de anagtwigs. Por ejemplo, “pots”, “stop” y “tops” son todos anagtwigs el uno del otro porque cada uno se puede formar permutando las letras de los demás.

Pensé un poco y se me ocurrió que la solución sería obtener la firma de la palabra que está buscando y compararla con todas las palabras del diccionario. Todos los anagtwigs de una palabra deben tener la misma firma. Pero, ¿cómo lograr esto? Mi idea era usar el teorema fundamental de la aritmética:

El teorema fundamental de la aritmética establece que

cada entero positivo (excepto el número 1) se puede representar exactamente en una dirección aparte de la reorganización como producto de uno o más números primos

Entonces, la idea es usar una matriz de los primeros 26 números primos. Luego, para cada letra de la palabra obtenemos el número primo correspondiente A = 2, B = 3, C = 5, D = 7 … y luego calculamos el producto de nuestra palabra de entrada. A continuación hacemos esto para cada palabra en el diccionario y si una palabra coincide con nuestra palabra de entrada, la agregamos a la lista resultante.

El rendimiento es más o menos aceptable. Para un diccionario de 479828 palabras, se necesitan 160 ms para obtener todos los anagtwigs. Esto es aproximadamente 0,0003 ms / palabra, o 0.3 microsegundo / palabra. La complejidad del algoritmo parece ser O (mn) o ~ O (m) donde m es el tamaño del diccionario yn es la longitud de la palabra de entrada.

Aquí está el código:

 package com.vvirlan; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Date; import java.util.List; import java.util.Scanner; public class Words { private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 }; public static void main(String[] args) { Scanner s = new Scanner(System.in); String word = "hello"; System.out.println("Please type a word:"); if (s.hasNext()) { word = s.next(); } Words w = new Words(); w.start(word); } private void start(String word) { measureTime(); char[] letters = word.toUpperCase().toCharArray(); long searchProduct = calculateProduct(letters); System.out.println(searchProduct); try { findByProduct(searchProduct); } catch (Exception e) { e.printStackTrace(); } measureTime(); System.out.println(matchingWords); System.out.println("Total time: " + time); } private List matchingWords = new ArrayList<>(); private void findByProduct(long searchProduct) throws IOException { File f = new File("/usr/share/dict/words"); FileReader fr = new FileReader(f); BufferedReader br = new BufferedReader(fr); String line = null; while ((line = br.readLine()) != null) { char[] letters = line.toUpperCase().toCharArray(); long p = calculateProduct(letters); if (p == -1) { continue; } if (p == searchProduct) { matchingWords.add(line); } } br.close(); } private long calculateProduct(char[] letters) { long result = 1L; for (char c : letters) { if (c < 65) { return -1; } int pos = c - 65; result *= PRIMES[pos]; } return result; } private long time = 0L; private void measureTime() { long t = new Date().getTime(); if (time == 0L) { time = t; } else { time = t - time; } } } 

El libro Programming Pearls de Jon Bentley cubre este tipo de cosas bastante bien. Una lectura obligada.

Cómo lo veo:

querrías construir una tabla que mapee conjuntos de letras desordenadas para enumerar palabras, es decir, pasar por el diccionario para que termines con, digamos

 lettermap[set(a,e,d,f)] = { "deaf", "fade" } 

luego, a partir de tu palabra de inicio, encuentras el conjunto de letras:

  astronomers => (a,e,m,n,o,o,r,r,s,s,t) 

luego recorra todas las particiones de ese conjunto (esta podría ser la parte más técnica, generando todas las particiones posibles) y busque las palabras para ese conjunto de letras.

editar: hmmm, esto es más o menos lo que Jason Cohen publicó.

editar: además, los comentarios sobre la pregunta mencionan la generación de anagtwigs “buenos”, como los ejemplos :). después de que construyas tu lista de todos los anagtwigs posibles, ejecútalos a través de WordNet y encuentra los que están semánticamente cerca de la frase original 🙂

He usado la siguiente forma de calcular anagtwigs hace un par de meses:

  • Calcule un “código” para cada palabra en su diccionario: cree una tabla de búsqueda a partir de letras en el alfabeto para números primos, por ejemplo, comenzando con [‘a’, 2] y terminando con [‘z’, 101]. Como paso de procesamiento previo, calcule el código de cada palabra en su diccionario buscando el número primo para cada letra en el que consiste en la tabla de búsqueda y multiplíquelas juntas. Para una búsqueda posterior crea una multimapa de códigos para palabras.

  • Calcule el código de su palabra de entrada como se describe arriba.

  • Compute codeInDictionary% inputCode para cada código en el multimap. Si el resultado es 0, ha encontrado un anagtwig y puede buscar la palabra adecuada. Esto también funciona para anagtwigs de 2 o más palabras.

Espero que haya sido útil.

Hace un tiempo escribí una publicación en un blog sobre cómo encontrar rápidamente dos anagtwigs de palabras. Funciona muy rápido: encontrar los 44 anagtwigs de dos palabras para una palabra con un archivo de texto de más de 300,000 palabras (4 Megabytes) toma solo 0.6 segundos en un progtwig de Ruby.

Algoritmo del Buscador de Anagtwigs de Dos Palabras (en Ruby)

Es posible hacer que la aplicación sea más rápida cuando se permite preprocesar la lista de palabras en una gran asignación de hash, desde palabras ordenadas por letras a una lista de palabras que utilizan estas letras. Estos datos preprocesados ​​se pueden serializar y usar a partir de ese momento.

Si tomo un diccionario como un Hash Map ya que cada palabra es única y la clave es una representación binaria (o hexadecimal) de la palabra. Entonces, si tengo una palabra, puedo encontrar fácilmente el significado con O (1) complejidad.

Ahora, si tenemos que generar todos los anagtwigs válidos, necesitamos verificar si el anagtwig generado está en el diccionario, si está presente en el diccionario, es válido, de lo contrario debemos ignorarlo.

Asumiré que puede haber una palabra de un máximo de 100 caracteres (o más, pero hay un límite).

Entonces, cualquier palabra que tomemos como una secuencia de índices como una palabra “hola” puede representarse como “1234”. Ahora los anagtwigs de “1234” son “1243”, “1242” ..etc

Lo único que debemos hacer es almacenar todas esas combinaciones de índices para un número particular de caracteres. Esta es una tarea de una sola vez. Y luego se pueden generar palabras a partir de las combinaciones eligiendo los caracteres del índice. Por lo tanto, obtenemos los anagtwigs.

Para verificar si los anagtwigs son válidos o no, simplemente indexe en el diccionario y valide.

Lo único que se debe manejar son los duplicados. Esto se puede hacer fácilmente. Como cuando necesitamos comparar con los anteriores que se han buscado en el diccionario.

La solución enfatiza en el rendimiento.

Por fuera de mi cabeza, la solución que tiene más sentido sería elegir una letra de la cadena de entrada de forma aleatoria y filtrar el diccionario en función de las palabras que comienzan con eso. Luego seleccione otro, filtre en la segunda letra, etc. Además, filtre las palabras que no se pueden hacer con el texto restante. Luego, cuando tocas el final de una palabra, inserta un espacio y comienza con las letras restantes. También puede restringir las palabras según el tipo de palabra (por ejemplo, no tendría dos verbos al lado del otro, no tendría dos artículos al lado del otro, etc.).

  1. Como Jason sugirió, prepare un diccionario haciendo hashtable con la palabra clave ordenada alfabéticamente, y la palabra de valor en sí (puede tener múltiples valores por tecla).
  2. Elimine los espacios en blanco y ordene su consulta antes de buscarla.

Después de esto, necesitarías hacer una especie de búsqueda recursiva y exhaustiva. El pseudo código es muy aproximado:

 function FindWords(solutionList, wordsSoFar, sortedQuery) // base case if sortedQuery is empty solutionList.Add(wordsSoFar) return // recursive case // InitialStrings("abc") is {"a","ab","abc"} foreach initialStr in InitalStrings(sortedQuery) // Remaining letters after initialStr sortedQueryRec := sortedQuery.Substring(initialStr.Length) words := words matching initialStr in the dictionary // Note that sometimes words list will be empty foreach word in words // Append should return a new list, not change wordSoFar wordsSoFarRec := Append(wordSoFar, word) FindWords(solutionList, wordSoFarRec, sortedQueryRec) 

Al final, necesita iterar a través de la lista de soluciones e imprimir las palabras en cada sublista con espacios entre ellas. Es posible que deba imprimir todos los pedidos para estos casos (por ejemplo, “Yo soy Sam” y “Sam soy” son ambas soluciones).

Por supuesto, no probé esto, y es un enfoque de fuerza bruta.