java - usando - prediccion en netbeans

Autocompletar la implementación del lado del servidor.

Question

¿Cuál es una manera rápida y eficiente de implementar el componente del lado del servidor para una función de autocompletar 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 nuestra interfaz web, y las terminaciones se muestran en un menú desplegable potenciado por ajax. Los datos contra 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 tailset se usa para proporcionar coincidencias adicionales más allá de la coincidencia más cercana. El problema con esta solución es que no se escala. Actualmente se está ejecutando contra el límite de espacio de almacenamiento de VM (he establecido -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 funciones. Cambiar a máquinas virtuales de 64 bits en máquinas con más memoria no es una opción inmediata.

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

Ediciones:

@Gandalf: Para nuestro caso de uso, es importante que el autocompletado sea integral y no solo sea una ayuda adicional para el usuario. En cuanto a lo que estamos completando, es una lista de pares de tipo de concepto. Por ejemplo, las posibles entradas son [("Microsoft", "Software Company"), ("Jeff Atwood", "Programmer"), ("StackOverflow.com", "Website")]. Estamos utilizando a Lucene para la búsqueda completa una vez que el usuario selecciona un elemento de la lista de autocompletar, pero aún no estoy seguro de que Lucene funcione bien para el autocompletado en sí.

@Glen: No se están utilizando bases de datos aquí. Cuando hablo de una tabla, 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 gran cantidad de memoria en realidad era 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

¿Hay posibles soluciones que me permitan escalar mejor?

Sí, Oracle. Esto es algo para lo que se construyen las bases de datos. Solo indexa las columnas relevantes. Si se está ejecutando contra la pared de soluciones en memoria, entonces la compensación con el tiempo de búsqueda del disco o la latencia de la red es probablemente discutible. Especialmente si inserta una capa de caché en el medio.

Además, puede reducir el número de visitas si modifica un poco su código del lado del cliente. Como establecer un número mínimo de caracteres de tipo antes de ejecutar una consulta o establecer una fracción de segundo de retraso después de que el usuario deja de escribir. Si ya los estás usando, configúralos un poco más alto.

Answer 2

Con un conjunto tan grande, intentaría algo como un índice de Lucene para encontrar los términos que desea, y establecer una tarea de temporizador que se reinicie después de cada golpe de tecla, con un retraso de .5 segundos. De esta manera, si un usuario escribe varios caracteres rápidamente, no consulta el índice en cada trazo, solo cuando el usuario hace una pausa por un segundo. Las pruebas de utilidad le permitirán saber cuánto tiempo debe durar esa 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 configuran los términos de la consulta, el Índice de Lucene se puede crear previamente y optimizar.

Answer 3

He hecho esto para pequeños conjuntos de datos utilizando un árbol de búsqueda ternario . El código DDJ no es demasiado difícil de convertir a Java, pero asume que todo el conjunto de datos cabrá en la memoria. Hay implementaciones en el disco de los árboles de búsqueda de Ternary ( here hay uno en Python), pero por supuesto van a tener menos rendimiento. Sin embargo, dado que los árboles de búsqueda ternarios sobresalen en las coincidencias parciales, el rendimiento puede ser adecuado para sus necesidades.

Answer 4

Para aquellos que se topan con esta pregunta ...

Acabo de publicar una implementación de autocompletado del lado del servidor en Google Code. El proyecto incluye una biblioteca java que se puede integrar en aplicaciones existentes y un servidor autocompletado HTTP AJAX independiente.

Mi esperanza es que las personas puedan incorporar autocompletar eficientemente en sus aplicaciones. Patea los neumáticos!

Answer 5

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

¿Qué DB estás usando?

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

MySQL también afirma tener algunas capacidades de memoria, pero no sé mucho sobre MySQL.

Luego puede eliminar su caché basado en Java, o puede usar el caché para las búsquedas más populares / recientes.

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

Si la búsqueda de disco lo está ralentizando, entonces podría investigar el uso de unidades SSD para acelerar sus lecturas.

Answer 6

Tal vez entendí mal tu pregunta, pero ¿no pudiste usar un complemento de JQuery para Ajax la información de tu aplicación?

He usado este antes

Ajax Auto Suggest v2

Answer 7

Tenía un requisito similar.

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

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

Esta es una solución para grandes conjuntos de datos que no puede almacenar en el cliente y funciona bastante rápido (la búsqueda no almacenada en caché siempre se recuperó en 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 puede jugar con el almacenamiento en caché de solo los resultados más utilizados en el cliente, especialmente si ya lo ha implementado. En mi caso, la solución del lado del servidor es lo suficientemente rápida y los tiempos de carga de los clientes son lo suficientemente lentos, por lo que no está justificado.

PD: una consulta del cliente solo cuando el usuario hace una pausa por un cierto tiempo para evitar búsquedas repetidas, como se sugiere, es una buena solución. En mi cliente, solicito la base de datos solo después de que se ingresan los primeros tres caracteres, ya que menos que eso devuelve demasiados resultados en todos los casos.

Answer 8

Terminé resolviendo este a través de Lucene; Las pruebas de rendimiento iniciales parecen suficientes para nuestro caso de uso. Fue necesario un poco de piratería para hacer que las consultas de prefijo funcionaran, ya que estaba ejecutando la excepción TooManyClauses al expandir consultas como "Jeff At *". Terminé envolviendo mi IndexReader con un FilterIndexReader, y puse el límite máximo en el número 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 9

Usé hashtable y mmap () y más de 10,000,000 registros de lista de términos no es un problema. Vea la demostración aquí: http://olegh.ath.cx/autocomplete.html

Answer 10

use la estructura de datos de trie aquí es el wiki Trie