Wie kann man alle möglichen Wörter aus einem String sortieren?

Ich frage mich, wie ich mit dieser Aufgabe fortfahren muss, nimm diese Saite zum Beispiel "Dinge und Dinge".

Wie könnte ich alle möglichen Strings aus dieser Saite generieren, um sie einzeln gegen ein englisches Wörterbuch zu sehen?

Das Ziel ist es, gültige englische Wörter in einer Zeichenfolge zu finden, die keinen Platz enthält.

Vielen Dank

11 Solutions collect form web for “Wie kann man alle möglichen Wörter aus einem String sortieren?”

Eine andere Möglichkeit geht es umgekehrt, anstatt Substrings aus einer Zeichenkette zu erzeugen, alle Kandidaten zu holen und sie gegen deinen String zu platzieren.

Sie können als Ergebnis (Anfang, Ende) Paare von Indizes der Wörter in der ursprünglichen Zeichenfolge speichern.

Dies könnte leicht in regex oder, wenn nicht performant genug, mit str.find (), oder wenn auch nicht performant genug mit komplexeren Wörterbuch Index-Schemata oder smarts über was kann und kann nicht übereinstimmen (siehe Gregg's Antwort für Ideen )

Hier hast du eine Probe von dem, was ich meine

candidate = "thingsandstuffmydarlingpretty" words = file('/usr/share/dict/words').read() #This generator calls find twice, it should be rewritten as a normal loop generate_matches = ((candidate.find(word),word) for word in words.split('\n') if candidate.find(word) != -1 and word != '') for match in generate_matches: print "Found %s at (%d,%d)" % (match[1],match[0],match[0] + len(match[1])) 

Die Leute sprechen darüber, als ob der Auftrag des Problems die Anzahl der möglichen Teilstrings ist. Das ist falsch. Die richtige Reihenfolge dieses Problems ist:

O (min (Anzahl der Worte-in-dict, Zahl-of-substring-Kombinationen) * Vergleichskonzert)

Also, ein anderer Ansatz für das Problem, auf Vinko aufzubauen, ist, den Heck aus dem Wörterbuch zu indizieren (zB für jede Arbeit im Dict, bestimmen die Buchstaben in diesem Wort, die Länge des Wortes usw.). Das kann die Dinge dramatisch beschleunigen. Als Beispiel wissen wir, dass das Ziel "Königin" nicht mit "Zebra" übereinstimmen kann (kein z ist!) (Oder irgendein Wort, das z, r, b, a …) und dergleichen enthält. Auch speichern Sie jedes Wort in der Dikt als sortierte Zeichenfolge ('Zebra' -> 'aberz') und "String in String" (längste gemeinsame Substring) Matching. 'Eenuq' vs 'abarz' (kein Spiel).

(Anmerkung: Ich gehe davon aus, dass die Reihenfolge der Buchstaben im ursprünglichen Wort egal ist – es ist ein "Brieftasche", wenn sie es tun, dann passen Sie sich entsprechend an)

Wenn Sie viele Wörter haben, um sofort zu vergleichen, können die Vergleichskosten mit etwas wie KMP weiter gesenkt werden.

(Auch ich tauchte direkt hinein und machte einige Annahmen, dass Alex nicht, also wenn sie falsch liegen, dann schließen Sie meinen Mund!)

Der Brute-Force-Ansatz, dh die Überprüfung jedes Substrings, ist auch für Strings mit mittleren Längen rechnerisch nicht möglich (ein String der Länge N hat O(N**2) Teilstrings). Es sei denn, es gibt eine ziemlich enge Bindung an die Länge der Saiten, die Sie interessieren, das klappt nicht gut.

Um die Dinge mehr machbar zu machen, ist mehr Wissen nötig – interessieren Sie sich für die Überschneidung von Wörtern (zB "Sachen" und "Sand" in Ihrem Beispiel) und / oder Wörter, die unberechtigte Zeichen (zB "Ding" und "und" In deinem Beispiel, so dass die Zwischenstufe "stranded", oder du willst eine strenge Trennung der String in nebeneinander liegende (nicht überlappende) Worte ohne Rückstand?

Letzteres wäre das einfachste Problem, denn die Grade der Freiheit fallen scharf ab – im wesentlichen, um zu versuchen, eine Folge von "Bruchpunkten" zu bestimmen, die jeweils zwischen zwei benachbarten Zeichen liegen, die den String in Worte aufteilen würden. Wenn das der Fall ist, brauchst du jeden möglichen gültigen Split (dh brauchst du beide "Sachen Sand" und "Sachen und"), oder wird irgendwelche einmalige Split tun, oder gibt es Kriterien, die dein Split optimieren muss?

Wenn Sie all diese Fragen klären, kann es Ihnen möglich sein, Ihnen mehr Hilfe zu geben!

Norden schrieb einen großartigen Artikel darüber, wie man eine Rechtschreibprüfung in Python schreibt.

http://norvig.com/spell-correct.html

Es wird Ihnen eine gute Idee, wie man Wörter zu erkennen. (Dh nur testen Sie jede Gruppe von Zeichen, bis Sie ein gültiges Wort bekommen … Vorsicht, dass Sie deterministisch sein, müssen Sie das Gegenteil tun. Testen Sie alle Zeichenfolge und dann gehen Sie entfernen Chars am Ende, so dass Sie zusammengesetzt werden Worte, wie sie beabsichtigt sind … oder nicht beabsichtigt, wer weiß, Räume haben einen Grund 🙂

Danach ist es einfach CS 101.

Dies wird finden, ob ein Kandidat aus den Buchstaben in einem gegebenen Wort gebildet werden kann oder nicht; Es wird davon ausgegangen, dass das word (aber nicht candidate ) vor dem Anruf sortiert wird.

 >>> def match(candidate, word): def next_char(w): for ch in sorted(w): yield ch g = next_char(word) for cl in sorted(candidate): try: wl = g.next() except StopIteration: return False if wl > cl: return False while wl < cl: try: wl = g.next() except StopIteration: return False if wl > cl: return False return True >>> word = sorted("supernatural") >>> dictionary = ["super", "natural", "perturb", "rant", "arrant"] >>> for candidate in dictionary: print candidate, match(candidate, word) super True natural True perturb False rant True arrant True 

Wenn ich die BSD Worte Datei (235.000 + Worte) und führen Sie diese mit plenipotentiary als mein Wort, bekomme ich etwa 2500 Hits in unter einer Sekunde und eine Hälfte.

Wenn du viele Suchvorgänge ausführen wirst, ist es eine gute Idee, die Sorte von next_char zu entfernen, ein Wörterbuch zu next_char , das auf die sortierte Version jedes Wortes geschrieben ist –

 d = dict([(sorted(word), word) for word in dictionary]) 

Und produzieren Ergebnisse über Logik wie folgt:

 result = [d[k] for k in d.keys() if match(k, word)] 

So dass du immer wieder 250.000 Sorten machen musst.

Nun, hier ist meine Idee

  • Finden Sie alle möglichen Strings mit 1 Zeichen aus dem Original
  • Finden Sie alle möglichen Strings mit 2 Zeichen aus dem Original
  • … Gleiches bis zur Länge der Original-String

Dann füge alles hinzu und gehe mit deinem Wörterbuch zusammen

Was passiert, wenn du es in Silben zerbrichst und dann die Worte baust, um Worte zu vergleichen, um deinem Wörterbuch zu vergleichen. Es ist immer noch eine Brute-Force-Methode, aber es würde sicherlich ein bisschen beschleunigen.

Ich schaute auf eine powerset Umsetzung. Zu viele Möglichkeiten.

Versuchen Sie, Ihre Zeichenfolge und alle Kandidaten aus Ihrem Wörterbuch zu verschlüsseln und sehen Sie, ob der Kandidat aus dem Wörterbuch aus dem Kandidatenstring gemacht werden könnte. Das heißt, die Buchstaben im Wörterbuchwort erscheinen nicht häufiger als in deiner Kandidatenfolge?

 from __future__ import with_statement import collections def word_dict(word): d = collections.defaultdict(int) for c in word: d[c] += 1 return d def compare_word_dict(dict_cand, cand): return all(dict_cand[k] <= cand[k] for k in dict_cand) def try_word(candidate): s = word_dict(candidate) dictionary_file = r"h:\words\WORDs(3).txt" i = 0 with open(dictionary_file) as f: for line in f: line = line.strip() dc = word_dict(line) if compare_word_dict(dc,s): print line i += 1 return i print try_word("thingsandstuff") 

Ich bekomme 670 Wörter mit meinem Wörterbuch. Scheint ein bisschen klein Dauert etwa 3 Sekunden auf 200k Worte im Wörterbuch.

Dies funktioniert für python 2.5 und höher wegen der Addition von collections.defaultdict . In python 3.1, collections.Counter wurde hinzugefügt, dass funktioniert wie collections.defaultdict (int).

Code:

 def all_substrings(val): return [val[start:end] for start in range(len(val)) for end in range(start + 1, len(val))] val = "thingsandstuff" for result in all_substrings(val): print result 

Ausgabe:

 t th thi thin thing 

[…]

 tu tuf u uf f 

Werfen Sie einen Blick auf diesen Beitrag , es adressiert das gleiche Problem, sowohl in Python und OCaml, mit einer Lösung auf die Normalisierung der Strings zuerst anstatt tun Brute-Force-Suche basiert.

Übrigens, die automatische Übersetzung entfernt die Einrückung, so dass die Arbeit Python-Code, die Sie sollten die unübersetzte spanische Version (das ist in der Tat ist sehr gut als die crappy Englisch von Google Übersetzer erstellt) …

Bearbeiten:

Re-lesen Sie Ihre Frage, ich verstehe jetzt, dass Sie wollen, dass nur die Worte, die nicht verwurzelt sind, richtig? Wenn ja, müssen Sie nicht alle Sachen, die in der Post beschrieben werden, nur:

 maxwordlength = max(map(len, english_words)) for i in range(len(word)): for j in range(i+1, min(maxwordlength+i, len(word))): if word[i:j] in english_words: print word[i:j] 

Die Komplexität sollte O (N) jetzt sein, da die Größe des größten Wortes in Englisch endlich ist.

Wenn du das volle Wörterbuch gut im Voraus kennst und es nicht zwischen den Suchvorgängen wechselt, kannst du folgendes versuchen …

Index das Wörterbuch. Jedes Wort (zB "hallo") wird zu einem (Schlüssel-, Daten-) Tupel wie ("ehllo", "hallo"). In der Taste sind die Buchstaben alphabetisch sortiert.

Gute Indexdatenstrukturen würden einen Trie (aka digital tree) oder einen ternären Baum enthalten . Ein konventioneller Binärbaum konnte zur Arbeit gebracht werden. Ein Hash-Tisch würde nicht funktionieren. Ich werde einen Trie oder einen ternären Baum annehmen. Hinweis – Die Datenstruktur muss als Multimap dienen (Sie benötigen wahrscheinlich eine verkettete Liste der übereinstimmenden Datenelemente an jedem Key-Matched-Blatt).

Bevor Sie eine bestimmte Zeichenfolge auswerten, sortieren Sie die Buchstaben in der Zeichenfolge. Dann mache eine Schlüsselsuche in der Datenstruktur. ABER eine einfache Schlüsselsuche findet nur Wörter, die alle Buchstaben aus der ursprünglichen Zeichenfolge verwenden.

Grundsätzlich entspricht eine Trie-Suche jeweils einem Buchstaben, indem sie einen untergeordneten Knoten auf der Grundlage des nächsten Buchstabens der Eingabe auswählt. Bei jedem Schritt haben wir jedoch eine zusätzliche Option – einen Buchstaben der sortierten Eingabezeichenfolge überspringen und am selben Knoten bleiben (dh diesen Buchstaben nicht in der Ausgabe verwenden). Die offensichtliche Sache zu tun ist eine Tiefe-erste Backtracking-Suche. Beachten Sie, dass sowohl unsere Schlüssel als auch unsere Eingabe die Buchstaben sortiert haben, also können wir die Suche ein bisschen optimieren.

Eine ternäre Baumversion folgt ähnlichen Prinzipien zu einem Trie, aber anstelle von mehreren Kindern pro Knoten haben Sie im Grunde die Binärbaumlogik des nächsten Buchstabens in die Struktur eingebaut. Die Suche kann leicht angepasst werden – die Optionen für jede nächste Buchstabensuche passen zum nächsten Eingabebrief oder verwerfen sie.

Wenn Sie Läufe des gleichen Buchstabens in der sortierten Eingabezeichenfolge erhalten, sollte die Option "Skript ein Buchstabe" in der Suche "Sprung zum nächsten Buchstaben" sein. Andernfalls machst du am Ende doppelte Recherchen (beim Backtracking) – zB gibt es 3 verschiedene Möglichkeiten, zwei von drei Duplikatbriefen zu benutzen – man könnte das erste, das zweite oder das dritte Duplikat ignorieren – und man muss nur einen Fall überprüfen .

Optimierungen können zusätzliche Details in den Datenstrukturknoten haben, um den Suchbaum zu beschneiden. Wenn Sie die maximale Länge der Wortschwänze im Teilbaum halten, können Sie überprüfen, ob Ihr verbleibender Teil Ihres Suchstrings genügend Buchstaben enthält, um die Suche fortzusetzen.

Zeitkomplexität ist aufgrund des Backtrackings nicht sofort offensichtlich.

Python ist die beste Programmiersprache der Welt.