効率的なアルゴリズムを使用したスペースのないテキストの単語へのトークン化

自然言語処理の領域で、文字の連続ストリームを分割する機能意味のある言葉に変えることが重要です。トークン化として知られるこのプロセスは、スペースや区切り文字のないテキストを扱う場合に特に困難です。

チャレンジ ステートメント

当面のタスクには、次のような入力文字列を分割することが含まれます。 「tableapplechairtablecupboard...」を単語のリストに組み込みます。シーケンスが複数の単語を構成する可能性があるあいまいな部分文字列の可能性を考慮します（たとえば、「食器棚」は「カップ」になる可能性があります）。

アルゴリズム: 単語の頻度を利用する

各位置で可能な限り長い単語を繰り返し識別する単純なアプローチでは、現実のシナリオでは満足のいく結果が得られません。 。この制限を克服するために、単語頻度分布を組み込んだアルゴリズムを利用します。

単語頻度のモデリング

単語頻度は、確率が次のとおりであるという Zipf の法則に従うと仮定します。 n 番目に頻繁に出現する単語に遭遇する確率は、約 1/(n * log(N)) です。ここで、N は言語内の単語の総数です。この関係をエンコードする事前に計算されたコスト辞書を使用すると、潜在的な各単語候補にコストを割り当てることができます。

動的プログラミング アプローチ

最適な単語セグメンテーションを決定するには、次のようにします。動的プログラミングを採用します。入力文字列を反復処理して、潜在的な各分割ポイントのランニングコスト値を維持します。各位置で、文字列の末尾から候補単語を評価し、コストが最も低い分割を選択します。

アルゴリズムの実装

提供された Python コードは次のことを提供します。このアルゴリズムの簡潔な実装:

from math import log

# Precomputed word cost dictionary using Zipf's law
wordcost = ...

# Helper function to find the best word match based on cost
def best_match(i):
    ...

# Function to infer spaces in the input string using dynamic programming
def infer_spaces(s):
    ...

使用例

このコードを利用するには、次のように連続テキスト文字列を入力するだけです:

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

結果と評価

このアルゴリズムは、限られた単語辞書でも優れたパフォーマンスを示します。複雑なテキストを高精度でトークン化することに成功しました。