thumbgreenappleactiveassignmentweeklymetaphor。显然，字符串中有"thumb"、"green"、"apple"等单词。我还有一个大型词典，可以查询这些单词是否合理。那么，最快的提取这些单词的方法是什么？我不确定一个简单的算法是否能有效地满足你的需求，正如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))
我正在使用我从维基百科的一个小子集中快速而粗略地组合起来的这个125k字典。
之前：thumbgreenappleactiveassignmentweeklymetaphor。
之后：thumb green apple active assignment weekly metaphor。
之前：有大量的人们评论的文本信息，这些信息是从HTML解析出来的，但它们没有定界符，例如thumb green apple active assignment weekly metaphor，显然在字符串中也有thumb green apple等词汇，我还有一个大型的字典可以查询单词是否合理，那么最快的提取方式是什么呢？非常感谢。
之后：有大量的人们评论的文本信息，这些信息是从HTML解析出来的，但它们没有定界符，例如thumb green apple active assignment weekly metaphor，显然在字符串中也有thumb green apple等词汇，我还有一个大型的字典可以查询单词是否合理，那么最快的提取方式是什么呢？非常感谢。
之前：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。
之后：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。
正如您所看到的，它基本上是无缺陷的。最重要的部分是确保您的单词列表经过了类似于实际遇到的语料库的训练，否则结果将非常糟糕。
该实现消耗的时间和内存量是线性的，因此它是相当高效的。如果您需要进一步加速，可以从单词列表构建后缀树以减少候选集的大小。
如果您需要处理非常大的连续字符串，则将字符串拆分以避免过度使用内存是合理的。例如，您可以将文本处理成每个块10000个字符加上左右各1000个字符的余量，以避免边界效应。这将使内存使用最小，并且几乎肯定不会影响质量。
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/words中的词以及长度至少为3的for j in xrange(3, len(s) - i):，它会找到：
thumb
hum
green
nap
apple
plea
lea
act
active
ass
assign
assignment
sign
men
twee
wee
week
weekly
met
eta
tap