確率論的なアプローチを使用して、連続するテキストを単語リストに効率的に分割するにはどうすればよいでしょうか?

連続したテキストを単語リストに効率的に分割する

この質問には課題があります。スペースのないテキスト文字列が与えられた場合、抽出するアルゴリズムを考案してください。

単純なアプローチでは、可能な限り長い単語を繰り返し識別して削除します。ただし、この戦略は現実のシナリオでは非効率であることが判明する可能性があります。

確率的アプローチ

これらの制限を克服するために、確率モデルはアルゴリズムに単語頻度を組み込みます。 Zipf の法則は、単語の確率を単語頻度のランクに反比例するものとして近似します。

このモデルを使用すると、考えられる単語の区切りごとに、文全体の負の対数確率としてコスト関数を定義できます。休憩が取られることになった。動的プログラミングを使用して、合計コストが最も低い単語区切りを見つけます。

実装

以下に提供される Python コードは、このアルゴリズムを実装します。

<code class="python">from math import log

# Build a cost dictionary based on Zipf's law
words = open("words-by-frequency.txt").read().split()
maxword = max(len(x) for x in words)
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))

def infer_spaces(s):
    cost = [0]
    for i in range(1,len(s)+1):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        c,k = min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)
        cost.append(c)
    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        assert c == cost[i]
        out.append(s[i-k:i])
        i -= k
    return " ".join(reversed(out))</code>

このコードの使用:

<code class="python">s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))</code>

生成:

thumb green apple active assignment weekly metaphor

最適化

さらに効率を高めるために、接尾辞ツリーを次のように構築できます。単語リストを使用して検索スペースを削減します。入力文字列をより小さなチャンクに分割すると、メモリ使用量も削減できます。

結論

単語頻度をモデル化し、動的プログラミングを使用することで、連続したテキストを分割するための効率的なアルゴリズムが得られます。個々の単語に変換し、現実世界のテキストに対して正確な結果を提供します。

以上が確率論的なアプローチを使用して、連続するテキストを単語リストに効率的に分割するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。