Ich habe eine große Datenbank zum Lösen von Kreuzworträtseln, bestehend aus einem Wort und einer Beschreibung. Meine Anwendung erlaubt die Suche nach Wörtern einer bestimmten Länge und Zeichen auf bestimmten Positionen (das ist auf die harte Tour gemacht ... gehe durch alle Wörter und überprüfe jedes). Zusätzlich eine Suche nach Beschreibung (falls erforderlich)
Finden Sie zum Beispiel das Wort _ _ A _ _ B (6-Buchstaben-Wort, drittes Zeichen A und letztes B)
Ich möchte die Wörter so indizieren, dass die Suche wirklich schnell ist. Meine erste Idee war, eine ausgewogene Baumstruktur zu verwenden, irgendeinen anderen Vorschlag?
Okay, ich werde etwas Seltsames vorschlagen, aber kommend von C++ Ich habe Boost schon lange benutzt und ich bin gekommen, um die MultiIndex -Bibliothek zu sehen.
Die Idee dieser Bibliothek besteht darin, eine Sammlung zu erstellen, aber viele verschiedene Möglichkeiten, sie abzufragen. Es könnte in der Tat eine Datenbank modellieren.
Lassen Sie uns also unsere Wörter in eine Tabelle setzen und die notwendigen Indizes einfügen:
%Vor%Nun wird die Abfrage wie folgt aussehen:
%Vor%Einfach genug, nicht wahr?
Für maximale Effizienz sollte die Tabelle in der Länge partitioniert werden, und die Indizes (einer pro cX-Spalte) sollten für die Partition lokal sein.
Für eine In-Memory-Lösung würden Sie einen Container pro Länge haben, der so viele Indizes wie die Länge enthält, wobei jeder Index eine Hash-Tabelle ist, die auf eine sortierte Liste verweist (leichtere Zusammenführung)
Hier ist eine Python-Beschreibung:
%Vor% Ich habe freiwillig das Argument length angegeben, um die Größe der Hashes zu minimieren und so die Suche zu verbessern. Außerdem sind die Sätze nach Länge sortiert, so dass die Berechnung der Kreuzung besser ist:)
Gehen Sie voran und testen Sie es gegen andere Lösungen, wenn Sie möchten:)
Diese Frage: Guter Algorithmus und Datenstruktur für das Nachschlagen von Wörtern mit fehlenden Buchstaben? begann genau wie der, den Sie fragen, aber dann wurde es zu etwas anderem anders und einfacher bearbeitet. Dennoch können Sie dort einige Ideen finden.
Kurz gesagt: Jeder empfiehlt, das gesamte Wörterbuch in den Speicher zu laden und die Wörter je nach Länge in Gruppen zu unterteilen. Von dort können Sie viele verschiedene Richtungen gehen. Je mehr Speicher Sie verbrauchen möchten, desto schneller können Sie gehen.
Ein schöner Vorschlag besteht darin, eine Hash-Tabelle von Listen von Wörtern einer gegebenen Länge zu halten, die einen gegebenen Buchstaben an einer gegebenen Position haben. Sie können es so (in Python) erstellen:
%Vor% Wenn Sie jetzt ein 6-Buchstaben-Wort benötigen, das auf B endet, können Sie einfach nach wordlists[6, 5, 'B'] fragen und Sie haben die vollständige Liste. Wenn Sie mehr als einen Buchstaben kennen, wie in ..A..B , können Sie die Liste auswählen, die am kürzesten ist, und jedes Wort mit dem gewünschten Muster testen. Das Wörterbuch meines Computers hat nur 21 Wörter mit sechs Buchstaben, die mit B enden, von denen nur SCARAB übereinstimmt.
Da Sie eine Datenbank verwenden, erstellen Sie eine Suffix-Tabelle.
Zum Beispiel:
Mit dieser Tabelle ist es einfach, alle Wörter zu erhalten, die ein bestimmtes Zeichen in einer bestimmten Position enthalten so:
%Vor% Erhalte alle Wörter, die 't' an Position 2 enthalten.
Update: Wenn Sie Speicherplatz sparen und ein wenig Geschwindigkeit opfern möchten, können Sie ein verwenden Suffix-Array .
Sie können alle Wörter in einer Zeile (Array) mit einem Trennzeichen zwischen ihnen speichern, zB $ , und create
ein Suffix-Array, das Zeiger auf Zeichen haben wird. Mit char c können Sie jetzt alle Instanzen von Wörtern finden, die sie enthalten. Trotzdem musst du prüfen, ob es in der richtigen Position ist.
(indem Sie überprüfen, wie weit es von der $ s entfernt ist)
Wahrscheinlich mit der obigen Technik ist die Suche x10 schneller als die Suche nach allen Wörtern in Ihrem ursprünglichen Programm.
Update 2: Ich habe den Datenbank-Ansatz in einem meiner Programme verwendet, wo ich Suffixe wie "ne" suchen musste, und ich habe vergessen, sie anzupassen (zu optimieren) dieses spezifische Problem.
Sie können einfach ein einzelnes Zeichen als Suffix speichern:
%Vor%das spart viel Platz. Jetzt wird die Abfrage
%Vor%Sie könnten Ihre Informationen in einem Trie einer Art speichern (vielleicht ein ternärer Suchbaum). Ein Algorithmus für die partielle Suche unter Verwendung eines Trie ist in Abschnitt 6 von beschrieben Papier von Sedgewick und Bentley. Sie möchten natürlich verschiedene Versuche für die verschiedenen Längen von Wörtern haben. Das Papier sagt, dass der partielle Suchalgorithmus eine Zeit von O (n ^ ((k-s) / k)) benötigt, damit s Buchstaben in einem Trie von n k-langen Wörtern spezifiziert werden.