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