Une implémentation java de la structure de données Préfixe Trie.
Introduction
Les essais sont des structures de données basées sur des arborescences ordonnées qui fournissent une recherche rapide de l’ordre O(k)
où k
est la longueur de la clé. En savoir plus sur trie ici.
Motivation
Cela a été initialement conçu pour être utilisé dans mon application Android, le lanceur d’applications T9 pour rechercher rapidement dans la liste des applications installées et les lancer.
Api publiques
Actuellement, il existe 3 implémentations publiques parmi lesquelles vous pouvez choisir.
-
MapTrie
:HashMap
mise en œuvre soutenue de trie. -
SortedTrie
:TreeMap
l’implémentation trie soutenue qui renvoie des suggestions et une valeur est un ordre de tri croissant. -
T9Trie
: Implémentation d’aide pour stocker et récupérer des suggestions pour la séquence T9.
Exemple d’utilisation
Création d’un trie simple et obtention de suggestions.
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();
L’appel print()
ci-dessus imprimerait la structure arborescente comme ceci.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
Essayons maintenant de trouver tous les mots commençant par ha
. N’oubliez pas que, par défaut, les clés sont insensibles à la casse.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
Cela affichera sur la console. La valeur est laissée intacte.
Contribution
Si vous êtes un développeur et que vous souhaitez contribuer, veuillez envisager de faire une pull request. J’apprécierais toute critique concernant le code ou la mise en œuvre en général.
Licence
Ce projet est sous licence Apache 2.0.