autocompletar, papeles, estrategias, etc

Question

Me pregunto si alguien tiene buenos recursos para leer o código de experimentar para "autcomplete"

Me gustaría saber cuál es la teoría detrás de la terminación automática, por dónde empezar lo son los errores comunes, etc.

Me pareció fascinante la forma en que productos como Enso, Launchy, Google Chrome e incluso tcsh realizan su autocompletar, comencé mi auto por curiosidad y obtuve un código de muestra y llegué a la conclusión de que este debe ser un campo ampliamente explorado antes.

Agradecería que alguien comparta algún buen recurso técnico sobre cómo implementar esto.

Gracias de antemano.

Answer 1

• http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/ -
• http://social.msdn.microsoft.com/Forums/en-US/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b4b1/ - en el mundo .Net
• Un desagradable patente sobre el enfoque de autocompletar (posiblemente todavía vale la pena leer para la teoría ) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text-completion-algorithm para un alto nivel de discusión sobre las estrategias a tomar.

Answer 2

Salida este blog en la implementación de autocompletar usando GWT:

http://jroller.com/glongman/entry/gwt_autocompleter

Pero le recomiendo que empiece con algo muy simple por su cuenta para comprender cómo se realiza la aplicación. Empezaría con un Trie, tal vez incluso almacenado por completo en el cliente, luego pasaría a optimizarlo con las consultas del servidor si crees que son necesarias.

Answer 3

Autocomplete se implementa normalmente usando uno de los siguientes:

• árboles. Al indexar el texto que se puede buscar en una estructura en árbol (árbol de prefijos, árbol de sufijos, dawg, etc.) uno puede ejecutar búsquedas muy rápidas a expensas del almacenamiento de la memoria. El recorrido del árbol se puede adaptar para una coincidencia aproximada.
• Partición de patrón. Al dividir el texto en tokens (ngrams), se pueden ejecutar búsquedas de ocurrencias de patrones usando un simple esquema de hash.
• Filtrado. Encuentre un conjunto de posibles coincidencias y luego aplique un algoritmo secuencial para verificar cada candidato.

Un par de artículos sobre el tema:

• Bořivoj Melichar. Coincidencia aproximada de cadenas por autómatas finitos;
• Gonzalo Navarro. Una visita guiada a la coincidencia de cadenas aproximadas;
• Leonid Boytsov. Métodos de indexación para la búsqueda aproximada del diccionario: análisis comparativo;
• Marios Hadjieleftheriou y Divesh Srivastava.Procesamiento de cadena aproximado;
• Surajit Chaudhuri y Raghav Kaushik. Extendiendo la Autocompletación para Tolerar Errores;

Eche un vistazo a completely, una biblioteca de autocompletado de Java.