3

重複の可能性:
スペースのないテキストを単語のリストに分割する方法は?

HTMLから解析された人々のコメントには大量のテキスト情報がありますが、それらには区切り文字がありません。例: thumbgreenappleactiveassignmentweeklymetaphor. どうやら、文字列には「親指」、「緑」、「リンゴ」などがあります。また、単語が妥当かどうかを照会するための大きな辞書もあります。では、これらの単語を抽出する最速の方法は何ですか?

4

2 に答える 2

8

eumiroが指摘したように、素朴なアルゴリズムがあなたの目的にうまく役立つかどうかはよくわからないので、もう少し複雑なアルゴリズムについて説明します.

アイデア

続行する最善の方法は、出力の分布をモデル化することです。最初の適切な近似は、すべての単語が独立して分布していると仮定することです。次に、すべての単語の相対頻度を知るだけで済みます。それらが Zipf の法則に従うと仮定するのは合理的です。つまり、単語のリストでランクnの単語は、おおよそ 1/( n log N )の確率を持ちます。ここで、 Nは辞書内の単語の数です。

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

コード

import math

# Build a cost dictionary, assuming Zipf's law and cost = -math.log(probability).
words = open("words-by-frequency.txt").read().split()
wordcost = dict((k,math.log((i+1)*math.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))

例

私は、ウィキペディアの小さなサブセットからまとめた、125,000 語の辞書を使用しています。

前:サムグリーンアップルアクティブ割り当てウィークリーメタファー。
後:親指緑のリンゴのアクティブな割り当ての毎週の比喩。

以前： HTMLから解析された人々のコメントのソフト拡張情報がありましたが、制限された文字がありました。

後： HTMLから解析された人々のコメントのテキスト情報の塊がありますが、それらには区切り文字がありません。単語が合理的かどうかを照会するので、抽出の最速の方法は何ですか。

以前：それは暗くて嵐の夜でした.雨が降っていたのは時折の間隔を除いて暴風雨が降っていました.

後:暗くて嵐の夜でした.雨が激しく降っていました.ときどき通りを吹き飛ばす激しい突風によって雨が降ったときを除いて.闇と戦ったランプのわずかな炎。

ご覧のとおり、それは本質的に完璧です。最も重要な部分は、単語リストが実際に遭遇するものと同様のコーパスにトレーニングされていることを確認することです。そうしないと、結果が非​​常に悪くなります。

最適化

実装は時間とメモリを直線的に消費するため、かなり効率的です。さらに高速化が必要な場合は、単語リストからサフィックス ツリーを作成して、候補セットのサイズを小さくすることができます。

非常に大きな連続した文字列を処理する必要がある場合は、過度のメモリ使用を避けるために文字列を分割するのが合理的です。たとえば、テキストを 10000 文字のブロックで処理し、両側に 1000 文字のマージンを加えて、境界効果を回避することができます。これにより、メモリ使用量が最小限に抑えられ、品質への影響はほぼ確実になくなります。

于 2012-07-21T00:03:16.367 に答える
4

「どうやら」はコンピューターではなく、人間にとっては良いことです…</p> 

words = set(possible words)
s = 'thumbgreenappleactiveassignmentweeklymetaphor'
for i in xrange(len(s) - 1):
    for j in xrange(1, len(s) - i):
        if s[i:i+j] in words:
            print s[i:i+j]

/usr/share/dict/wordsandの可能な単語for j in xrange(3, len(s) - i):(最小単語長 3) については、次のことがわかります。

thumb
hum
green
nap
apple
plea
lea
act
active
ass
assign
assignment
sign
men
twee
wee
week
weekly
met
eta
tap
于 2012-07-20T09:45:34.503 に答える