Was ist der beste Autocomplete/Suggest-Algorithmus, Datenstruktur [C++/C]

Wir sehen Google, Firefox, einige AJAX-Seiten zeigen eine Liste wahrscheinlicher Elemente, während der Benutzer Zeichen eingibt.

Kann jemand einen guten Algorithmus und eine Datenstruktur für die Implementierung der automatischen Vervollständigung angeben?

EIN versuchen ist eine Datenstruktur, die verwendet werden kann, um schnell Wörter zu finden, die mit einem Präfix übereinstimmen.

Bearbeiten: Hier ist ein Beispiel, das zeigt, wie man eine verwendet, um die automatische Vervollständigung zu implementieren http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Hier ist ein Vergleich von 3 verschiedenen Auto-Complete-Implementierungen (obwohl es in Java nicht C++ ist).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

Beim Nachschlagen von Schlüsseln ist der Trie geringfügig schneller als die Set-Implementierung. Sowohl der Trie als auch der Set sind ein gutes Stück schneller als die relationale Datenbanklösung.

Die Einrichtungskosten des Sets sind geringer als bei der Trie- oder DB-Lösung. Sie müssten entscheiden, ob Sie häufig neue “Wortsätze” erstellen oder ob die Suchgeschwindigkeit die höhere Priorität hat.

Diese Ergebnisse sind in Java, Ihr Kilometerstand kann mit einer C++-Lösung variieren.

Für große Datensätze wären ternäre Suchbäume ein guter Kandidat für das Backend. Sie vereinen das Beste aus zwei Welten: den geringen Platzverbrauch binärer Suchbäume und die zeichenbasierte Zeiteffizienz digitaler Suchversuche.

Siehe im Dr. Dobbs Journal: http://www.ddj.com/windows/184410528

Das Ziel ist das schnelle Abrufen einer endlichen Ergebnismenge, wenn der Benutzer eintippt. Betrachten wir zunächst, dass Sie für die Suche nach “Informatik” mit der Eingabe von “Computer” oder “Wissenschaft” beginnen können, aber nicht von “Computer”. Generieren Sie also bei einem gegebenen Satz die Untersätze, die mit einem Wort beginnen. Geben Sie nun jeden der Sätze in den TST (ternären Suchbaum) ein. Jeder Knoten im TST stellt ein Präfix eines bisher eingegebenen Satzes dar. Wir werden die besten 10 (sagen wir) Ergebnisse für dieses Präfix in diesem Knoten speichern. Wenn es viel mehr Kandidaten als die endliche Anzahl von Ergebnissen (hier 10) für einen Knoten gibt, sollte es eine Ranking-Funktion geben, um den Wettbewerb zwischen zwei Ergebnissen aufzulösen.

Der Baum kann je nach Dynamik der Daten einmal alle paar Stunden aufgebaut werden. Wenn die Daten in Echtzeit vorliegen, wird ein anderer Algorithmus vermutlich für eine bessere Balance sorgen. In diesem Fall ist die absolute Anforderung das blitzschnelle Abrufen von Ergebnissen für jeden getippten Tastendruck, was sehr gut funktioniert.

Weitere Komplikationen ergeben sich, wenn es um den Vorschlag von Rechtschreibkorrekturen geht. In diesem Fall müssen auch die Entfernungsalgorithmen berücksichtigt werden.

Für kleine Datensätze wie eine Liste von Ländern reicht eine einfache Implementierung von Trie aus. Wenn Sie ein solches Autocomplete-Dropdown in einer Webanwendung implementieren, erledigt das Autocomplete-Widget von YUI3 alles für Sie, nachdem Sie die Daten in einer Liste bereitgestellt haben. Wenn Sie YUI3 nur als Frontend für eine Autovervollständigung verwenden, die von großen Daten unterstützt wird, erstellen Sie die TST-basierten Webdienste in C++ und verwenden Sie dann die Skriptknoten-Datenquelle des Autovervollständigungs-Widgets, um Daten vom Webdienst anstelle einer einfachen Liste abzurufen.

Bäume segmentieren können zur effizienten Umsetzung genutzt werden automatisch vervollständigen

Wenn Sie die beliebtesten Vervollständigungen vorschlagen möchten, ist ein “Vorschlagsbaum” möglicherweise eine gute Wahl:
Baum vorschlagen

Für eine einfache Lösung: Sie generieren einen “Kandidaten” mit einer minimalen Bearbeitung (Levenshtein) Distanz (1 oder 2) dann testen Sie die Existenz des Kandidaten mit einem Hash-Container (einstellen reicht für eine einfache Lösung, dann verwenden unordered_set von tr1 oder boost).

Beispiel: Du hast carr geschrieben und willst car. arr wird durch 1 Löschung generiert. Ist arr in deinem unordered_set ? Nr. crr wird durch 1 Löschung generiert. Ist crr in Ihrem unordered_set ? Nr. Auto wird durch 1 Löschung generiert. Ist Auto in Ihrem unordered_set ? Ja, du gewinnst.

Natürlich gibt es Einfügungen, Löschungen, Transpositionen usw.

Sie sehen, dass Ihr Algorithmus zur Generierung von Kandidaten wirklich Zeit verschwendet, besonders wenn Sie nur sehr wenig Zeit haben unordered_set.