Suchen nach Wörtern aus zufälligen Eingabe Buchstaben in Python. Was Algorithmus zur Verwendung / code schon da?

StackOverflow https://stackoverflow.com/questions/1570242

Frage

Ich versuche, ein Wort Descrambler wie diese zu code hier und frage mich, was Algorithmen ich sollte dies implementieren verwenden. wenn jemand Außerdem können vorhandenen Code für diese finden, das wäre toll, wie gut. Grundsätzlich ist die Funktionalität wird wie ein boggle Löser sein, aber ohne eine Matrix zu sein, nur die Suche nach allen Wort Möglichkeiten aus einer Folge von Zeichen. Ich bereits ausreichende Wörterbücher haben.

Ich habe geplant, diese in jedem Python oder Ruby zu tun. Vielen Dank im Voraus für Ihre Hilfe Jungs!

War es hilfreich?

Lösung

würde ich ein Trie . Hier ist eine Implementierung in Python: http://jtauber.com/2005/02/trie.py (Kredit James Tauber)

Andere Tipps

Ich kann das Verständnis des Spiels fehlt aber einige Komplikationen in den Regeln abgesehen, wie mit der Einführung von „Joker“ (Wildcard) Buchstaben, fehlende oder zusätzliche Buchstaben, mehrere Wörter etc ... Ich denke, die folgenden Ideen würde helfen, das Problem in einer etwas relativ uninteressant Sache zu machen. : - (

Leitgedanke Index Wörter durch die bestellt Reihenfolge ihrer Buchstaben .
   Zum Beispiel „Computer“ wird als „cemoprtu“ eingegeben. Ganz gleich, ob die Zufall Zeichnungen bieten sind die Sortierung in der Art, und als Schlüssel verwendet, um mögliche Übereinstimmungen zu finden.    Mit trie Strukturen wie perimosocordiae vorgeschlagen, da die zugrunde liegenden Speicher für diese sortierten Schlüssel und die damit verbundene Worte (n) / wordids in dem „Blatt“ Knoten, Wort Nachschlagen kann in O (n) Zeit durchgeführt werden, wobei n die Anzahl der Buchstaben (oder besser, im Durchschnitt aufgrund von nicht vorhandenen Wörter).

Um weitere Hilfe bei der Indizierung wir mehrere Tabellen / Wörterbücher haben können, je eine pro Anzahl der Buchstaben. Auch je nach Statistik könnten die Vokale und Konsonanten getrennt behandelt werden. Ein weiterer Trick wäre, eine benutzerdefinierte Sortierreihenfolge haben, Anordnen der selektivsten Buchstaben zuerst.

Weitere Drehungen um das Spiel (wie aus einer Teilmenge der Briefe Worte zu finden) ist vor allem eine Frage der Iterieren der Potenzmenge diese Buchstaben und für jede Kombination das Wörterbuch zu überprüfen.

Ein paar Heuristiken können eingeführt werden, um Hilfe Prune einige der Kombinationen (zB Kombinationen ohne Vokale [und einer bestimmten Länge] sind nicht möglich Lösungen etc. Eines dieser Heuristik sorgfältig für die Verwaltung sollte Lookup-Kosten relativ gering ist.

Für Ihre Wörterbuch-Index, bauen eine Karte (Map [Bag [Char], List [String]]). Es sollte eine Hash-Karte sein, so können Sie erhalten O (1) Wort-Lookup. A Bag [Zeichen] ist eine Kennung für ein Wort, das Zeichen, um einzigartige oben ist. Es ist im Grunde eine Hash-Karte von Char zu Int. Der Char ist ein bestimmtes Zeichen in dem Wort und die Int ist die Anzahl der Male, die Zeichen in dem Wort angezeigt wird.

Beispiel: 

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

Worte zu finden, nehmen Sie jede Kombination von Zeichen aus der Eingabezeichenfolge und sehen Sie in dieser Karte auf. Die Komplexität dieses Algorithmus ist O (2 ^ n) in der Länge der Eingabezeichenfolge. Bemerkenswert ist, wird die Komplexität hängt nicht von der Länge des Wörterbuchs.

Das klingt wie Rabin-Karp String suchen wäre sein gute Wahl. Wenn Sie eine rollende Hash-Funktion dann an jeder Position benötigen Sie einen Hash-Wert zu aktualisieren und ein Wörterbuchsuche. Sie müssen auch eine gute Möglichkeit zu schaffen, mit unterschiedlichen Wortlängen, wie Kürzen alle Worte auf das kürzeste Wort in dem Satz und erneute Überprüfung mögliche Übereinstimmungen zu bewältigen. Splitting der Wortsatz in einzelne Längenbereichen wird die Menge von Fehlalarmen auf Kosten der Erhöhung der Hashing-Arbeit reduzieren.

Es gibt zwei Möglichkeiten, dies zu tun. Eine davon ist jeden Kandidaten Permutation der Buchstaben im Wort zu überprüfen, um zu sehen, ob der Kandidat in Ihrem Wörterbuch von Worten ist. Das ist ein O (N!) Betrieb, abhängig von der Länge des Wortes.

Die andere Möglichkeit ist es, jedes Kandidatenwort in Ihrem Wörterbuch zu überprüfen, um zu sehen, ob es innerhalb des Wortes enthalten ist. Dies kann durch die Aggregation des Wörterbuchs beschleunigt werden; statt jedes Kandidatenwort, Sie alle Wörter überprüfen, die auf einmal Anagramme voneinander sind, denn wenn einer von ihnen in Ihrem Wort enthalten ist, alle von ihnen sind.

beginnen also durch ein Wörterbuch Gebäude, dessen Schlüssel ist eine sortierte Folge von Buchstaben und deren Wert eine Liste der Wörter, die Anagramme des Schlüssels sind: 

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

Jetzt müssen wir eine Funktion, um zu sehen, ob ein Wort, einen Kandidaten enthält. Diese Funktion geht davon aus, dass das Wort und Kandidaten sind beide sortieren, so dass es schnell durch sie beiden Buchstaben für Buchstaben und geben gehen kann, wenn es feststellt, dass sie nicht übereinstimmen. 

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

Nun sind alle Kandidaten Schlüssel im Wörterbuch finden, die das Wort enthalten sind, und alle ihre Werte in einer einzigen Liste zusammenfassen: 

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

Der letzte Schritt dauert etwa eine Viertelsekunde auf meinem Laptop; es gibt 195K Schlüssel in meinem Wörterbuch (ich die BSD Unix Wortdatei bin mit).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top