Où puis-je trouver une implémentation standard de carte basée sur Trie en Java ?

Question

J'ai un programme Java qui stocke un grand nombre de mappings de chaînes de caractères vers divers objets.

Pour l'instant, j'ai le choix entre le hachage (via HashMap) et les recherches binaires (via TreeMap). Je me demande s'il existe une implémentation efficace et standard de la carte à base de trie dans une bibliothèque de collections populaire et de qualité ?

J'ai écrit mes propres textes dans le passé, mais je préfère utiliser quelque chose de standard, si possible.

Clarification rapide : Bien que ma question soit d'ordre général, dans le projet actuel, je traite beaucoup de données qui sont indexées par nom de classe ou signature de méthode entièrement qualifiés. Ainsi, il y a beaucoup de préfixes partagés.

Answer 1

Vous pouvez consulter le La mise en œuvre de Trie à laquelle Limewire contribue au Google Guava.

Answer 2

Il n'existe pas de structure de données trie dans les bibliothèques Java de base.

Cela peut s'expliquer par le fait que les essais sont généralement conçus pour stocker des chaînes de caractères, alors que les structures de données Java sont plus générales, et contiennent généralement n'importe quelle Object (définissant l'égalité et une opération de hachage), bien qu'ils soient parfois limités à Comparable des objets (définition d'un ordre). Il n'y a pas d'abstraction commune pour "une séquence de symboles", bien que CharSequence est adapté aux chaînes de caractères, et je suppose que vous pourriez faire quelque chose avec Iterable pour d'autres types de symboles.

Voici un autre point à prendre en compte : lorsque vous essayez d'implémenter un tableau conventionnel en Java, vous êtes rapidement confronté au fait que Java supporte l'Unicode. Pour obtenir une certaine efficacité en termes d'espace, vous devez restreindre les chaînes de votre trie à un sous-ensemble de symboles ou abandonner l'approche conventionnelle consistant à stocker les nœuds enfants dans un tableau indexé par symbole. C'est peut-être une autre raison pour laquelle les tries ne sont pas considérées comme suffisamment polyvalentes pour être incluses dans la bibliothèque de base, et un élément à surveiller si vous implémentez votre propre bibliothèque ou si vous utilisez une bibliothèque tierce.

Answer 3

Consultez également arbres concurrents . Ils prennent en charge les arbres Radix et Suffix et sont conçus pour les environnements à forte concurrence.

Answer 4

J'ai écrit et publié une implémentation simple et rapide aquí .

Answer 5

Ce dont vous avez besoin, c'est org.apache.commons.collections.FastTreeMap Je pense.