Aperçu

Implémentation de l'arbre TRIE en Python LOUDS est utilisé pour la structure de données lors de la création de l'arborescence TRIE

Arbre TRIE

--Un arbre TRIE est un ensemble de chaînes de caractères représentées par une structure arborescente ordonnée. --Composé de nœuds et d'arêtes, et la position et la clé (chaîne de recherche) de chaque nœud correspondent. --Une chaîne de caractères vide correspond au nœud racine

Caractéristiques de l'arbre TRIE

Recherche rapide dans le dictionnaire: Vous pouvez effectuer une recherche dans un temps fixe quelle que soit la taille de l'arborescence. --Save memory: Puisque la clé n'est pas stockée dans le nœud, plusieurs clés peuvent partager le nœud et économiser de la mémoire.
Recherche de préfixe efficace: puisque le nœud est partagé par plusieurs clés, il est possible de rechercher efficacement les nœuds enfants associés au nœud parent (préfixe).

En raison de ses caractéristiques, les arbres TRIE sont utilisés pour la conversion kana-kanji et la complétion automatique.

LOUDS --LOUDS (séquence de degrés unaire d'ordre de niveau) est l'une des expressions de l'arbre d'ordre et peut exprimer la structure arborescente avec une taille extrêmement petite.

En particulier, lorsque le nombre de nœuds est N, la structure arborescente est représentée par un tableau d'étiquettes de longueur N et un tableau de bits de 2N + 1. ――Cependant, afin de rechercher efficacement à partir de l'arbre créé, des données auxiliaires (dictionnaire complet) sont nécessaires séparément.

Dictionnaire complet

Un dictionnaire complet est la structure de données la plus basique dans une structure de données concise.
En utilisant le dictionnaire complet comme données auxiliaires, il est possible de rechercher dans un temps fixe.
En particulier, recherchez l'arborescence TRIE en utilisant le rang des opérations et sélectionnez. --rank (): Combien de bits y a-t-il entre le début de la chaîne de bits et la position k --select (): Où se trouve la position à côté du nième bit 1 lorsqu'il est vu depuis le début de la chaîne de bits?
La structure de données concise est expliquée en détail sur cette page

la mise en oeuvre

Implémentation de ce qui suit en Python (GitHub)

--trie.py: arbre TRIE --builder.py: tableau de bits --words.py: créer / lire des données de dictionnaire --measure.py: mesure la mémoire et le temps de recherche --search_word.py: recherche de mots --test.py: Mesure du temps de recherche

Création de données de dictionnaire

Lorsqu'elles sont exécutées comme suit, les données de dictionnaire dans lesquelles les numéros de nœud et les mots de l'arborescence TRIE sont écrits séparés par des virgules sont créées. Données utilisées corpus wordnet de nltk Plus tard, les données de test seront créées à partir de ces données de dictionnaire.

from words import CreateWords
CreateWords("./data/origin/wordnet_words.csv")

Recherche de mot

 python search_word.py Données du dictionnaire PATH

Vous pouvez effectuer une recherche sur un seul mot en exécutant le fichier ci-dessus Lorsque vous entrez un mot, le numéro de nœud, la définition du mot et le préfixe obtenus à partir de la recherche sont affichés comme indiqué ci-dessous.

Mesure du temps de recherche

Créer des données de test

Vous pouvez créer des données de test pour un nombre illimité de mots à partir des données du dictionnaire en exécutant ce qui suit

 python words.py Données du dictionnaire PATH Nombre d'échantillons 1, Nombre d'échantillons 2, Nombre d'échantillons 3,…

Si vous souhaitez créer plusieurs données de test, spécifiez la taille de l'échantillon des données séparées par des virgules. Si "Les données de test sont créées." Est sortie, c'est ok. Les données de test sont créées dans ./data/test

La mesure

Une fois exécuté, le test peut être exécuté un nombre illimité de fois avec les données de test comme indiqué ci-dessous.

 python test.py Données du dictionnaire PATH Données de test PATH Nombre de tests

Si "Test est terminé." Est sortie, c'est ok. Les résultats de sortie sont créés dans ./results

Dans la mesure, le temps exact de recherche de correspondance et le temps de recherche de préfixe sont mesurés.

Recherche de correspondance exacte: durée totale d'exécution de la fonction de recherche de la classe trie
Recherche de préfixes: temps total d'exécution de la fonction get_blow_nodes de la classe trie

En interne, la fonction de recherche de la classe trie est exécutée pour le mot d'entrée et le numéro de nœud de l'arbre TRIE est sorti. Le numéro de nœud de sortie est assemblé avec le numéro de nœud dans les données du dictionnaire, et s'ils correspondent, le nombre de recherches est incrémenté de 1 et il est confirmé si la recherche est exacte. La même chose s'applique à la recherche de préfixe

Résultat de sortie

Recherche de correspondance exacte: temps total nécessaire pour rechercher un mot
Résultats de la recherche: nombre d'enregistrements qui correspondent au numéro de nœud des données du dictionnaire
Recherche de préfixes: temps total nécessaire pour rechercher tous les préfixes associés au mot recherché
Recherche de préfixe (par élément): temps de recherche par préfixe associé au mot recherché
utilisation de la mémoire --bit_array: utilisation de la mémoire du tableau de bits --labels: utilisation de la mémoire du tableau d'étiquettes --rank: classe l'utilisation de la mémoire --select: sélectionnez l'utilisation de la mémoire

Implémentation de l'arbre TRIE avec Python et LOUDS