Recherche de mots de lettres d'entrée aléatoires en python. Quel algorithme utiliser / code déjà là?

Question

Je suis en train de coder un mot décrypteur comme celui-ci et je me demandais quels algorithmes J'utiliser pour mettre en œuvre. Aussi, si quelqu'un peut trouver le code existant pour ce qui serait super aussi. Fondamentalement, la fonctionnalité va être comme un solveur Boggle mais sans être une matrice, juste la recherche de toutes les possibilités de mot d'une chaîne de caractères. Je n'ai déjà des dictionnaires adéquats.

Je comptais le faire soit en python ou le rubis. Merci d'avance pour votre aide les gars!

Answer 1

J'utiliser un Trie. Voici une implémentation en Python: http://jtauber.com/2005/02/trie.py (crédit à James Tauber)

Answer 2

Je peux comprendre manquerai du jeu, mais à l'exception des complications dans les règles, telles que l'introduction de lettres « joker » (joker), manquant ou lettres supplémentaires, plusieurs mots etc ... Je pense que les idées suivantes contribuerait à tourner le problème dans une chose un peu relativement inintéressant. : - (

L'idée principale mots d'index par ordonné séquence de leurs lettres .
   Par exemple, « ordinateur » obtient codé comme « cemoprtu ». Quels que soient les dessins au hasard fournissent trie en nature, et utilisé comme clé pour trouver des correspondances possibles.    En utilisant Trie structures comme le suggère perimosocordiae, que le stockage sous-jacent ces clés triées et des mots associés (s) / wordIds dans les noeuds « feuilles », Word recherche peut être effectuée de temps en O (n) , où n est le nombre de lettres (ou mieux, en moyenne en raison de mots non-existants).

Pour aider à l'indexation, nous pouvons avoir plusieurs tables / dictionnaires, un par nombre de lettres. En outre, selon les statistiques les voyelles et les consonnes peuvent être traitées séparément. Une autre astuce serait d'avoir un ordre de tri personnalisé, plaçant les lettres les plus sélectives en premier.

torsions supplémentaires au jeu (comme la recherche de mots fabriqués à partir d'un sous-ensemble des lettres) est surtout une question de itérer le puissance set de ces lettres et vérifier le dictionnaire pour chaque combinaison.

Quelques heuristiques peuvent être introduits pour aider élaguer quelques-unes des combinaisons (par exemple des combinaisons sans voyelles [et d'une longueur donnée] ne sont pas des solutions possibles, etc. Il faut gérer ces heuristiques soigneusement la coût de recherche est relativement faible.

Answer 3

Pour votre index de dictionnaire, construire une carte (carte [Sac [Char], Liste [chaîne]]). Il devrait être une carte de hachage de sorte que vous pouvez obtenir O (1) mot recherche. Un sac [Char] est un identificateur pour un mot qui est unique à l'ordre des caractères. Il est est essentiellement une carte de hachage de Char à Int. Le Char est un caractère donné dans le mot et l'Int est le nombre de fois que le caractère apparaît dans le mot.

Exemple:

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

Pour trouver les mots, prendre toutes les combinaisons de caractères de la chaîne d'entrée et le chercher dans cette carte. La complexité de cet algorithme est O (2 ^ n) de la longueur de la chaîne d'entrée. Notamment, la complexité ne dépend pas de la longueur du dictionnaire.

Answer 4

Cela ressemble à recherche de chaîne Rabin-Karp serait bon choix. Si vous utilisez une fonction de hachage puis rouler à chaque position que vous avez besoin d'une mise à jour de la valeur de hachage et une recherche de dictionnaire. Vous devez également créer une bonne façon de faire face à différentes longueurs de mots, comme tronquer tous les mots au mot le plus court dans l'ensemble et revérifier correspondances possibles. Fractionnement le mot mis en plages de longueurs séparées réduira la quantité de faux positifs au détriment de l'augmentation du travail de hachage.

Answer 5

Il y a deux façons de le faire. La première consiste à vérifier chaque permutation candidat de lettres dans le mot pour voir si le candidat est dans votre dictionnaire de mots. C'est un O (N!) Fonctionnement, en fonction de la longueur du mot.

L'autre façon est de vérifier chaque mot candidat dans votre dictionnaire pour voir si elle est contenue dans le mot. Cela peut être accéléré par l'agrégation du dictionnaire; au lieu de chaque mot candidat, vous vérifiez tous les mots qui sont anagrammes les uns des autres à la fois, car si l'un d'eux est contenu dans votre mot, tous sont.

Donc, commencer par la construction d'un dictionnaire dont la clé est une chaîne triée de lettres et dont la valeur est une liste des mots qui sont anagrammes de la clé:

>>> 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)

Maintenant, nous avons besoin d'une fonction pour voir si un mot contient un candidat. Cette fonction suppose que le mot et le candidat sont tous deux classés, pour qu'il puisse passer par les deux lettre par lettre et donner rapidement quand il estime qu'ils ne correspondent pas.

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

Maintenant, trouver toutes les clés candidats dans le dictionnaire qui sont contenus par le mot, et regrouper toutes leurs valeurs dans une seule liste:

>>> 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']

Cette dernière étape prend environ un quart de seconde sur mon ordinateur portable; il y a 195K clés dans mon dictionnaire (j'utilise le fichier mots Unix BSD).