Implémentation efficace de Trie pour les chaînes unicode

Je cherchais une implémentation efficace de String trie. Surtout, j'ai trouvé du code comme celui-ci:

Implémentation référentielle en Java (par wikipedia)

Je n'aime pas ces implémentations pour principalement deux raisons:

1. Ils ne prennent en charge que 256 caractères ASCII. Je dois couvrir des choses comme cyrillique.
2. Ils sont extrêmement inefficaces en mémoire.

Chaque nœud contient un tableau de 256 références, soit 4096 octets sur une machine 64 bits en Java. Chacun de ces nœuds peut avoir jusqu'à 256 sous-nœuds avec chacun 4096 octets de références. Ainsi, un Trie complet pour chaque chaîne de caractères ASCII 2 nécessiterait un peu plus de 1 Mo. Trois chaînes de caractères? 256 Mo uniquement pour les tableaux dans les nœuds. Etc.

Bien sûr, je n'ai pas l'intention d'avoir les 16 millions de chaînes de caractères en trois dans mon Trie, donc beaucoup d'espace est juste gaspillé. La plupart de ces tableaux ne sont que des références nulles car leur capacité dépasse de loin le nombre réel de clés insérées. Et si j'ajoute unicode, les tableaux deviennent encore plus grands (char a 64k valeurs au lieu de 256 en Java).

Y a-t-il un espoir de faire un tri efficace pour les cordes? J'ai envisagé quelques améliorations par rapport à ces types d'implémentations:

• Au lieu d'utiliser un tableau de références, je pourrais utiliser un tableau de type entier primitif, qui indexe dans un tableau de références à des nœuds dont la taille est proche du nombre de nœuds réels.
• Je pourrais briser les chaînes en parties de 4 bits qui permettraient des tableaux de nœuds de taille 16 au prix d'un arbre plus profond.

Pourquoi utilisez-vous ce trie? Quel est le nombre total de mots que vous prévoyez de tenir et quelle est la rareté de leurs caractères constitutifs? Et le plus important, un trie est-il même approprié (contre une simple carte de préfixe à une liste de mots)?

Votre idée d'une table intermédiaire et de remplacer les pointeurs par des index fonctionnera, à condition que vous ayez un ensemble relativement petit de mots courts et un jeu de caractères clairsemé. Sinon, vous risquez de manquer d'espace dans votre table intermédiaire. Et à moins que vous ne regardiez un ensemble de mots extrêmement petit, vous n'économiserez pas vraiment beaucoup d'espace: 2 octets pour un court contre 4 octets pour une référence sur une machine 32 bits. Si vous utilisez une machine virtuelle Java 64 bits, les économies seront plus importantes.

Votre idée de diviser les caractères en morceaux de 4 bits ne vous sauvera probablement pas beaucoup, sauf si tous vos caractères attendus sont dans une plage extrêmement limitée (peut-être OK pour les mots limités en majuscules US-ASCII, peu probable avec un corpus général Unicode ).

Si vous avez un jeu de caractères clairsemé, alors a HashMap<Character,Map<...>>pourrait être votre meilleure implémentation. Oui, chaque entrée sera beaucoup plus grande, mais si vous n'avez pas beaucoup d'entrées, vous obtiendrez une victoire globale. (en guise de remarque: j'ai toujours pensé que c'était drôle que l'article de Wikipedia sur Tries montre - peut-être encore - un exemple basé sur une structure de données hachée, ignorant complètement les compromis espace / temps de ce choix)

Enfin, vous voudrez peut-être éviter complètement un trie. Si vous regardez un corpus de mots normaux dans une langue humaine (10000 mots en utilisation active, avec des mots de 4 à 8 caractères), vous serez probablement beaucoup mieux avec un HashMap<String,List<String>, où la clé est le préfixe entier.

si vous encodez les chaînes en UTF8, vous pouvez utiliser le tri de branchement 256 standard et toujours être compatible unicode

vous devez également noter que seuls 70 caractères environ sur les 128 caractères ascii possibles (qui codent tous en 1 octet en UTF8) seront trouvés le plus lourdement que vous pouvez optimiser pour cela (comme inclure les digraphes communs à la place des caractères de contrôle inutilisés )