Back-end per completamento automatico

Question

Questa è una domanda di intervista: progettare un back-end distribuito per il completamento automatico.

vorrei rispondere come segue:

completamento automatico è una ricerca in un dizionario da un determinato suffisso. Probabilmente il dizionario dovrebbe essere organizzato come trie. Il dizionario è costruito dalle domande più frequenti, ma è un'altra storia.

Ora presumo che il dizionario non venga modificato di frequente (ad esempio una volta al giorno anziché ogni millisecondo). Quindi possiamo semplicemente replicare il dizionario su un numero di server che gestiscono le query di completamento automatico (ad esempio con un bilanciamento del carico e un criterio round-robin).

Dovremmo anche pensare al dizionario ma questa è anche un'altra storia.

Ha senso? Mi sto perdendo qualcosa?

Answer 1

Sembra la domanda giusta. L'idea del trie è davvero carina e ti aiuterebbe a cercare in log(n). La frequenza del cambiamento dipende dalle informazioni, quindi non direi esattamente il tempo, ma lo sintonizzerei dinamicamente .. Supponiamo che cambi una volta al giorno, sarebbe bello quanto l'albero è cambiato. E puoi dare un confine (per esempio il 10%). Se il limite viene superato è possibile aggiornare più spesso il trie. Dipende anche da quanto è importante essere aggiornati, perché nella maggior parte dei casi non lo è. Anche l'idea del bilanciamento del carico è buona.

Answer 2

Dai un'occhiata a cosa SOLR 4.0 (solr ha trie's ed è distribuito). È altamente dipendente dal modo in cui si prevede che il completamento automatico funzioni. Se è solo un wild card filter di qualcosa come un trie andrà bene per ASCII semplice ... altrimenti diventa più complicato se vogliono la correzione automatica. Detto questo, dubito che un trie ti ottenga buoni risultati se è un campo generico (cioè non uno SKU o un ID specializzato) altrimenti avrai un trie mostruosamente grande e inefficiente.

Date un'occhiata a:

• particolare guardare la sua Suggester: http://wiki.apache.org/solr/Suggester
• e analizzatori di Solr: http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters
  • Ancora più precisamente: http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters#solr.EdgeNGramFilterFactory