単語の頻度と動的プログラミングを活用して、スペースのないテキストを効率的に単語リストに分割するにはどうすればよいでしょうか?

スペースを含まないテキストを単語リストに分割する

概要

この記事では、スペースを含まない単語で構成される文字列を分割するための効率的なアルゴリズムを紹介します。

問題ステートメント

入力: "tableapplechairtablecupboard..."

出力: ["table", "apple", "椅子", "テーブル", ["食器棚", ["カップ", "ボード"]], ...]

アルゴリズムの概要

アルゴリズムは、単純なアプローチを使用するのではなく、単語の頻度を活用して精度を向上させます。単語が独立して分布し、Zipf の法則に従っていると仮定すると、アルゴリズムは動的プログラミングを使用して、最も可能性の高い単語のシーケンスを特定します。

コード

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

words = open("words-by-frequency.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)        
        cost.append(c)

    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        out.append(s[i-k:i])
        i -= k

    return " ".join(reversed(out))

def best_match(i):
    candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
    return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

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

単語頻度推定

このアルゴリズムは、Zipf の法則を前提として、単語を相対頻度にマッピングする辞書に依存します。目に見えない単語を考慮して、それらに高いコストが割り当てられます。

動的プログラミング

アルゴリズムは、次の単語の可能性を考慮して、考えられる各単語セグメントのコストを計算します。動的プログラミングを使用して最小コストのパスを選択し、最も可能性の高い単語シーケンスを保証します。

パフォーマンスの最適化

大規模な入力の場合、テキストをブロックに分割して処理することでアルゴリズムを最適化できます。それらは独立して行われます。これにより、精度に大きな影響を与えることなくメモリ使用量が削減されます。

以上が単語の頻度と動的プログラミングを活用して、スペースのないテキストを効率的に単語リストに分割するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。