uma implementação java do prefixo estrutura de dados Trie.
introdução
as tentativas são mapeadas como estruturas de dados baseadas em árvore ordenadas que fornecem pesquisa rápida da ordem O(k)
onde k
é o comprimento da chave. Leia mais sobre trie aqui.
motivação
este foi inicialmente construído para usar no meu aplicativo Android, Lançador de aplicativos T9 para pesquisar rapidamente através da lista de aplicativos instalados e iniciá-los.
APIs públicas
Atualmente, existem 3 implementações públicas que podem ser escolhidas.
-
MapTrie
:HashMap
implementação Trie apoiada. -
SortedTrie
:TreeMap
implementação Trie apoiada que retorna sugestões e valor é ordem de classificação crescente. -
T9Trie
: implementação auxiliar para armazenar e recuperar sugestões para a sequência T9.
exemplo de uso
Criando um trie simples e recebendo sugestões.
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();
a chamada acima print()
imprimiria a estrutura da árvore assim.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
agora vamos tentar encontrar todas as palavras começando com ha
. Lembre-se de que, por padrão, as chaves não diferenciam maiúsculas de minúsculas.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
isto imprimirá ao console. O valor é deixado intocado.
contribuição
se você é um desenvolvedor e gostaria de contribuir, considere fazer uma solicitação pull. Eu apreciaria qualquer crítica em relação ao código ou implementação em geral.
licença
este projeto está licenciado sob a Licença Apache 2.0.