Wie würde man ein Programm erstellen, bei dem der Benutzer eine Zeichenfolge eingibt, und das Programm generiert eine Liste von Wörtern, die mit dieser Zeichenfolge beginnen?
Beispiel:
Benutzer: "abd"
Programm: Abdankung, Abdomen, Entführung ...
Danke!
Bearbeiten: Ich benutze Python, aber ich nehme an, dass dies ein ziemlich sprachunabhängiges Problem ist.
Verwenden Sie einen trie .
Fügen Sie Ihre Liste von Wörtern zu einem Trie hinzu. Jeder Pfad von der Wurzel zu einem Blatt ist ein gültiges Wort. Ein Pfad von einem Stammknoten zu einem Zwischenknoten stellt ein Präfix dar, und die untergeordneten Elemente des Zwischenknotens sind gültige Beendigungen für das Präfix.
Eine der besten Methoden hierfür ist die Verwendung eines gerichteten Graphen zum Speichern Ihres Wörterbuchs. Es braucht ein wenig Aufbau, aber wenn es einmal fertig ist, ist es ziemlich einfach, die Art von Suchen zu machen, über die Sie sprechen.
Die Knoten im Diagramm entsprechen einem Buchstaben in Ihrem Wort, so dass jeder Knoten einen eingehenden Link und bis zu 26 (in Englisch) ausgehende Links hat.
Sie können auch einen hybriden Ansatz verwenden, bei dem Sie eine sortierte Liste mit Ihrem Wörterbuch verwalten und das gerichtete Diagramm als Index in Ihr Wörterbuch verwenden. Dann suchen Sie einfach nach Ihrem Präfix in Ihrem gerichteten Diagramm und gehen dann zu diesem Punkt in Ihrem Wörterbuch und spucken alle Wörter aus, die Ihren Suchkriterien entsprechen.
Wenn Sie wirklich Geschwindigkeit wollen, verwenden Sie einen Trie / Automaton. Allerdings wird etwas schneller sein, als einfach die gesamte Liste zu scannen, da die Liste der Wörter sortiert ist:
%Vor%Beachten Sie, dass ein Automat O (1) bezüglich der Größe Ihres Wörterbuchs ist, während dieser Algorithmus O (log (m)) und dann O (n) in Bezug auf die Anzahl der Strings ist, die tatsächlich mit dem beginnen Präfix, während der vollständige Scan O (m) ist, mit n & lt; & lt; m.
Wenn Sie wirklich effizient sein möchten - verwenden Sie Suffixbäume oder Suffix-Arrays - Wikipedia-Artikel .
Ihr Problem besteht darin, welche Suffixbäume entwickelt wurden. Es gibt sogar eine Implementierung für Python - hier
Verwenden Sie regex, um Ihre Wörterliste zu durchsuchen, z. / ^ Wort / und melden Sie alle Übereinstimmungen.
Wenn Sie wirklich schnell sein müssen, verwenden Sie einen Baum:
Erstellen Sie ein Array und teilen Sie die Wörter in 26 Sätze basierend auf dem ersten Buchstaben, dann teilen Sie jedes Element in 26 basierend auf dem zweiten Buchstaben, dann wieder.
Wenn Ihr Benutzer also "abd" eingibt, würden Sie nach Array [0] [1] [3] suchen und eine Liste aller Wörter erhalten, die so beginnen. An diesem Punkt sollte Ihre Liste klein genug sein, um auf den Client überzugehen und Javascript zum Filtern zu verwenden.
Benutze keine Bazooka, um eine Fliege zu töten. Verwenden Sie etwas Einfaches wie SQLite. Es gibt alle Werkzeuge, die Sie für jede moderne Sprache benötigen und Sie können einfach Folgendes tun:
%Vor%Es ist blitzschnell und ein Baby könnte es tun. Außerdem ist es tragbar, ausdauernd und so einfach zu warten.
Python tuto:
Erinnerungsgeneratoren können nur einmal verwendet werden, also drehen Sie sie zu einer Liste (mit list (word_generator)) oder verwenden Sie die itertools.teefunktion, wenn Sie sie mehr als einmal benutzen wollen.
Speichern Sie es in einer Datenbank und verwenden Sie SQL, um nach dem gewünschten Wort zu suchen. Wenn es viele Wörter in Ihrem Wörterbuch gibt, wird es viel schneller und effizienter.
Python hat tausend DB API bekommen, um Ihnen bei der Arbeit zu helfen; -)
Wenn Ihr Wörterbuch wirklich groß ist, würde ich vorschlagen, mit einem Python-Textindex zu indizieren (PyLucene - beachten Sie, dass ich nie die Python-Erweiterung für Lucene verwendet habe). Die Suche wäre effizient und Sie könnten sogar einen Suchwert zurückgeben '.
Auch wenn Ihr Wörterbuch relativ statisch ist, haben Sie nicht einmal den Overhead der Neuindizierung sehr oft.
Tags und Links python list dictionary