Introduction à l'algorithme de recherche de dictionnaire

introduction

Il y a eu de nombreuses occasions où je faisais du traitement du langage naturel dans mon travail et que je devais accélérer quelque chose, alors j'ai proposé le terme algorithme de recherche de dictionnaire. Peut-être parce que l'apprentissage en profondeur est trop répandu dans le domaine du traitement du langage naturel, il semble que beaucoup de gens ne viennent pas au point même s'ils entendent l'algorithme de recherche de dictionnaire.

Qu'est-ce qu'un algorithme de recherche de dictionnaire?

Un algorithme qui récupère les mots du dictionnaire à partir de toutes les sous-chaînes possibles du texte. Il prend en charge l'arrière du traitement tel que l'analyse morphologique. Il semble que si vous maîtrisez ce chemin, vous pouvez créer MeCab ou Human. Par exemple, étant donné la chaîne abc, la sous-chaîne est:

Vérifiez si ces sous-chaînes sont dans le dictionnaire. En bref, c'est comme un algorithme qui extrait des mots d'un dictionnaire à partir d'une chaîne de caractères.

Le montant du calcul pour énumérer cette sous-chaîne est $ O (N \ ^ 2) , mais à ce stade, il est loin d'être pratique en tant qu'application. ( O (N) $ est préférable)

Au fait, le dictionnaire est parfois appelé hachage, mais il en coûte $ O (N) $ pour calculer la valeur de hachage de la chaîne de caractères, donc il en coûte $ O (N ^ 3) $ à la fin.

Exemple d'accélération

Par conséquent, nous devons accélérer d'une manière ou d'une autre. Un exemple est la recherche de préfixe commun $ $.

Cela va à l'encontre de la phrase «obstruction à l'exécution des affaires publiques»

--Publique --Affaires publiques --Exécution des affaires publiques --Interférence avec l'exécution des affaires publiques

C'est le processus qui consiste à extraire les mots enregistrés dans le dictionnaire des phrases avec le même préfixe.

Ceci est accéléré à l'aide d'une structure de données appelée tri-arbre. (Voir ici pour les tri-arbres)

Publique
 |---end 
Fonctions
 |---end
Exécution
 |---end
Ingérence
 |
end

Lorsque le mot «public» apparaît, permettez la recherche en traçant la sous-chaîne comme ceci. (Lorsque la fin apparaît, elle est enregistrée comme un mot à ce moment)

Le montant du calcul de cette recherche à trois arbres est de $ O (K) $. (K: longueur de mot moyenne)

En utilisant la recherche de préfixe commun, pour la phrase "Je veux quitter l'université"

Vous pouvez rechercher le dictionnaire comme ceci. C'est $ O (NK) $.

Connaissance des haricots

Il semble que les tri-arbres soient utilisés dans MeCab, et il semble que la méthode d'implémentation la plus rapide des tri-arbres appelée double array soit utilisée. (La destination du lien est une diapositive facile à comprendre avec une double disposition) Une bibliothèque C ++ appelée Darts a été publiée, ce qui facilite l'utilisation des tableaux doubles.

Ensuite, je voudrais me concentrer sur le traitement après avoir consulté le dictionnaire.

Recommended Posts

Introduction à l'algorithme de recherche de dictionnaire
Introduction à MQTT (Introduction)
Introduction à Scrapy (3)
Premiers pas avec Supervisor
Introduction à Tkinter 1: Introduction
Introduction à PyQt
Introduction à Scrapy (2)
Algorithme d'apprentissage du dictionnaire
[Linux] Introduction à Linux
[Introduction à l'application Udemy Python3 +] 24. Type de dictionnaire
Introduction à Scrapy (4)
Introduction à discord.py (2)
[Introduction à Udemy Python3 + Application] 61. Notation d'inclusion de dictionnaire
Qu'est-ce qu'un algorithme? Introduction à l'algorithme de recherche] ~ Python ~
[Introduction à Udemy Python3 + Application] 26. Copie du dictionnaire
[Introduction à l'algorithme] Trouvez l'itinéraire le plus court [Python3]
Introduction à Lightning Pytorch
Premiers pas avec le Web Scraping
Introduction aux baies non paramétriques
Introduction à EV3 / MicroPython
Introduction au langage Python
Introduction à la reconnaissance d'image TensorFlow
Introduction à OpenCV (python) - (2)
Introduction à PyQt4 Partie 1
Comment utiliser le dictionnaire {}
Introduction à l'injection de dépendances
Introduction à Private Chainer
Accès aux champs du dictionnaire
Introduction à l'apprentissage automatique
[Introduction au renforcement de l'apprentissage] part.1-Algorithme Epsilon-Greedy dans Bandit Game
[Introduction à Udemy Python3 + Application] 53. Dictionnaire des arguments de mots-clés
[Introduction à Udemy Python3 + Application] 27. Comment utiliser le dictionnaire
AOJ Introduction à la programmation Sujet 1, Sujet 2, Sujet 3, Sujet 4
Introduction au module de papier électronique
Introduction à la méthode Monte Carlo
[Mémorandum d'apprentissage] Introduction à vim
Introduction à PyTorch (1) Différenciation automatique
opencv-python Introduction au traitement d'image
Introduction à Python Django (2) Win
Introduction à l'écriture de Cython [Notes]
Introduction à Private TensorFlow
Une introduction à l'apprentissage automatique
[Introduction à cx_Oracle] Présentation de cx_Oracle
Une super introduction à Linux
AOJ Introduction à la programmation Sujet n ° 7, Sujet n ° 8
Ajouter un dictionnaire à MeCab
Introduction à la détection des anomalies 1 principes de base
Introduction à RDB avec sqlalchemy Ⅰ
[Introduction au système] Retracement de Fibonacci ♬
Introduction à l'optimisation non linéaire (I)
Introduction à la communication série [Python]
AOJ Introduction à la programmation Sujet n ° 5, Sujet n ° 6
Introduction au Deep Learning ~ Règles d'apprentissage ~
[Introduction à Python] <liste> [modifier le 22/02/2020]
Introduction à Python (version Python APG4b)
Une introduction à la programmation Python
Introduction à Python scikit-learn, matplotlib, algorithme monocouche (~ vers B3 ~ part3)