arunkumar9t2 / trie

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.