[PYTHON] Einführung in den Wörterbuch-Suchalgorithmus

Einführung

Es gab viele Fälle, in denen ich in meiner Arbeit die Verarbeitung natürlicher Sprache durchführte und etwas beschleunigen musste, und so kam ich auf den Begriff Wörterbuch-Suchalgorithmus. Vielleicht, weil tiefes Lernen im Bereich der Verarbeitung natürlicher Sprache zu weit verbreitet ist, scheint es viele Menschen zu geben, die nicht auf den Punkt kommen, selbst wenn sie den Wörterbuch-Suchalgorithmus hören.

Was ist ein Wörterbuch-Suchalgorithmus?

Ein Algorithmus, der Wörter im Wörterbuch aus allen möglichen Teilzeichenfolgen im Text abruft. Es unterstützt die Rückseite der Verarbeitung wie die morphologische Analyse. Es scheint, dass Sie MeCab oder Human erstellen können, wenn Sie diesen Pfad beherrschen. Wenn der String abc gegeben ist, lautet der Teilstring beispielsweise:

Überprüfen Sie, ob diese Teilzeichenfolgen im Wörterbuch enthalten sind. Kurz gesagt, es ist wie ein Algorithmus, der Wörter in einem Wörterbuch aus einer Zeichenkette zieht.

Der Rechenaufwand für die Aufzählung dieser Teilzeichenfolge beträgt $ O (N \ ^ 2) , ist jedoch zu diesem Zeitpunkt noch weit von der praktischen Verwendung als Anwendung entfernt. ( O (N) $ wird bevorzugt)

Übrigens wird das Wörterbuch manchmal als Hash bezeichnet, aber es kostet $ O (N) $, um den Hash-Wert der Zeichenfolge zu berechnen, sodass es am Ende $ O (N ^ 3) $ kostet.

Beispiel für eine Beschleunigung

Deshalb müssen wir irgendwie beschleunigen. Ein Beispiel ist die $ common prefix search $.

Dies ist gegen den Satz "Behinderung der Ausführung öffentlicher Angelegenheiten"

--Öffentlichkeit

Dies ist der Vorgang, bei dem die im Wörterbuch registrierten Wörter aus den Sätzen mit demselben Präfix gezogen werden.

Dies wird mithilfe einer Datenstruktur beschleunigt, die als Tri-Tree bezeichnet wird. (Siehe hier für Tri-Bäume)

Öffentlichkeit
 |---end 
Aufgaben
 |---end
Ausführung
 |---end
Interferenz
 |
end

Wenn das Wort "public" angezeigt wird, können Sie suchen, indem Sie den Teilstring wie folgt verfolgen. (Wenn end angezeigt wird, wird es zu diesem Zeitpunkt als ein Wort registriert.)

Der Berechnungsbetrag für diese Tri-Tree-Suche beträgt $ O (K) $. (K: durchschnittliche Wortlänge)

Verwenden Sie die allgemeine Präfixsuche für den Satz "Ich möchte das College verlassen".

Sie können das Wörterbuch so nachschlagen. Dies ist $ O (NK) $.

Bohnenwissen

Es scheint, dass Tri-Bäume in MeCab verwendet werden, und es scheint, dass die schnellste Tri-Tree-Implementierungsmethode namens double array verwendet wird. (Das Linkziel ist eine leicht verständliche Folie mit doppelter Anordnung.) Eine C ++ - Bibliothek namens Darts wurde veröffentlicht, die die Verwendung von Doppelarrays vereinfacht.

Als nächstes möchte ich mich auf die Verarbeitung konzentrieren, nachdem ich das Wörterbuch nachgeschlagen habe.

Recommended Posts

Einführung in den Wörterbuch-Suchalgorithmus
Einführung in MQTT (Einführung)
Einführung in Scrapy (3)
Erste Schritte mit Supervisor
Einführung in Tkinter 1: Einführung
Einführung in PyQt
Einführung in Scrapy (2)
Wörterbuch-Lernalgorithmus
[Linux] Einführung in Linux
[Einführung in die Udemy Python3 + -Anwendung] 24. Wörterbuchtyp
Einführung in Scrapy (4)
Einführung in discord.py (2)
[Einführung in die Udemy Python3 + -Anwendung] 61. Wörterbucheinschlussnotation
Was ist ein Algorithmus? Einführung in den Suchalgorithmus] ~ Python ~
[Einführung in die Udemy Python3 + -Anwendung] 26. Kopie des Wörterbuchs
[Einführung in den Algorithmus] Finden Sie den kürzesten Weg [Python3]
Einführung in Lightning Pytorch
Erste Schritte mit Web Scraping
Einführung in nichtparametrische Felder
Einführung in EV3 / MicroPython
Einführung in die Python-Sprache
Einführung in die TensorFlow-Bilderkennung
Einführung in OpenCV (Python) - (2)
Einführung in PyQt4 Teil 1
Verwendung des Wörterbuchs {}
Einführung in die Abhängigkeitsinjektion
Einführung in Private Chainer
Zugriff auf Wörterbuchfelder
Einführung in das maschinelle Lernen
[Einführung in die Stärkung des Lernens] Teil 1 - Epsilon-Greedy-Algorithmus im Banditenspiel
[Einführung in Udemy Python3 + Application] 53. Wörterbuch der Schlüsselwortargumente
[Einführung in die Udemy Python3 + -Anwendung] 27. Verwendung des Wörterbuchs
AOJ Einführung in die Programmierung Thema Nr. 1, Thema Nr. 2, Thema Nr. 3, Thema Nr. 4
Einführung in das elektronische Papiermodul
Einführung in die Monte-Carlo-Methode
[Lernmemorandum] Einführung in vim
Einführung in PyTorch (1) Automatische Differenzierung
opencv-python Einführung in die Bildverarbeitung
Einführung in Python Django (2) Win
Einführung in das Schreiben von Cython [Notizen]
Einführung in Private TensorFlow
Eine Einführung in das maschinelle Lernen
[Einführung in cx_Oracle] Übersicht über cx_Oracle
Eine super Einführung in Linux
AOJ Einführung in die Programmierung Thema Nr. 7, Thema Nr. 8
Fügen Sie MeCab ein Wörterbuch hinzu
Einführung in die Anomalieerkennung 1 Grundlagen
Einführung in RDB mit sqlalchemy Ⅰ
[Einführung in Systre] Fibonacci Retracement ♬
Einführung in die nichtlineare Optimierung (I)
Einführung in die serielle Kommunikation [Python]
AOJ Einführung in die Programmierung Thema Nr. 5, Thema Nr. 6
Einführung in Deep Learning ~ Lernregeln ~
[Einführung in Python] <Liste> [Bearbeiten: 22.02.2020]
Einführung in Python (Python-Version APG4b)
Eine Einführung in die Python-Programmierung
Einführung in Python Scikit-Learn, Matplotlib, Single-Layer-Algorithmus (~ in Richtung B3 ~ Teil3)