¿Qué son buenas estructuras de datos para los algoritmos de autocompletado? ¿Qué estructuras de datos permiten encontrar de manera eficiente las cadenas que contienen una subcadena particular?estructura de datos para finalización automática
Si usted está buscando para hacer algo similar a la forma en que Google implementa es autocompletar, es posible que desee comprobar fuera de un ternario árbol de búsqueda:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Sin embargo, si usted quiere encontrar cualquier subserie aleatoria dentro de una cadena, intente con un árbol de sufijo generalizado.
¿Eso no funciona solo si solo quieres unir prefijos? p.ej. un árbol de búsqueda ternario lo ayuda a hacer coincidir "ab" en "abcd", pero no "bc" en "abcd" (puede ser grueso, no sabe mucho sobre árboles de búsqueda ternarios, y solo le dio al enlace una mirada fugaz). –
Creo que sí, en general funciona en una x "comienza con" y más o menos. Sin embargo, en la práctica esto parece ser el funcionamiento de todas las funciones de autocompletar que he usado alguna vez. –
entre algunos de los widgets de autocompletado que uso día a día coinciden en cualquier lugar de la cadena; no obstante, enlace útil, entonces +1. –
Salida suffix array y suffix tree.
¡Hombre, he estado buscando el algoritmo de Ukkonen durante años y nunca lo supe! Tengo una aplicación que necesita una coincidencia eficiente de subcadenas con errores. Incluso he preguntado en foros como este en el pasado y no obtuve ningún buen puntero. ¡Me hiciste el día! – swestrup
@swestrup: me alegra que te haya ayudado a rastrear esa información :) Debes obtener una copia de * The Algorithm Design Manual *, http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref = sr_1_1? Ie = UTF8 & s = books & qid = 1268325877 & sr = 8-1 es una invaluable * compilación * de estructuras de datos, algoritmos y bibliografía/referencias de URL;) –
Si está haciendo prefijos (que es lo que la mayoría de autocompleta) entonces un árbol de búsqueda ternario también es lo que yo recomendaría. Si está haciendo infixes generales, vaya con un árbol de sufijos, como se mencionó anteriormente.
Nah, es una idea tonta. Usa árboles de sufijo. Mucho mejor. – swestrup
si es tonto, edita tu respuesta –
Como alternativa a los Arreglos de Sufijo, Arboles y Tries, eche un vistazo a Directed Acyclic Word Graphs (DAWG) y la variante Comprimida (CDAWG). Se pueden construir en tiempo lineal, ocupar espacio lineal y permitir la búsqueda de subcadenas.
Con una función de búsqueda más complicada, puede incluso admitir un conjunto limitado de comodines.
He creado una aplicación para lo que desea. Es el algoritmo de autocompletado alineado basado en el prefijo más eficiente.
Si el conjunto de sugerencias de autocompletado es jerarquizada, un SuggestTree es una buena estructura de datos. Para cualquier prefijo dado, proporciona acceso rápido a las sugerencias superiores k que comienzan con ese prefijo.
http://en.wikipedia.org/wiki/Trie – frankc