[解決済み] スペースがないテキストを単語のリストに分割する方法

質問

入力してください。 "tableapplechairtablecupboard..." 多くの単語

このようなテキストを単語のリストに分割して取得する効率的なアルゴリズムは何でしょうか。

出力します。 ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

最初に思いつくのは、考えられるすべての単語（最初の文字で始まる）を調べ、可能な限り長い単語を見つけることです。 position=word_position+len(word)

追伸

可能な限りの単語をリストアップしています。

単語 "cupboard" は "cup" と "board" があり、最も長いものを選択します。

言語：python、しかし、主なものは、アルゴリズムそのものです。

どのように解決するのですか？

単純なアルゴリズムでは、実世界のデータに適用したときに良い結果を得ることはできません。ここでは、実際の単語のテキストに対して正確な結果を与えるために、相対的な単語頻度を利用した20行のアルゴリズムを紹介します。

(20 文字の単語と 10 個の 3 文字の単語があるほうがよいのか、それとも 5 個の 10 文字の単語があるほうがよいのか。正確な定義が決まったら、次のように定義している行を変更するだけです。 wordcost を定義している行を、意図した意味を反映するように変更すればよいのです)。

アイデア

最適な進め方は モデル をモデル化することです。良い第一近似は、すべての単語が独立に分布していると仮定することです。そうすると、すべての単語の相対的な頻度を知るだけでよいことになります。Zipfの法則に従うと仮定するのは合理的で、つまり、順位が n を持つ単語の確率はおよそ1/( n ログ N ) ここで N は辞書に含まれる単語の数です。

モデルを固定したら、動的計画法を使って空白の位置を推測します。最も可能性の高い文は、個々の単語の確率の積を最大化するものであり、動的計画法で簡単に計算することができる。確率を直接使うのではなく、確率の逆数の対数として定義されたコストを使って、オーバーフローを回避しています。

コード

from math import log

# Build a cost dictionary, assuming Zipf's law and cost = -math.log(probability).
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):
    """Uses dynamic programming to infer the location of spaces in a string
    without spaces."""

    # Find the best match for the i first characters, assuming cost has
    # been built for the i-1 first characters.
    # Returns a pair (match_cost, match_length).
    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)

    # Build the cost array.
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)
        cost.append(c)

    # Backtrack to recover the minimal-cost string.
    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))

で使用することができます。

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

---

結果

私が使っているのは 私が作成した 125k ワードのクイック アンド ダーティな辞書です。 を使っています。

<ブロッククオート

以前は thumbgreenappleactiveassignmentweeklymetaphor。

後です。 親指青りんごアクティブ課題週間比喩。

<ブロッククオート

前です。 をクリックすると、コメント欄のテキスト情報が大量に表示されます。 というのは、"aple "は "aple "の略で、"aple "は "aple "の略です。 また、文字列の中には、その単語がどのような理由によるものかを調べるための大辞典があるようです。 また、文字列の中にサムグリーンアップルがあるかどうか、最速の抽出方法は何か、などを調べるための大辞典もあります。

後です。 htmlから解析された人々のコメントのテキスト情報の質量がありますが、それらの中に区切られた文字がありません例えば親指青リンゴアクティブ割り当て週間比喩明らかに文字列に親指青リンゴなどがあります私はまた、単語が妥当であるかどうかを照会するための大規模な辞書を持っているので、抽出thxの多くの最も速い方法は何だ。

<ブロッククオート

前です。

の夜だった、雨で激しく降り続く、時折の中断以外は、それはロンドンの炎のための大通りで押し寄せる激しい風の風によって確認され、我々の千種は家の頂上をラットリングと激しく、暗闇に抵抗している火山のスキャンティ火炎に影響を及ぼすことでした。

後です。 その夜は暗く荒れ狂い、雨は時折激しい突風に煽られる以外は滔々と降り注ぎ、街は一掃された。

見ての通り、基本的に完璧です。最も重要なのは、単語リストが実際に遭遇するものに近いコーパスに対して学習されていることを確認することで、そうでなければ結果は非常に悪くなります。

---

最適化

この実装は時間とメモリを直線的に消費するため、それなりに効率的である。さらに高速化が必要な場合は、単語リストから接尾辞ツリーを構築し、候補の集合のサイズを小さくすることができる。

非常に大きな連続した文字列を処理する必要がある場合、メモリの過剰使用を避けるために文字列を分割するのが合理的でしょう。たとえば、10000 文字のブロックに、境界の影響を避けるために両側に 1000 文字の余白を付けてテキストを処理することができます。これにより、メモリの使用量は最小限に抑えられ、品質への影響もほとんどありません。