Vemos Google, Firefox algunas páginas de AJAX muestran una lista de elementos probables mientras los tipos de usuario escriben caracteres.Cuál es el mejor algoritmo de autocompletar/sugerir, estructura de datos [C++/C]
¿Alguien puede dar un buen algoritmo, estructura de datos para implementar autocompletar?
A trie es una estructura de datos que se puede utilizar para encontrar rápidamente palabras que coincidan con un prefijo.
Edición: He aquí un ejemplo que muestra cómo utilizar uno para implementar autocompletar http://rmandvikar.blogspot.com/2008/10/trie-examples.html
He aquí una comparación de diferentes 3 auto-complete implementations (aunque es en Java no en C++).
* In-Memory Trie
* In-Memory Relational Database
* Java Set
Al buscar claves, el trie es marginalmente más rápido que la implementación del conjunto. Tanto el trie como el set son un poco más rápidos que la solución de base de datos relacional.
El costo de instalación del conjunto es menor que la solución Trie o DB. Tendría que decidir si construiría nuevos "conjuntos de palabras" con frecuencia o si la velocidad de búsqueda es la prioridad más alta.
Estos resultados están en Java, su kilometraje puede variar con una solución de C++.
Para una solución sencilla: se genera un 'candidato' con una edición mínima (Levenshtein) distancia (1 o 2) a continuación, se prueba la existencia del candidato con un recipiente de almohadilla (conjunto será suficiente para un simple Soltion , luego use unordered_set desde tr1 o boost).
Ejemplo: Has escrito carr y quieres coche. arr se genera por 1 eliminación. ¿Está en su conjunto desordenado? No. crr es generado por 1 eliminación. ¿Está crr en tu conjunto desordenado? No. coche es generado por 1 eliminación. ¿Está el automóvil en su conjunto desordenado? Sí, tú ganas.
Por supuesto que hay inserción, deleción, transposición, etc ...
ve que su algoritmo para generar candidatos es realmente donde estás perdiendo el tiempo, especialmente si usted tiene un muy poco unordered_set.
Para grandes conjuntos de datos, un buen candidato para el backend serían los árboles de búsqueda de Ternary. Combinan lo mejor de dos mundos: la baja sobrecarga de espacio de los árboles de búsqueda binarios y la eficiencia de tiempo basada en caracteres de los intentos de búsqueda digital.
Ver en el Dr. Dobbs Journal: http://www.ddj.com/windows/184410528
El objetivo es la rápida recuperación de un conjunto de resultados finitos como el usuario teclea Vamos a considerar en primer lugar que para buscar "la informática", se puede empezar a escribir de "ordenador". o "ciencia" pero no "omputer". Entonces, dada una frase, genere las sub-frases comenzando con una palabra. Ahora, para cada una de las frases, introdúzcalas en el TST (árbol de búsqueda ternario). Cada nodo en el TST representará un prefijo de una frase que se haya tipeado hasta ahora. Almacenaremos los mejores 10 (por ejemplo) resultados para ese prefijo en ese nodo. Si hay muchos más candidatos que la cantidad finita de resultados (10 aquí) para un nodo, debe haber una función de clasificación para resolver la competencia entre dos resultados.
El árbol se puede construir cada pocas horas, dependiendo del dinamismo de los datos.Si los datos están en tiempo real, entonces supongo que algún otro algoritmo dará un mejor equilibrio. En este caso, el requisito absoluto es la recuperación de los resultados al instante para cada pulsación de teclado que hace muy bien.
Surgirán más complicaciones si se trata de sugerencias de correcciones ortográficas. En ese caso, los algoritmos de distancia de edición tendrán que ser considerados también.
Para pequeños conjuntos de datos como una lista de países, una simple implementación de Trie servirá. Si va a implementar un menú desplegable de autocompletar en una aplicación web, el widget de autocompletar de YUI3 hará todo por usted una vez que haya proporcionado los datos en una lista. Si usa YUI3 como interfaz para un autocompletado respaldado por datos grandes, cree los servicios web basados en TST en C++ y luego use el origen de datos del nodo de script del widget de autocompletar para obtener datos del servicio web en lugar de una lista simple.
Si desea sugerir las terminaciones más populares, un "Sugerir árbol" puede ser una buena opción: Suggest Tree
Segment trees se puede utilizar para implementar eficientemente auto complete
Poco relacionado es descripción de Peter Norvig de Google cómo hacer la corrección ortográfica: http://norvig.com/spell-correct.html –
Un Trie estándar requiere mucha memoria, para los sets más grandes que desea usar un Trie Compactado que reduce enormemente la huella de memoria. Las optimizaciones adicionales incluyen la inicialización diferida de los valores de nodo y las estructuras de datos correctas para los conjuntos de valores/hijos. Hace un tiempo, creé una [biblioteca de autocompletar] (https://github.com/fmmfonseca/completely) capaz de manejar conjuntos de datos muy grandes (10,000,000+) y responde eficientemente búsquedas exactas y aproximadas. –