Was sind gute Datenstrukturen für automatische Vervollständigungsalgorithmen? Welche Datenstrukturen ermöglichen es, effizient Strings zu finden, die einen bestimmten Teilstring enthalten?Datenstruktur für die automatische Vervollständigung
Wenn Sie schauen, um etwas ähnlich wie zu tun, Google es ist die automatische Vervollständigung implementiert, könnte man ein ternäres Suchbaum prüfen wollen:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Wenn Sie jedoch einen beliebigen Teilzeichen finden wollen Versuchen Sie in einer Zeichenfolge eine generalisierte Suffixstruktur.
Funktioniert das nicht nur, wenn Sie nur Präfixe abgleichen wollen? z.B. ein ternärer Suchbaum hilft Ihnen, "ab" in "abcd", aber nicht "bc" in "abcd" zu finden (könnte dick sein, weiß nicht viel über ternäre Suchbäume und gab dem Link nur einen flüchtigen Blick). –
Ich denke, im Allgemeinen funktioniert es in einem x "beginnt mit" y Art und Weise. In der Praxis scheint dies jedoch so zu sein, dass alle Autocomplete-Funktionen, die ich jemals benutzt habe, funktionierten. –
fwiw eine Anzahl der Auto-Vervollständigen-Widgets Ich verwende alltägliche Übereinstimmung irgendwo in der Zeichenfolge; nichtsdestotrotz - nützlicher Link, also +1. –
Check out suffix array und suffix tree.
Mann, ich suche seit Jahren nach Ukkonens Algorithmus und wusste nie davon! Ich habe eine Anwendung, die eine effiziente Anpassung von Teilstrings mit Fehlern benötigt. Ich habe sogar in Foren wie diesem in der Vergangenheit gefragt und keine guten Hinweise bekommen. Du hast meinen Tag gerettet! – swestrup
@swestrup: Ich bin froh, dass ich Ihnen geholfen habe, diese Informationen zu verfolgen :) Sie sollten eine Kopie von * The Algorithm Design Manual *, http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp bekommen/1848000693/ref = sr_1_1? Ie = UTF8 & s = Bücher & qid = 1268325877 & sr = 8-1 es ist eine unschätzbare * Zusammenstellung * von Datenstrukturen, Algorithmen und Bibliographie/URLs Referenzen;) –
Wenn Sie Präfixe machen (was die meisten Autocomplets tun), dann ist auch ein ternärer Suchbaum das, was ich empfehlen würde. Wenn du allgemeine Infixe machst, dann gehe mit einem Suffixbaum, wie oben erwähnt.
Nein, es ist eine dumme Idee. Verwenden Sie Suffixbäume. Viel besser. – swestrup
Wenn es dumm ist, redigiere deine Antwort –
Als Alternative zu Suffix Arrays, Trees und Tries sehen Sie sich Directed Acyclic Word Graphs (DAWGs) und die Compressed-Variante (CDAWGs) an. Sie können in linearer Zeit erstellt werden, linearen Raum einnehmen und Teilstringsuche ermöglichen.
Mit einer komplizierteren Suchfunktion können Sie sogar eine begrenzte Anzahl von Platzhaltern unterstützen.
Ich habe eine Anwendung für genau das, was Sie wollen erstellt. Es ist der effizienteste Präfix-basierte Ranked-Autocomplete-Algorithmus um.
Wenn der Satz von der automatischen Vervollständigung Vorschläge ist Rang geordnet, ist ein SuggestTree eine gute Datenstruktur. Für jedes gegebene Präfix bietet es schnellen Zugriff auf die obersten k Vorschläge, die mit diesem Präfix beginnen.
http://en.wikipedia.org/wiki/Trie – frankc