Encontrar palabras de letras al azar de entrada en Python. Lo algoritmo para usar / código ya existe?

Question

Estoy tratando de codificar una palabra decodificadora como éste aquí y se preguntaba qué algoritmos debería utilizar para implementar esto. Además, si alguien puede encontrar el código existente para este que sería grande también. Básicamente la funcionalidad va a ser como un solucionador de Boggle pero sin ser una matriz, simplemente buscar todos los posibilidades de palabras de una cadena de caracteres. Yo ya tengo los diccionarios adecuados.

Yo tenía la intención de hacerlo, ya sea en Python o Ruby. Gracias de antemano por su ayuda chicos!

Answer 1

que haría uso de un Trie . Aquí está una implementación en Python: http://jtauber.com/2005/02/trie.py (crédito a James Tauber)

Answer 2

Me puede faltar una comprensión del juego pero salvo algunas complicaciones en las normas, como por ejemplo con la introducción de "comodín" letras (comodín), desaparecidos o más letras, palabras múltiples, etc ... Creo que las siguientes ideas ayudaría a su vez el problema de una cosa un tanto relativamente poco interesante. : - (

términos de índice de la ordenaron secuencia de sus cartas .
   Por ejemplo, "ordenador" recibe introducido como "cemoprtu". Sean cuales sean los dibujos aleatorios proporcionan está clasificando en especie, y se utiliza como clave para encontrar posibles coincidencias.    Utilizando trie estructuras según lo sugerido por perimosocordiae, como el almacenamiento subyacente para estas teclas ordenados y palabras asociadas (s) / wordIds en los nodos "hoja", Word tiempo de búsqueda se puede hacer de o (n) , donde n es el número de letras (o mejor, en promedio debido a las palabras no existentes).

Para ayudar aún más con la indexación podemos tener varias tablas / diccionarios, uno por cada número de letras. También en función de las estadísticas de las vocales y las consonantes pueden ser manipulados por separado. Otro truco sería tener un orden personalizado, colocando las letras más selectivos en primer lugar.

giros adicionales para el juego (como la búsqueda de palabras hechas a partir de un subconjunto de las letras) es principalmente una cuestión de iteración de la conjunto potencia de estas cartas y comprobando el diccionario para cada combinación.

Unos heurísticas pueden ser introducidos para ayudar a podar algunas de las combinaciones (por ejemplo combinaciones sin vocales [y de una longitud dada] no son posibles soluciones etc. Uno debe gestionar estas heurísticas cuidadosamente para la costo de búsqueda es relativamente pequeño.

Answer 3

Para su índice de diccionario, construir un mapa (Mapa [Bolsa [Char], Lista [cadena]]). Debe ser un mapa hash para que pueda obtener O (1) palabra de búsqueda. Una bolsa [Char] es un identificador para una palabra que es único hasta el orden de los caracteres. Es es básicamente un mapa hash de char a int. El Char es un carácter determinado en la palabra y la int es el número de veces que el personaje aparece en la palabra.

Ejemplo:

{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]

Para encontrar las palabras, tomar todas las combinaciones de caracteres de la cadena de entrada y búsquelo en este mapa. La complejidad de este algoritmo es O (2 ^ n) en la longitud de la cadena de entrada. En particular, la complejidad no depende de la longitud del diccionario.

Answer 4

Esto suena como Rabin-Karp cadena de búsqueda sería una buena elección. Si se utiliza una función de troceado rodando después en cada posición que necesita una actualización del valor hash y una búsqueda de diccionario. También es necesario crear una buena manera de hacer frente a diferentes longitudes de palabra, al igual que todas las palabras truncar a la palabra más corta en el conjunto y volver a comprobar posibles coincidencias. La división de la palabra establecido en rangos de longitud separadas reducirá la cantidad de falsos positivos a expensas de aumentar el trabajo hashing.

Answer 5

Hay dos maneras de hacer esto. Una de ellas es para comprobar todas las permutaciones candidato de letras de la palabra para ver si el candidato está en su diccionario de palabras. Eso es un O (N!) Operación, dependiendo de la longitud de la palabra.

La otra forma es comprobar cada palabra candidato en el diccionario para ver si está contenida dentro de la palabra. Esto puede ser acelerado mediante la agregación del diccionario; en lugar de cada palabra candidato, que comprueba todas las palabras que son anagramas entre sí a la vez, ya que si uno de ellos está contenido en su palabra, todos ellos son.

Así que empieza por la construcción de un diccionario cuya clave es una cadena ordenada de letras y cuyo valor es una lista de las palabras que son anagramas de la tecla:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> with open(r"c:\temp\words.txt", "r") as f:
        for line in f.readlines():
            if line[0].isupper(): continue
            word = line.strip()
            key = "".join(sorted(word.lower()))
            d[key].append(word)

Ahora necesitamos una función para ver si una palabra contiene un candidato. Esta función supone que la palabra y el candidato se clasifican tanto, para que pueda pasar por ellos, tanto letra por letra y abandonar rápidamente cuando se encuentra que no coinciden.

>>> def contains(sorted_word, sorted_candidate):
        wchars = (c for c in sorted_word)
        for cc in sorted_candidate:
            while(True):
                try:
                    wc = wchars.next()
                except StopIteration:
                    return False
                if wc < cc: continue
                if wc == cc: break
                return False
        return True

Ahora encontrar todas las claves candidatas en el diccionario que están contenidos por la palabra, y agregar todos sus valores en una sola lista:

>>> w = sorted("mythopoetic")
>>> result = []
>>> for k in d.keys():
        if contains(w, k): result.extend(d[k])
>>> len(result)
429
>>> sorted(result)[:20]
['c', 'ce', 'cep', 'ceti', 'che', 'chetty', 'chi', 'chime', 'chip', 'chit', 'chitty', 'cho', 'chomp', 'choop', 'chop', 'chott', 'chyme', 'cipo', 'cit', 'cite']

Esto último paso toma alrededor de un cuarto de segundo en mi portátil; 195K hay llaves en mi diccionario (estoy utilizando el archivo de palabras BSD Unix).