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. trie tree (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

Recommended Posts

J'ai écrit un tri-arbre qui peut être utilisé pour l'implémentation de dictionnaire à grande vitesse en langage D et Python
J'ai créé un modèle de projet Python générique
Comprendre les probabilités et les statistiques qui peuvent être utilisées pour la gestion des progrès avec un programme python
Un mémo que j'ai écrit un tri rapide en Python
Fonctions pouvant être utilisées dans l'instruction for
J'ai écrit une classe en Python3 et Java
Je souhaite créer une file d'attente prioritaire pouvant être mise à jour avec Python (2.7)
Programme d'installation facile et programme de mise à jour automatique pouvant être utilisé dans n'importe quelle langue
Scripts pouvant être utilisés lors de l'utilisation de Bottle en Python
Peut être utilisé avec AtCoder! Une collection de techniques pour dessiner du code court en Python!
J'ai créé un outil pour générer automatiquement un diagramme de transition d'état pouvant être utilisé à la fois pour le développement Web et le développement d'applications
Un minuteur (ticker) qui peut être utilisé sur le terrain (peut être utilisé n'importe où)
J'ai fait un shuffle qui peut être réinitialisé (inversé) avec Python
Nouvelles fonctionnalités de Python 3.9 (1) -L'opérateur d'ensemble de somme peut être utilisé dans le type de dictionnaire.
Résumé de l'entrée standard de Python pouvant être utilisée dans Competition Pro
Je l'ai fait parce que je veux des données JSON qui peuvent être utilisées librement dans les démos et les prototypes
Code et leçons apprises pour les fonctions qui ouvrent des dossiers Windows spéciaux dans les ctypes Python3
J'ai acheté et analysé la loterie jumbo de fin d'année avec Python qui peut être exécutée dans Colaboratory
Remplissage facile des données pouvant être utilisées dans le traitement du langage naturel
Optimisation mathématique pour un travail gratuit avec Python + PuLP
J'ai écrit un graphe comme R glmnet en Python pour une modélisation clairsemée avec Lasso
++ et-ne peuvent pas être utilisés pour incrémenter / décrémenter en python
J'ai créé un fichier de dictionnaire python pour Neocomplete
[Python3] Code qui peut être utilisé lorsque vous souhaitez découper une image dans une taille spécifique
Classe pour PYTHON qui peut être utilisée sans connaître LDAP
J'ai essayé de créer une classe qui peut facilement sérialiser Json en Python
J'ai enregistré PyQCheck, une bibliothèque qui peut effectuer QuickCheck avec Python, dans PyPI.
Notes personnelles des opérations liées aux pandas qui peuvent être utilisées dans la pratique
Notez que je comprends l'algorithme des moindres carrés. Et je l'ai écrit en Python.
Comment installer la bibliothèque Python qui peut être utilisée par les sociétés pharmaceutiques
J'ai créé un outil en Python qui clique avec le bouton droit sur un fichier Excel et le divise en fichiers pour chaque feuille.
Résumé des méthodes d'analyse de données statistiques utilisant Python qui peuvent être utilisées en entreprise
Visualisation des informations géographiques de R et Python qui peuvent être exprimées par Power BI
Mettre en place un serveur FTP qui peut être créé et détruit immédiatement (en Python)
Un mécanisme pour appeler des méthodes Ruby à partir de Python qui peut être fait en 200 lignes
Algorithmes de base utilisables par les pros de la compétition
Pour pouvoir utiliser le japonais avec Python dans l'environnement Docker
J'ai créé une VM qui exécute OpenCV pour Python
Notes sur les connaissances Python utilisables avec AtCoder
Enregistrement d'image ANT qui peut être utilisé en 5 minutes
Peut être utilisé chez les pros de la compétition! Bibliothèque standard Python
J'ai écrit python3.4 dans .envrc avec direnv et je l'ai autorisé, mais j'ai eu une erreur de syntaxe
Installez Mecab et CaboCha sur ubuntu16.04LTS afin qu'il puisse être utilisé à partir de la série python3
Comment configurer un serveur SMTP simple qui peut être testé localement en Python
J'ai écrit un module Ansible brut qui vous permet d'utiliser Virtualenv en installant Pythonz.
[Django] Noms de champs pouvant être utilisés pour le modèle utilisateur, l'enregistrement des utilisateurs et les méthodes de connexion
[Python3] Code qui peut être utilisé lorsque vous souhaitez redimensionner des images dossier par dossier
[Atcoder] [C ++] J'ai fait un outil d'automatisation de test qui peut être utilisé pendant le concours
Étant donné que ImageDataGenerator ne peut plus être utilisé, une histoire sur la création d'une classe d'extension de données pour tensorflow> = 2.0
[Python] Un programme pour trouver le nombre de pommes et d'oranges qui peuvent être récoltées
Goroutine (contrôle parallèle) utilisable sur le terrain
J'ai essayé "un programme qui supprime les déclarations en double en Python"
Goroutine utilisable sur le terrain (édition errgroup.Group)
Créez le code qui renvoie "A et prétendant B" en python
J'ai créé une classe en Python et essayé de taper du canard
J'ai écrit un script qui divise l'image en deux
[Python] Dessinez des données d'altitude sur une surface sphérique avec Plotly et dessinez un globe qui peut être tourné en rond et en rond
J'ai écrit python en japonais
Créer un dictionnaire en Python
[Pour les débutants] Statistiques de baseball dont on peut se souvenir en 33 minutes et 4 secondes et PyData ~ avec Yojima Steel