Ich mache eine mobile App, um Anagramme und teilweise Übereinstimmungen zu finden. Mobil ist wichtig, weil es nicht viel Rechenleistung gibt und Effizienz der Schlüssel ist.
Der Algorithmus nimmt eine beliebige Anzahl von Buchstaben, einschließlich Wiederholungen, und findet die längsten Wörter, die aus seinen Buchstaben bestehen, wobei jeder Buchstabe nur einmal verwendet wird. Ich bin auch daran interessiert, die Top-Ergebnisse schnell zu finden und kümmere mich nicht wirklich um die Bottoms (kürzere), solange N erfüllt ist. Zum Beispiel:
%Vor%Ich habe ein wenig gegoogelt und ein paar Algorithmen gefunden, und ich habe eine gefunden, von der ich dachte, dass sie effizient wäre, aber nicht so effizient ist, wie ich es gerne hätte.
Ich habe ein vorgefertigtes Nachschlagwörterbuch, das den echten Wörtern, die diesen Schlüssel erzeugen, einen sortierten Schlüssel zuordnet.
%Vor%Ich habe jedes Wörterbuch auf der Basis der Länge des Schlüssels weiter unterteilt. So befinden sich Schlüssel, die 5 Buchstaben lang sind, in einem Wörterbuch, Schlüssel, die 6 in einem anderen sind. Jedes dieser Wörterbücher befindet sich in einem Array, in dem der Index die Länge der Schlüssel angibt, die im Wörterbuch gefunden werden.
%Vor% Mein Algorithmus beginnt mit einem Eingabewort " lappe " und sortiert es:
Nun, für jedes Wörterbuch, das einen Inhalt von höchstens 5 Buchstaben hat, mache ich einen Vergleich, um es herauszuziehen. Hier ist Pseudocode:
%Vor% Das Wörterbuch enthält nur ungefähr 170.000 Wörter, aber Suchvorgänge dauern bis zu 20 Sekunden für 12-Buchstaben-Eingaben. Meine match Methode macht eine Regex aus dem Schlüssel:
, so dass beispielsweise ein 4-stelliger Schlüssel wie acst (act) mit ackst (stack) übereinstimmt, weil:
Ich habe gesehen, dass andere Apps dasselbe in sehr viel kürzerer Zeit machen, und ich frage mich, ob mein Ansatz Müll ist oder nur einige Feinabstimmungen erfordern.
Wie kann ich die maximale Recheneffizienz für die Erzeugung der oberen N Anagramme von einem Wort erhalten, sortiert nach maximaler Länge?
Wenn Sie ein Wörterbuch als einen Buchstabenbaum betrachten (und vielleicht sogar darstellen), können Sie vermeiden, viele Knoten zu betrachten. Wenn "stack" im Wörterbuch ist, dann wird es einen Pfad von der Wurzel zu einem Blatt mit der Bezeichnung a-c-k-s-t geben. Wenn das eingegebene Wort "attacks" ist, dann sortiere das, um aackstt zu erhalten. Sie können eine rekursive Routine schreiben, um Links von der Wurzel nach unten zu verfolgen, wobei Sie Buchstaben von aackstt konsumieren, während Sie fortfahren. Wenn du die Quecke erreichst, hast du noch etwas übrig in deiner Schnur, so kannst du den s folgen, um zu kommen, aber du kannst dich ausschließen, um acku und seine Nachkommen zu erreichen, v, um ackv und seine Nachkommen zu erreichen, und so weiter / p>
Tatsächlich könnten Sie mit diesem Schema nur einen Baum verwenden, um Wörter aus einer beliebigen Anzahl von Buchstaben zu speichern, was Sie davor bewahren sollte, mehrere Suchen durchzuführen, eine für jede Ziellänge.
Das Erzeugen von regulären Ausdrücken ist ein wenig teuer, und deshalb möchten Sie das wahrscheinlich nicht innerhalb einer Schleife machen.
Eine Option (nicht unbedingt super effizient, aber es scheint in diesem speziellen Fall nützlich zu sein) ist, dass statt alle Wörter in Ihrem Wörterbuch zu durchsuchen, versuchen, Buchstaben in verschiedenen Kombinationen zu entfernen und zu prüfen, ob das Ergebnis Zeichenfolge ist in Ihrem Wörterbuch. Dies wird bei 2 ^ n Iterationen (wobei n die Anzahl der Buchstaben in Ihrem Wort ist) max., Was besser ist als 170k für n & lt; 18. Beachten Sie, dass dieser spezielle Ansatz bei langen Eingaben nicht standhält, aber ansonsten sehr schnell sein sollte.
Erstellen Sie Ihr Wörterbuch wie folgt:
%Vor%Und jetzt, um alle Anagramme zu finden oder Suchwort S
%Vor%Nun habe ich nicht behandelt, wie man mit "Teilstringsuchen" umgeht (nach Anagrammwörtern suchend, die kleiner sind als das Suchwort. Ich war etwas verwirrt, wenn das eine Voraussetzung war Anagramme sollten genau die gleichen Zeichen wie das Suchwort haben, aber Sie können wahrscheinlich alle Teilzeichenfolgen Ihrer Suchzeichenfolge aufzählen und jede Teilzeichenfolge über den oben beschriebenen Suchalgorithmus ausführen.
Das ist nur eine Idee, aber vielleicht ist es genau das, wonach Sie suchen. Sie haben nur eine Struktur, die Sie durchlaufen, und alle Wörter aller Größen sind darin enthalten. Mit jedem Iterationsschritt führen Sie einen weiteren Buchstaben ein und Sie beschränken die Suche nur auf Wörter, die keine Buchstaben "größer" als die bereits eingegebenen haben. Zum Beispiel, wenn Sie M einführen, können Sie nichts mehr in den Bereich N-Z einführen.
Die Struktur könnte ein binärer Baum sein, bei dem die Einführung eines Buchstabens mehrere Baumebenen weiterführt. Jeder Knoten hat einen Buchstaben und verzweigt sich in den Rest kleinerer Buchstaben und den Zweig in den Rest größerer Buchstaben und einen Zweig zum Stamm der nächsten eingegrenzten Suche und einen Zeiger auf die Liste der Wörter, die vollständig mit Buchstaben aufgebaut sind soweit eingeführt. Verzweigungen können null sein, wenn in diesem Suchunterraum keine möglichen Wörter vorhanden sind, aber Sie können nicht gleichzeitig null für 3 Zweige und null für den Zeiger auf die Liste der Wörter haben. (Nun, Sie können, als eine Art von Optimierung, die im Moment irrelevant ist). Anstelle des Zeigers zur Liste der Wörter können Sie eine Markierung haben, die die Existenz von Wörtern mit gegebenen Buchstaben anzeigt, aber diese Wörter können in einem anderen Wörterbuch gespeichert werden.
Sagen wir also, wir haben Buchstaben ACKST. Von der Wurzel der Struktur aus suchen Sie nach allen diesen Buchstaben in einer Schleife, aber nach K zum Beispiel können Sie nur weiter mit A und C suchen (da S und T über K liegen). Da uns das größte Wort am meisten interessiert, sollten wir die Suche vom größten Buchstaben (in diesem Fall T) starten und es mit dem nächstgrößeren Buchstaben fortsetzen. Zu dem Wort CAT können wir nur in dieser bestimmten Reihenfolge nach den Buchstaben T, C, A suchen. Sobald wir bei A angekommen sind, wird ein Zeiger auf die folgenden Wörter angezeigt: ACT, CAT.
Tags und Links algorithm performance logic anagram