arunkumar9t2 / trie

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.

Deixe uma resposta

O seu endereço de email não será publicado.