arunkumar9t2/trie

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.