入力： "tableapplechairtablecupboard..."たくさんの言葉
このようなテキストを単語のリストに分割して取得する効率的なアルゴリズムは何でしょうか。
出力： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
最初に思いついたのは、すべての可能な単語（最初の文字から始めて）を調べて、可能な限り長い単語を見つけることです。position=word_position+len(word)
PS
考えられるすべての単語のリストがあります。
単語「cupboard」は「cup」と「board」のどちらにもなり得ますが、最も長いものを選択してください。
言語: Python ですが、重要なのはアルゴリズムそのものです。
ベストアンサー1
単純なアルゴリズムを現実世界のデータに適用すると、良い結果は得られません。ここでは、相対的な単語の頻度を利用して、現実世界のテキストに対して正確な結果を提供する 20 行のアルゴリズムを紹介します。
(単語の頻度を使用しない元の質問への回答が必要な場合は、「最長の単語」が正確に何を意味するのかを明確にする必要があります。20 文字の単語 1 つと 3 文字の単語 10 個を使用する方が良いのでしょうか、それとも 10 文字の単語 5 個を使用する方が良いのでしょうか。正確な定義が決まったら、wordcost意図した意味を反映するように定義行を変更するだけです。)
アイデア
最善の方法はモデル出力の分布。最初の近似として、すべての単語が独立して分布していると仮定するのが良いでしょう。そうすれば、すべての単語の相対的な頻度を知るだけで済みます。Zipfの法則、つまり順位がん単語リストの確率はおよそ1/(んログいいえ） どこいいえ辞書内の単語の数です。
モデルを修正したら、動的プログラミングを使用してスペースの位置を推測できます。最も可能性の高い文は、各単語の確率の積を最大化する文であり、動的プログラミングを使用して簡単に計算できます。確率を直接使用する代わりに、オーバーフローを回避するために、確率の逆数の対数として定義されたコストを使用します。
コード
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))
結果
使っています私がまとめた125,000語の辞書Wikipedia の小さなサブセットから。
前に：サムグリーンアップルアクティブ割り当てウィークリーメタファー。
後：親指の緑のリンゴのアクティブな割り当ての毎週の比喩。
前に：HTML から解析される人々のコメントのテキスト情報を評価しますが、その中には制限された文字がありません。たとえば、thumbgreenappleactiveassignmentweeklymetapho rap には ethumbgreenapple などがあるようです。そのため、単語が妥当かどうかを問い合わせるための大きな辞書が必要です。そのため、抽出する最も速い方法は何ですか?
後：HTML から解析された人々のコメントのテキスト情報が大量にありますが、それらには区切られた文字がありません。たとえば、thumb green apple active assignment weekly metaphor などです。どうやら文字列には、thumb green apple などが含まれているようです。単語が妥当かどうかを照会するための大きな辞書も持っているので、抽出の最も速い方法は何ですか。どうもありがとうございます。
前に： itwasadarkandstormynighttherainfellintorrentsexceptatoccasionalintervalswhenitwascheckedbyaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatoursceneliesrattlingalongthehousetopsandfiercelyagitatingthescantyflameofthelampsthatstruggledagainstthedarkness.
After: it was a dark and stormy night the rain fell in torrents except at occasional intervals when it was checked by a violent gust of wind which swept up the streets for it is in london that our scene lies rattling along the housetops and fiercely agitating the scanty flame of the lamps that struggled against the darkness.
As you can see it is essentially flawless. The most important part is to make sure your word list was trained to a corpus similar to what you will actually encounter, otherwise the results will be very bad.
Optimization
The implementation consumes a linear amount of time and memory, so it is reasonably efficient. If you need further speedups, you can build a suffix tree from the word list to reduce the size of the set of candidates.
If you need to process a very large consecutive string it would be reasonable to split the string to avoid excessive memory usage. For example you could process the text in blocks of 10000 characters plus a margin of 1000 characters on either side to avoid boundary effects. This will keep memory usage to a minimum and will have almost certainly no effect on the quality.