Autocomplete -Algorithmen, Papiere, Strategien usw.

Question

Ich frage mich, ob jemand gute Ressourcen hat, um zu lesen oder zu codieren, um für "automplete" zu experimentieren.

Ich würde gerne wissen, wie die Theorie hinter der Autoperation ist, wo man anfangen soll, was die Commonn -Fehler usw. sind usw.

Ich fand faszinierend, wie Produkte wie ENSO, Launchy, Google Chrome und sogar TCSH ihre automatische vollständige Ausführung von selbst ausführen, nur für Neugier ein Beispielcode und ich kam zu dem Schluss, dass dies ein Feld sein muss, das zuvor weit verbreitet ist.

Ich würde mich freuen, wenn jemand eine gute technische Ressource dafür teilt, wie dies implementiert werden soll.

Danke im Voraus.

Answer 1

• http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/ --
• http://social.msdn.microsoft.com/forums/en-us/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b1/ - in der .net-Welt
• EIN böse Patent zum Autocompletion -Ansatz (möglicherweise noch wert für die Lesen Theorie) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/fuzzy-text-completion-algorithm für eine hohe Diskussion über Strategien.

Answer 2

Schauen Sie sich dieses Blog zur Implementierung von AutoComplete mit GWT an:

http://jroller.com/glongman/entry/gwt_autocompleter

Aber ich würde Ihnen empfehlen, dass Sie zuerst mit etwas sehr Einfachem selbst beginnen, um zu verstehen, wie die Implementierung durchgeführt wird. Ich würde mit einem Trie beginnen, vielleicht sogar vollständig auf dem Client gespeichert und dann mit Serverabfragen optimiert werden, wenn Sie der Meinung sind, dass sie notwendig sind.

Answer 3

Autokaponete wird normalerweise mit einem der folgenden implementiert:

• Bäume. Durch Indizieren des durchsuchbaren Textes in einer Baumstruktur (Präfixbaum, Suffixbaum, Dawg usw.) kann man auf Kosten des Speicherspeichers sehr schnelle Suchanfragen ausführen. Der Baumtraversal kann für eine ungefähre Übereinstimmung angepasst werden.
• Musterpartitionierung. Durch die Aufteilung des Textes in Tokens (NGRAMS) kann man Suchvorgänge nach Mustervorkommen mit einem einfachen Hashing -Schema ausführen.
• Filterung. Suchen Sie eine Reihe potenzieller Übereinstimmungen und wenden Sie dann einen sequentiellen Algorithmus an, um jeden Kandidaten zu überprüfen.

Ein paar Papiere zu diesem Thema:

• Bořivoj Melichar. Ungefähre Zeichenfolge, die durch endliche Automaten angepasst wird;
• Gonzalo Navarro. Eine geführte Tour zur ungefähren String -Matching;
• Leonid Boytsov. Indexierungsmethoden für die ungefähre Suchen von Wörterbuch: Vergleichende Analyse;
• Marios Hadjieleftheriou und Divesh Srivastava. Ungefähre String -Verarbeitung;
• Surajit Chaudhuri und Raghav Kaushik. Ausdehnung der Autoperation, um Fehler zu tolerieren;

Sich ansehen vollständig, eine Java -Autoperete -Bibliothek.