Back-End für Auto-Vervollständigung

Question

Dies ist eine Interviewfrage: Entwerfen Sie ein verteiltes Back-End für die automatische Vervollständigung.

Ich würde es wie folgt beantworten:

Auto-complete eine Suche in einem Wörterbuch von einem bestimmten Suffix ist. Das Wörterbuch sollte wahrscheinlich als Trie organisiert sein. Das Wörterbuch ist aus den häufigsten Abfragen aufgebaut, aber es ist eine andere Geschichte.

Nun gehe ich davon aus, dass das Wörterbuch nicht häufig geändert wird (z. B. einmal am Tag statt in jeder Millisekunde). Daher können wir das Wörterbuch nur auf eine Reihe von Servern replizieren, die Abfragen zur automatischen Vervollständigung durchführen (z. B. mit einer Load-Balancer- und Round-Robin-Richtlinie).

Wir sollten auch über Wörterbuch nachdenken, aber das ist auch eine andere Geschichte.

Macht es Sinn? Fehle ich etwas?

Answer 1

Es sieht wie die richtige Frage aus. Die Idee ist wirklich nett und würde Ihnen helfen, in log(n) zu suchen. Die Änderungshäufigkeit hängt von der Information ab, also würde ich nicht genau Zeit sagen, aber ich würde sie dynamisch einstellen. Nehmen wir an, dass Sie sich einmal am Tag ändern, es wäre schön, wie sehr sich der Baum verändert hat. Und Sie können eine Grenze angeben (zum Beispiel 10%). Wenn die Grenze überschritten wird, können Sie den Trie öfter aktualisieren. Es kommt auch darauf an, wie wichtig es ist, auf dem neuesten Stand zu sein, denn in den meisten Fällen ist dies nicht der Fall. Die Load-Balancer-Idee ist ebenfalls gut.

Answer 2

Werfen Sie einen Blick auf, was SOLR 4.0 (Solr hat Trie und ist verteilt). Es hängt stark davon ab, wie sie die automatische Vervollständigung zu arbeiten erwarten. Wenn es nur ein wild card filter als etwas wie ein Trie ist, wird für einfaches ASCII gut sein ... sonst wird es komplizierter, wenn sie Autokorrektur wollen. Davon abgesehen bezweifle ich, dass ein Trie Ihnen gute Ergebnisse bringen wird, wenn es ein generisches Feld ist (dh keine SKU oder spezialisierte ID), sonst haben Sie einen monströs großen und ineffizienten Trie.

Werfen Sie einen Blick auf:

• speziell auf seine Suggester aussehen: http://wiki.apache.org/solr/Suggester
• und Analysatoren der Solr: http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters
  • Noch mehr spezifisch: http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters#solr.EdgeNGramFilterFactory