¿Cuál es el mejor algoritmo de autocompletar/sugerir, estructura de datos? [C++/C]

4 minutos de lectura

¿Cual es el mejor algoritmo de autocompletarsugerir estructura de datos
Subbul

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

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

¿Cual es el mejor algoritmo de autocompletarsugerir estructura de datos
Cañada

A probar es una estructura de datos que se puede utilizar para encontrar rápidamente palabras que coincidan con un prefijo.

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

Aquí hay una comparación de 3 diferentes implementaciones 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 de Set. 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 Set es más bajo que el de la solución Trie o DB. Tendría que decidir si estaría construyendo nuevos “conjuntos de palabras” con frecuencia o si la velocidad de búsqueda es la mayor prioridad.

Estos resultados están en Java, su kilometraje puede variar con una solución de C++.

  • Algo relacionado está la descripción de Peter Norvig de Google de cómo hacer la corrección ortográfica: norvig.com/spell-correct.html

    –Nate Kohl

    23 de noviembre de 2009 a las 15:23

  • Un Trie estándar consume mucha memoria, para conjuntos más grandes, querrá usar un Trie compacto que reduce en gran medida la huella de memoria. Las optimizaciones adicionales abarcan la inicialización diferida de los valores de los nodos y las estructuras de datos correctas para los conjuntos de valores/hijos. Hace un tiempo creé un biblioteca de autocompletar capaz de manejar conjuntos de datos muy grandes (más de 10,000,000) y responde de manera eficiente a búsquedas exactas y aproximadas.

    –Filipe Miguel Fonseca

    23 de junio de 2015 a las 14:47


¿Cual es el mejor algoritmo de autocompletarsugerir estructura de datos
Alegría Dutta

Para grandes conjuntos de datos, un buen candidato para el backend serían los árboles de búsqueda ternarios. 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 Diario del Dr. Dobbs: http://www.ddj.com/windows/184410528

El objetivo es la recuperación rápida de un conjunto de resultados finito a medida que el usuario ingresa. Consideremos primero que para buscar “ciencias de la computación” puede comenzar a escribir desde “computadora” o “ciencia”, pero no “computadora”. Entonces, dada una frase, genera las subfrases que comienzan 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 ha escrito hasta el momento. Almacenaremos los mejores 10 (digamos) 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 una vez cada pocas horas, según el dinamismo de los datos. Si los datos son en tiempo real, supongo que algún otro algoritmo dará un mejor equilibrio. En este caso, el requisito absoluto es la recuperación ultrarrápida de los resultados de cada pulsación de tecla, lo que hace muy bien.

Surgirán más complicaciones si se trata de la sugerencia de correcciones ortográficas. En ese caso, también se tendrán que considerar los algoritmos de distancia de edición.

Para conjuntos de datos pequeños como una lista de países, bastará con una implementación simple de Trie. Si va a implementar un menú desplegable de autocompletar de este tipo en una aplicación web, el widget de autocompletar de YUI3 hará todo por usted después de que proporcione los datos en una lista. Si usa YUI3 solo como interfaz para un autocompletado respaldado por grandes datos, haga los servicios web basados ​​en TST en C++ y luego use la fuente de datos del nodo de secuencia de comandos del widget de autocompletado para obtener datos del servicio web en lugar de una lista simple.

Segmentar árboles se puede utilizar para implementar eficientemente autocompletar

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

1646757972 6 ¿Cual es el mejor algoritmo de autocompletarsugerir estructura de datos
año

Para una solución simple: genera un ‘candidato’ con una edición mínima (Levenshtein) distancia (1 o 2) luego prueba la existencia del candidato con un contenedor hash (colocar será suficiente para una solución simple, luego use conjunto_desordenado desde el tr1 o boost).

Ejemplo: Escribiste carr y quieres car. arr es generado por 1 eliminación. ¿Está arr en tu unordered_set ? No. crr se genera por 1 eliminación. ¿Está crr en su conjunto desordenado? No. coche es generado por 1 borrado. ¿Está el coche en tu unordered_set ? Sí, ganas.

Por supuesto, hay inserción, eliminación, transposición, etc.

Ves que tu algoritmo para generar candidatos es realmente donde estás perdiendo el tiempo, especialmente si tienes muy poco conjunto_desordenado.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad