Tengo una larga lista de palabras y quiero mostrar palabras comenzando con el texto ingresado por el usuario. A medida que el usuario introduce un personaje, la aplicación debería actualizar la lista mostrada al usuario. Debería ser como AutoCompleteTextView en Android. Solo tengo curiosidad sobre la mejor estructura de datos para almacenar las palabras, de modo que la búsqueda sea muy rápida.¿Cuál es la mejor estructura de datos para autocompletar texto?
Se puede usar un trie. http://en.wikipedia.org/wiki/Triehttps://stackoverflow.com/search?q=trie
Un buen artículo - http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/
PS: Si usted tiene algunas sub-secuencias que "no se ramifican" entonces es posible ahorrar espacio mediante el uso de un trie por residuos, que es una aplicación que pone varios trie personajes de nodo cuando sea posible - http://en.wikipedia.org/wiki/Radix_tree
Se pueden encontrar este interesante hilo:
No es exactamente lo que quiere, sino que es una versión ligeramente extendida de su problema.
Para la implementación de la función de autocompletar, también se utilizan los árboles de búsqueda ternarios (TST):
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Sin embargo, si usted quiere encontrar cualquier subcadena dentro de una cadena aleatoria, pruebe con un árbol de sufijos generalizado.
Tries (y sus diversas variedades) son útiles aquí. Un tratamiento más detallado sobre este tema está en este paper. ¿Tal vez pueda implementar un trie de compleción para Android?
Creo que una tabla hash sería lo mejor. No estoy seguro del idioma o la plataforma que está utilizando, por lo que, en general, las tablas hash son rápidas y dinámicas. – c0d3Junk13
bien ... primero necesitamos saber la plataforma con la que está trabajando. ¿Androide? iOS? Windows? Linux? OSX? ¿Web o HTML? –
@ c0d3Junk13 ¿Cómo buscaría cadenas con un prefijo dado en una tabla hash? – delnan