tipos programacion orientada ordenamiento objetos metodos metodo lenguaje ejemplos dev dela datos burbuja algoritmos abstractos c++ c algorithm search autocomplete

c++ - programacion - tipos de datos abstractos en java



Cuál es el mejor algoritmo de autocompletar/sugerir, estructura de datos (5)

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 recuperación rápida de un conjunto de resultados finitos a medida que el usuario ingresa. Primero consideremos que para buscar "ciencias de la computación" puede comenzar a escribir desde "computadora" o "ciencia" pero no con "computadora". 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 está involucrada la sugerencia 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.

Vemos Google, Firefox, algunas páginas AJAX muestran una lista de elementos probables mientras el usuario escribe los caracteres.

¿Alguien puede dar un buen algoritmo, estructura de datos para implementar autocompletar?

Para una solución simple: generas un ''candidato'' con una distancia mínima de edición ( Levenshtein ) (1 o 2) luego pruebas la existencia del candidato con un contenedor hash (el conjunto será suficiente para una simple solución, luego usa el unordered_set del tr1 o boost).

Ejemplo: escribió carr y quiere coche. arr es generado 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, hay inserción, borrado, transposición, etc.

Usted ve que su algoritmo para generar candidatos es realmente donde está perdiendo el tiempo, especialmente si tiene un muy poco conjunto desordenado .

Si desea sugerir las terminaciones más populares, un "Árbol de sugerencias" puede ser una buena opción: Sugerir árbol

Un trie es una estructura de datos que se puede usar para encontrar rápidamente palabras que coincidan con un prefijo.

Editar: Aquí hay un ejemplo que muestra cómo usar uno para implementar autocompletar http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Aquí hay una comparación de 3 implementaciones diferentes de autocompletar (aunque está 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 ++.