Effizienter Wortscramble-Algorithmus

Question

Ich bin auf der Suche nach einem effizienten Algorithmus zum Verwürfeln eines Satzes von Buchstaben in eine Permutation, die die maximale Anzahl von Wörtern enthält.

Zum Beispiel sagen, dass ich die Liste der Buchstaben gegeben habe: {e, e, h, r, s, t}. Ich muss sie so bestellen, dass sie die maximale Anzahl von Wörtern enthält. Wenn ich diese Buchstaben in "Theres" bestelle, enthalten sie die Wörter "das", "dort", "sie", "hier" und "davor". So könnte dieses Beispiel eine Punktzahl von 5 haben, da es 5 Wörter enthält. Ich möchte die Buchstaben so bestellen, dass sie die höchste Punktzahl haben (die meisten Wörter enthalten).

Ein naiver Algorithmus wäre es, jede Permutation zu bewerten. Ich glaube, das ist O (n!), Also würden 720 verschiedene Permutationen nur für die obigen 6 Buchstaben versucht werden (einschließlich einiger Duplikate, da das Beispiel e zweimal hat). Für weitere Briefe wird die naive Lösung natürlich schnell unmöglich.

Der Algorithmus muss nicht wirklich die beste Lösung erzeugen, aber er sollte in einer angemessenen Zeit eine gute Lösung finden. Für meine Anwendung funktioniert das einfache Raten (Monte Carlo) bei einigen Millionen Permutationen ziemlich schlecht, und das ist derzeit der Punkt, den es zu schlagen gilt.

Ich verwende derzeit den Aho-Corasick Algorithmus, um Permutationen zu bewerten. Es sucht nach jedem Wort im Wörterbuch in nur einem Durchlauf durch den Text, also glaube ich, dass es sehr effizient ist. Das bedeutet auch, dass ich alle Wörter in einem trie gespeichert habe, aber wenn ein anderer Algorithmus einen anderen Speicher benötigt, ist das auch in Ordnung. Ich mache mir keine Sorgen über das Einrichten des Wörterbuchs, nur die Laufzeit der eigentlichen Bestellung und Suche. Selbst ein unscharfes Wörterbuch könnte bei Bedarf verwendet werden, wie beispielsweise ein Bloom Filter.

Für meine Anwendung ist die Liste der Buchstaben etwa 100, und das Wörterbuch enthält über 100.000 Einträge. Das Wörterbuch ändert sich nie, aber mehrere verschiedene Listen von Buchstaben müssen bestellt werden.

Ich überlege, eine path finding algorithm zu versuchen. Ich glaube, ich könnte mit einem zufälligen Buchstaben von der Liste als Ausgangspunkt beginnen. Dann würde jeder verbleibende Buchstabe verwendet, um einen "Pfad" zu erstellen. Ich denke, das würde gut mit dem Aho-Corasick-Scoring-Algorithmus funktionieren, da die Scores einen Buchstaben nach dem anderen ergeben könnten. Ich habe den Pfad noch nicht ausprobiert; vielleicht ist es nicht einmal eine gute Idee? Ich weiß nicht, welcher Pfadfindungsalgorithmus der beste sein könnte.

Ein anderer Algorithmus, an den ich dachte, beginnt auch mit einem zufälligen Buchstaben. Dann würde der Wörterbuchtried nach "reichen" Zweigen durchsucht, die die verbleibenden Buchstaben enthalten. Wörterbuchzweige, die nicht verfügbare Buchstaben enthalten, würden abgeschnitten werden. Ich bin ein wenig neblig auf die Details, wie das genau funktionieren würde, aber es könnte vollständig Scoring-Permutationen beseitigen.

Answer 1

Sie könnten versuchen simulated annealing, die erfolgreich für komplexe Optimierungsprobleme in einer Reihe von Domänen verwendet wurde. Im Grunde machen Sie randomisiertes Bergsteigen, während Sie die Zufälligkeit allmählich reduzieren. Da Sie bereits die Aho-Corasick-Wertung haben, haben Sie die meiste Arbeit bereits erledigt. Alles, was Sie brauchen, ist eine Möglichkeit, Nachbar-Permutationen zu erzeugen; Dafür sollte etwas Einfaches wie das Tauschen von Buchstaben gut funktionieren.

Answer 2

Haben Sie über die Verwendung eines genetischen Algorithmus nachgedacht? Sie haben bereits den Anfang Ihrer Fitnessfunktion. Sie könnten mit den Mutations- und Crossover-Algorithmen (danke Nathan) experimentieren, um zu sehen, welche die beste Arbeit machen. Eine andere Option wäre, dass Ihr Algorithmus das kleinste mögliche Wort aus dem Eingabesatz erstellt und dann einen Buchstaben nach dem anderen hinzufügt, sodass das neue Wort auch ein neues Wort ist oder ein neues Wort enthält.

Beginnen Sie mit ein paar verschiedenen Startwörtern für jeden Eingabesatz und sehen Sie, wohin es führt.

Nur ein paar müßige Gedanken.

Answer 3

Es könnte nützlich sein, um zu überprüfen, wie andere diese gelöst: http://sourceforge.net/search/?type_of_search=soft&words=anagram

Auf dieser Seite findet man Anagramm Online generieren können. Ich habe eine Weile damit herumgespielt und es macht großen Spaß.Es erklärt nicht im Detail, wie es seine Arbeit macht, aber die Parameter geben einen Einblick. http://wordsmith.org/anagram/advanced.html

Answer 4

Hier ist eine Idee, inspiriert von Markov Chains:

1. Precompute den Buchstaben Übergangswahrscheinlichkeiten in Ihrem Wörterbuch. Erstellen Sie eine Tabelle mit der Wahrscheinlichkeit, dass einem Buchstaben X ein weiterer Buchstabe Y für alle Buchstabenpaare folgt, basierend auf den Wörtern im Wörterbuch.
2. Generieren Sie Permutationen, indem Sie jeden nächsten Buchstaben aus dem verbleibenden Buchstabenpool nach dem vorherigen Buchstaben und der Wahrscheinlichkeitstabelle zufällig auswählen, bis alle Buchstaben aufgebraucht sind. Führe das viele Male aus.
3. Sie können experimentieren, indem Sie den "Speicher" Ihrer Übergangstabelle vergrößern - schauen Sie nicht nur einen Buchstaben zurück, sondern sagen Sie 2 oder 3. Dies erhöht die Wahrscheinlichkeitstabelle, gibt Ihnen aber mehr Möglichkeiten, ein gültiges Wort zu erstellen.