J'ai écrit un tri-arbre qui peut être utilisé pour l'implémentation de dictionnaire à grande vitesse en langage D et Python

Qu'est-ce qu'un arbre d'essai?

Connaissez-vous la structure de données appelée arbre Trie? Tri-tree est une structure de données qui peut être utilisée pour implémenter des dictionnaires à grande vitesse. La mise en œuvre à l'aide d'une structure de données appelée LOUDS présente l'avantage que l'arbre peut être représenté avec très peu de mémoire. Le tri-arbre est utilisé pour garder le dictionnaire japonais en mémoire lors de la conversion Kana-Kanji (entrée japonaise de Google, etc.), par exemple.

Le tri-arbre a une telle forme. (La figure est tirée de Wikipedia)

Ce qui le différencie des autres arbres, c'est que les "branches" de l'arbre sont étiquetées.

Comment puis-je l'utiliser comme dictionnaire? Cherchons "in". c'est simple. Tout ce que vous avez à faire est de suivre i-> n. Vous pouvez récupérer "5" comme résultat de recherche. Cherchons "auberge". Tout ce que vous avez à faire est de descendre de la position actuelle "5". "9" peut être récupéré en conséquence.

Caractéristiques de tri tree

Vous pouvez rechercher à grande vitesse

Ce qui est génial avec cet arbre d'essai, c'est que vous pouvez effectuer des recherches très rapidement. Dans un tri-arbre, la vitesse de recherche est proportionnelle à la taille de la clé à rechercher. Et ce n'est pas proportionnel à la taille de l'arbre __! __

Par exemple, supposons que vous implémentiez un dictionnaire japonais avec un tri-arbre. Il faut environ 4 (= 12/3) fois plus de temps pour rechercher le "Waraukado ni Fukukitaru" à 12 caractères dans le dictionnaire japonais que le "Warau" à 3 caractères. Cependant, si vous recherchez le même mot, qu'il contienne 100 mots ou 1 million de mots dans le dictionnaire, la vitesse de recherche ne change pas en théorie. C'est incroyable.

Réduisez les recherches inutiles

En outre, lorsque vous recherchez une chaîne de caractères ayant une partie commune, vous pouvez réduire les recherches inutiles en relançant la recherche à partir du milieu. Par exemple, lorsque j'ai recherché "inn" plus tôt, j'ai pu trouver rapidement les résultats de la recherche pour "inn" en relançant la recherche à partir du nœud "5" dans le résultat de la recherche de "in".

Mise en œuvre par LOUDS

Implémenter un tri-arbre sans y penser en utilisant des structures et des pointeurs consomme beaucoup de mémoire. La machine se fige si la mémoire est trop occupée pour rester bloquée. Par conséquent, nous utilisons une méthode de représentation des données appelée LOUDS. Avec LOUDS, un nœud peut être représenté par seulement 2 bits. Un arbre avec 11 nœuds comme celui montré au début peut être représenté par seulement 23 bits, et il tient dans une variable de type long.

Je voudrais expliquer LOUDS ici, mais comme Explication de la structure de données concise LOUDS était très facile à comprendre, je vais vous la donner. ..

code

Le code est ci-dessous. Implémenté respectivement en langage D et Python. github.com/IshitaTakeshi/Louds-Trie J'avais l'intention d'écrire beaucoup de commentaires, donc je pense que vous pouvez le comprendre en lisant l'explication de LOUDS dans le lien ci-dessus, puis en lisant le code. Si vous avez des questions ou des préoccupations, veuillez commenter ou nous dire sur Twitter et nous vous répondrons.

Edition en boîte

Il peut être géré par le système de gestion de paquets en langage D. DUB. Page DUB Code source