autocompletar aplicación del lado del servidor

Question

¿Cuál es una manera rápida y eficiente para implementar el componente del lado del servidor para una función de autocompletado en un cuadro de entrada html?

Estoy escribiendo un servicio para autocompletar las consultas de los usuarios en el cuadro de búsqueda principal de la interfaz web, y las terminaciones se muestran en un menú desplegable impulsado por Ajax. Los datos con los que estamos ejecutando consultas son simplemente una gran tabla de conceptos que nuestro sistema conoce, que coincide aproximadamente con el conjunto de títulos de páginas de wikipedia. Para este servicio, obviamente, la velocidad es de suma importancia, ya que la capacidad de respuesta de la página web es importante para la experiencia del usuario.

La implementación actual simplemente carga todos los conceptos en la memoria en un conjunto ordenado, y realiza una simple búsqueda de registro (n) en una pulsación de tecla del usuario. El tail tail se usa para proporcionar coincidencias adicionales más allá de la coincidencia más cercana. El problema con esta solución es que no escala. Actualmente se está ejecutando en contra del límite de espacio de almacenamiento dinámico de la máquina virtual (he configurado -Xmx2g, que es lo máximo que podemos impulsar en nuestras máquinas de 32 bits), y esto nos impide expandir nuestra tabla de conceptos o agregar más funcionalidades. Cambiar a máquinas virtuales de 64 bits en máquinas con más memoria no es una opción inmediata.

He dudado en comenzar a trabajar en una solución basada en disco, ya que me preocupa que el tiempo de búsqueda de disco mate el rendimiento. ¿Hay posibles soluciones que me permitan escalar mejor, ya sea completamente en memoria o con algunas implementaciones rápidas respaldadas por disco?

ediciones:

@Gandalf: Para nuestro caso de uso es importante que el de la terminación automática es integral y no es simplemente ayuda adicional para el usuario. En cuanto a lo que estamos completando, es una lista de pares de conceptos conceptuales. Por ejemplo, las posibles entradas son [("Microsoft", "Compañía de software"), ("Jeff Atwood", "Programador"), ("StackOverflow.com", "Sitio web")]. Estamos utilizando Lucene para la búsqueda completa una vez que el usuario selecciona un elemento de la lista de autocompletar, pero todavía no estoy seguro de que Lucene funcione bien para la autocompleta.

@Glen: No hay bases de datos están siendo utilizados aquí. Cuando estoy hablando de una tabla solo me refiero a la representación estructurada de mis datos.

@Jason Day: Mi implementación original para este problema fue usar un Trie, pero la saturación de memoria con eso era en realidad peor que el conjunto ordenado debido a la necesidad de una gran cantidad de referencias de objetos. Leeré en los árboles de búsqueda ternarios para ver si podría ser de utilidad.

Answer 1

Con un conjunto tan grande probaría algo así como un índice Lucene para encontrar los términos que desea, y establecer una tarea de temporizador que se restablece después de cada golpe de tecla, con un retraso de .5 segundos. De esta forma, si un usuario escribe múltiples caracteres rápidamente, no consulta el índice en cada pasada, solo cuando el usuario hace una pausa por un segundo. Las pruebas de usabilidad le permitirán saber cuánto tiempo debe ser la pausa.

Timer findQuery = new Timer(); 
... 
public void keyStrokeDetected(..) { 
    findQuery.cancel(); 
    findQuery = new Timer(); 
    String text = widget.getEnteredText(); 
    final TimerTask task = new TimerTask() { 
     public void run() { 
     ...query Lucene Index for matches 
     } 
    }; 
    findQuery.schedule(task, 350); //350 ms delay 
} 

Algunos pseduocode allí, pero esa es la idea. Además, si se establecen los términos de la consulta, el índice de Lucene se puede precrear y optimizar.

Answer 2

Si no puede cargar físicamente todos los datos en la RAM, entonces vamos a tener que lidiar con tener algunos en el disco.

¿Qué DB estás usando?

Por ejemplo, Oracle tiene una opción donde puede mantener toda la tabla en la memoria y realizar sus consultas en contra de eso.

MySQL también afirma que tiene algunas capacidades de memoria, pero no sé mucho acerca de MySQL.

continuación, puede acabar con su caché basada en Java, o puede utilizar la caché para las búsquedas más populares/recientes.

Obviamente cuando se queda sin memoria RAM, algunos de los datos estarán en el disco cuando los consulta, pero dependiendo de la carga en el sistema, esto solo será un problema para la primera pulsación de tecla, no los siguientes , ya que la fila estará en la memoria después de eso.

Si el disco busca le está desacelerando, entonces se podría investigar el uso de las unidades SSD para acelerar su lecturas.

Answer 3

Tenía un requisito similar.

Utilicé la base de datos relacional con una sola tabla sintética bien indexada (evitando uniones y vistas para acelerar las búsquedas), y la memoria caché en la memoria (Ehcache) para almacenar las entradas más utilizadas.

Al utilizar MRU caché podrá tener tiempos de respuesta instantáneos para la mayoría de las búsquedas, y probablemente no haya nada que pueda vencer a la base de datos relacional al acceder a la columna indexada en una gran tabla almacenada en el disco.

Esta es la solución para grandes conjuntos de datos no se puede almacenar en el cliente y funciona bastante rápido (de búsqueda en caché no siempre fue recuperado menos de 0,5 segundos en mi caso). También es escalable horizontalmente: siempre puede agregar servidores adicionales y servidores de bases de datos.

También se puede jugar con el almacenamiento en caché de sólo los resultados más utilizado en el cliente, sobre todo si ya se ha implementado. En mi caso, la solución del lado del servidor es lo suficientemente rápida, y los tiempos de carga del cliente son lo suficientemente lentos como son, por lo que no está garantizado.

P.S. Hacer una consulta al cliente solo cuando el usuario hace una pausa durante un cierto período de tiempo para evitar repetidas búsquedas como se sugiere es una buena solución. En mi cliente, consulto la base de datos solo después de que se ingresan los tres primeros caracteres, ya que menos de eso arroja demasiados resultados en todas las instancias.

Answer 4

Tal vez no he entendido bien su pregunta, pero no podía usar un plugin de jQuery Ajax a la información para su aplicación?

he utilizado esto antes:

Ajax Auto Suggest v2

Answer 5

He hecho esto para los pequeños conjuntos de datos utilizando una Ternary search tree. El código DDJ no es demasiado difícil de convertir a Java, pero supone que todo el conjunto de datos encajará en la memoria. Hay implementaciones en disco de los árboles de búsqueda de Ternary (here es uno en python), pero, por supuesto, van a ser menos efectivos. Sin embargo, dado que los árboles de búsqueda ternarios se destacan en las coincidencias parciales, el rendimiento puede ser adecuado para sus necesidades.

Answer 6

¿Existen posibles soluciones que me deja escalan mejor

Sí, Oracle. Esto es algo para lo que las bases de datos están diseñadas. Simplemente indexe las columnas relevantes. Si se está ejecutando contra la pared de soluciones en memoria, entonces la compensación con el tiempo de búsqueda de disco o la latencia de la red probablemente sea irrelevante. Especialmente si inserta una capa de almacenamiento en caché en el medio.

También, puede ser capaz de disminuir el número de visitas si ajustar su código de cliente un poco. Como establecer un número mínimo de caracteres de tipo antes de ejecutar una consulta o establecer una fracción de segundo después de que el usuario deja de escribir.Si ya los está usando, configúrelos un poco más.

Answer 7

Terminé resolviendo este a través de Lucene; las pruebas iniciales de rendimiento parecen suficientes para nuestro caso de uso. Se necesitaba una pequeña piratería para hacer que las consultas de prefijo funcionasen, ya que me estaba ejecutando la excepción TooManyClauses al expandir consultas como "Jeff at *". Terminé envolviendo mi IndexReader con FilterIndexReader, y establecí un límite máximo en la cantidad de términos devueltos en una llamada de término de prefijo. Aquí está mi código:

Directory directory = FSDirectory.getDirectory(indexDir); 
IndexReader reader = IndexReader.open(directory); 
FilterIndexReader filteredReader = new FilterIndexReader(reader) { 
    @Override public TermEnum terms(Term t) throws IOException { 
    final TermEnum origEnum = super.terms(t); 

    return new TermEnum() { 
     protected int count = 0; 
     @Override public boolean next() throws IOException { 
     if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) 
      return origEnum.next(); 
     else return false; 
     } 

     @Override public Term term() { 
     return origEnum.term(); 
     } 

     @Override public int docFreq() { 
     return origEnum.docFreq(); 
     } 

     @Override public void close() throws IOException { 
     origEnum.close(); 
     } 
    }; 
    } 
}; 

IndexSearcher searcher = new IndexSearcher(filteredReader); 

Answer 8

Para los que se tropiezan con esta pregunta ...

solo he publicado un server-side autocomplete implementation en Google Code. El proyecto incluye una biblioteca de Java que se puede integrar en aplicaciones existentes y un servidor de autocompletado HTTP AJAX independiente.

Mi esperanza es que permita a las personas incorporar la autocompletación eficiente en sus aplicaciones. Patea los neumáticos!

Answer 9

Utilicé hashtable y mmap() Y la lista de términos con más de 10.000.000 de registros no es problema. Ver demostración aquí: http://olegh.ath.cx/autocomplete.html

Answer 10

estructura de datos trie uso aquí es el wiki http://en.wikipedia.org/wiki/Trie