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.
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)
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.
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) $.
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