スペースを含まずに単語が連結されたテキスト文字列を個々の単語に効率的に分割するにはどうすればよいでしょうか?

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

問題

スペースを含まずに連結された単語で構成されるテキスト文字列があるとします:

Input: "tableapplechairtablecupboard..."

このテキストを個々の単語のリストに効率的に分割するにはどうすればよいですか?

Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

アルゴリズム

簡単なアプローチは、テキスト内で可能な限り長い単語を繰り返し見つけることです。ただし、これは次善の結果につながる可能性があります。

頻度ベースのアルゴリズム

代わりに、言語内の単語の相対頻度を利用して精度を向上させることができます。

1. 単語分布のモデル化: 単語は独立して分布しており、単語の確率がその順位に反比例するという Zipf の法則に従うと仮定します。
2. 単語コストの定義: コスト単語の尤度の逆数の対数として定義されます。

3. 動的プログラミング アプローチ:

   • 最初のコスト配列を初期化します。要素は 0 です。
   • テキスト内の各文字について、その時点までの文字の総コストを最小にする単語を見つけます。
   • 最後からバックトラックして最小コストの単語シーケンスを再構築します。 .

コードの実装

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

wordcost = {}  # Dictionary of word costs using Zipf's law

maxword = max(len(word) for word in wordcost)

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((wordcost.get(s[i - k - 1:i], 9e999) + c, 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>

結果

このアルゴリズムは、テキストを単語のリストに正確に分割できます。スペースがないこと。

例:

Input: "tableapplechairtablecupboard..."
Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

最適化:

• サフィックス ツリー: 単語リストから接尾辞ツリーを構築することで、候補検索を高速化できます。
• テキスト ブロック分割: 大きなテキスト入力の場合、テキストをブロックに分割して、精度を維持しながらメモリ使用量を最小限に抑えます。

以上がスペースを含まずに単語が連結されたテキスト文字列を個々の単語に効率的に分割するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。