¿Cuál es la mejor solución de código abierto para implementar el autocompletado rápido?

Investigué mucho sobre esto hace unos años y no pude encontrar una buena biblioteca de autocompletado de código abierto. Si alguien pudiera escribir una buena biblioteca para este código abierto, creo que sería un gran beneficio para la comunidad.

Una buena biblioteca de autocompletado de código abierto:

  1. ser eficiente (por ejemplo, una biblioteca eficiente de trie probablemente escrita en C / C ++)
  2. admite escala de datos (por ejemplo, divide las consultas en varios servidores)
  3. apoyar un mecanismo de actualización en tiempo real

Las bibliotecas de búsqueda de código abierto actuales carecen de varias de estas características:

  • Lucene / Solr (carece de 1, admite 2, admite pero con frecuencia se rompe en 3)
  • Esfinge (admite 1 y 2, carece de 3)

La mayoría de las grandes compañías web han escrito una implementación personalizada internamente (Facebook, Google, Yahoo, Quora). Para aplicaciones pequeñas como una búsqueda wiki interna de la empresa, he visto a varias grandes empresas web usar Solr para su backend de autocompletado.

Escribí un artículo sobre cómo hacer autocompletar usando CouchDB: http://blog.couchone.com/post/23

Se inspiró en un artículo similar de Salvatore sobre cómo implementar el autocompletado usando Redis: http://antirez.com/post/autocomp

Ninguno de estos es exactamente plug and play, pero si los lee, verá en qué se convierten algunas de las preguntas de diseño. Por ejemplo: la solución de Redis es aproximada, CouchDB es exacta. Ambos se escalan de manera diferente según el tamaño del corpus frente a los recuentos de cada término.

Al final, algo dedicado al texto completo como Lucene o Sphinx probablemente será el más rápido, pero para muchos casos de uso, las soluciones CouchDB o Redis son lo suficientemente rápidas.

La biblioteca de código abierto LingPipe ofrece funcionalidad de autocompletar. Se basa en: (1) un modelo de lenguaje, (2) búsqueda A *, (3) un árbol de prefijos.

Una cosa interesante es que puede corregir errores en las cadenas de prefijos, como en este ejemplo de autocompletado de Google: http://bit.ly/cVbTJY .