Una implementación java de la estructura de datos Trie de Prefijo.
Introducción
Los intentos son estructuras de datos basadas en árboles ordenados como mapas que proporcionan una búsqueda rápida del orden O(k)
donde k
es la longitud de la clave. Lea más sobre trie aquí.
Motivation
Esto se creó inicialmente para usarlo en mi aplicación Android, T9 App Launcher, para buscar rápidamente en la lista de aplicaciones instaladas e iniciarlas.
API públicas
Actualmente hay 3 implementaciones públicas que se pueden elegir.
-
MapTrie
:HashMap
implementación de trie respaldada. -
SortedTrie
:TreeMap
la implementación de trie respaldada que devuelve sugerencias y valores es de orden ascendente. -
T9Trie
: Implementación de ayuda para almacenar y recuperar sugerencias para la secuencia T9.
Ejemplo de uso
Crear un trie simple y obtener sugerencias.
final MapTrie<String> trie = new MapTrie<>();trie.insert("Hello", "Hello");trie.insert("Help", "Help");trie.insert("Has", "Has");trie.insert("Have", "Have");trie.insert("Had", "Had");trie.insert("Hadn't", "Hadn't"); // Print to stdouttrie.print();
La llamada anterior print()
imprimiría la estructura de árbol de esta manera.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
Ahora intentemos encontrar todas las palabras que comiencen con ha
. Recuerde que, por defecto, las teclas no distinguen entre mayúsculas y minúsculas.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
Esto imprimirá en la consola. El valor se deja intacto.
Contribución
Si es desarrollador y desea contribuir, considere hacer una solicitud de extracción. Agradecería cualquier crítica con respecto al código o la implementación en general.
Licencia
Este proyecto está licenciado bajo la licencia Apache 2.0.