optimization - Cómo implementar autocompletar en un conjunto de datos masivo

autocomplete

Question

Estoy tratando de implementar algo como Google sugieren en un sitio web que estoy construyendo y tengo curiosidad por saber cómo hacerlo en un gran conjunto de datos. Claro, si tienes 1000 elementos, guardas los elementos en la memoria caché y los recorres. ¿Pero cómo lo haces cuando tienes un millón de artículos? Además, supongamos que los elementos no son una sola palabra. Específicamente, me ha impresionado mucho Pandora.com. Por ejemplo, si busca "mojado" recupera "Arena húmeda" pero también recupera Toad The Wet Sprocket. Y su autocompletar es RÁPIDO. Mi primera idea fue agrupar los artículos con las dos primeras letras, por lo que tendría algo como:

Dictionary<string,List<string>>

donde la clave son las dos primeras letras. Está bien, pero ¿y si quiero hacer algo similar a Pandora y permitir que el usuario vea resultados que coincidan con la mitad de la cadena? Con mi idea: Wet nunca igualaría a Toad the Wet Sprocket porque estaría en el cubo "TO" en lugar del "WE". Entonces, tal vez podrías dividir la cuerda y "Toad the Wet Sprocket" entrar en los segmentos "TO", "WE" y "SP" (quitar la palabra "THE"), pero cuando hablas de un millón entradas que pueden tener que decir algunas palabras cada una posiblemente, parece que comenzaría rápidamente a usar mucha memoria. Ok, esa fue una pregunta larga. ¿Pensamientos?

Answer 1

Como señalé en Cómo implementar la búsqueda incremental en una lista , debe usar estructuras como Trie o Patricia para buscar patrones en textos grandes.

Y para descubrir patrones en medio de un texto, hay una solución simple. No estoy seguro de si es la solución más eficiente, pero generalmente lo hago de la siguiente manera.

Cuando inserto un texto nuevo en el Trie, simplemente lo inserto, luego elimino el primer carácter, inserto de nuevo, elimino el segundo carácter, lo inserto nuevamente ... y así sucesivamente hasta que se consuma todo el texto. Luego puede descubrir cada subcadena de cada texto insertado con solo una búsqueda desde la raíz. Esa estructura resultante se llama Suffix Tree y hay muchas optimizaciones disponibles.

Y es realmente increíble rápido. Para encontrar todos los textos que contienen una secuencia dada de n caracteres, debe inspeccionar como máximo n nodos y realizar una búsqueda en la lista de elementos secundarios para cada nodo. Dependiendo de la implementación (matriz, lista, árbol binario, lista de omisiones) de la colección de nodos secundarios, es posible que pueda identificar el nodo secundario requerido con solo 5 pasos de búsqueda asumiendo letras latinas insensibles a mayúsculas y minúsculas. La ordenación por interpolación puede ser útil para alfabetos y nodos grandes con muchos niños, como los que se encuentran generalmente cerca de la raíz.

Answer 2

He creado AutoCompleteAPI para este escenario exactamente.

Regístrese para obtener un índice privado, luego, Cargue sus documentos.

Carga de ejemplo usando curl en el documento "Nueva York":

curl -X PUT -H "Content-Type: application/json" -H "Authorization: [YourSecretKey]" -d ''{
"key": "New York",
"input": "New York"
}'' "http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]"

Después de indexar todo el documento, para obtener sugerencias de autocompletar, use:

http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]?prefix=new

Puede usar cualquier biblioteca de autocompletado del cliente para mostrar estos resultados al usuario.

Answer 3

Mantiene los elementos en el lado del servidor (quizás en un DB, si el conjunto de datos es realmente grande y complejo) y envía llamadas AJAX desde el navegador del cliente que devuelven los resultados usando json / xml. Puede hacerlo en respuesta a la escritura del usuario o con un temporizador.

Answer 4

No está relacionado algorítmicamente con lo que está preguntando, pero asegúrese de tener un retraso de 200ms o más (lag) después de los kaypress (es) para asegurarse de que el usuario haya dejado de escribir antes de emitir la solicitud asincrónica. De esta forma, reducirá las solicitudes HTTP redundantes al servidor.

Answer 5

No intente implementarlo usted mismo (a menos que sea curioso). Usa algo como Lucene o Endeca: te ahorrará tiempo y cabello.

Answer 6

Utilizaría algo Trie un Trie , y Trie que el valor de cada nodo hoja sea una lista de las posibilidades que contienen la palabra representada por el nodo hoja. Puede ordenarlos por orden de probabilidad, o dinámicamente clasificarlos / filtrarlos según otras palabras que el usuario haya ingresado en el cuadro de búsqueda, etc. Se ejecutará muy rápidamente y en una cantidad razonable de RAM.

Answer 7

si no quiere un trie y quiere cosas del medio de la cuerda, generalmente quiere ejecutar algún tipo de función de distancia de edición (distancia levenshtein) que le dará un número que indica qué tan bien coinciden 2 cuerdas. no es un algoritmo particularmente eficiente, pero no importa demasiado para cosas como palabras, ya que son relativamente cortas. Si está ejecutando comparaciones en cadenas de 8000 caracteres, probablemente demore unos segundos. Sé que la mayoría de los idiomas tienen una implementación, o puede encontrar código / pseudocódigo para ello con bastante facilidad en Internet.