当应用于现实世界的数据时，简单的算法不会给出好的结果。这是一个 20 行算法，它利用相对词频来为真实单词文本提供准确的结果。
（如果您想要不使用词频的原始问题的答案，则需要细化“最长单词”的确切含义：是有一个 20 个字母的单词和 10 个 3 字母的单词更好，还是最好有五个 10 个字母的单词？一旦确定了精确的定义，您只需更改定义行wordcost以反映其预期含义。）
The idea
最好的方法是继续model输出的分布。一个好的第一个近似是假设所有单词都是独立分布的。那么你只需要知道所有单词的相对频率即可。可以合理地假设它们遵循齐普夫定律，即具有等级的词n单词列表中的概率大约为 1/(n log N) where N是字典中的单词数。
修复模型后，您可以使用动态规划来推断空间的位置。最可能的句子是使每个单词的概率乘积最大化的句子，并且很容易通过动态规划来计算它。我们不直接使用概率，而是使用定义为概率倒数对数的成本来避免溢出。
The code
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 单词词典 http://tinypaste.com/c1666a6b来自维基百科的一小部分。
Before:拇指绿色苹果每周主动作业隐喻。
After:拇指青苹果每周主动作业隐喻。
Before:存在大量从 html 解析而来的人们评论的文本信息，但有
其中的有限字符例如拇指青苹果活跃作业每周隐喻
显然，字符串中有拇指、青苹果等，因此有一个大字典可供查询
这个词是否合理，那么最快的提取方式是什么？
After:有大量从 html 解析出来的人们评论的文本信息，但其中没有分隔字符，例如拇指青苹果主动作业每周隐喻显然字符串中有拇指青苹果等我还有一个大字典来查询是否这个词是合理的，那么最快的提取方法是什么，非常感谢。
Before:那是一个漆黑的暴风雨之夜，大雨倾盆，除了偶尔有一阵猛烈的狂风席卷伦敦的街道，我们的场景沿着屋顶嘎嘎作响，猛烈地搅动着与黑暗作斗争的灯火。
After:那是一个漆黑的暴风雨之夜，雨倾盆而下，偶尔会被席卷街道的狂风所阻止，因为我们的场景是在伦敦，沿着屋顶嘎嘎作响，猛烈地搅动着微弱的火焰。那些与黑暗作斗争的灯。
正如您所看到的，它基本上是完美无缺的。最重要的部分是确保你的单词列表被训练成与你实际遇到的相似的语料库，否则结果将非常糟糕。
优化
该实现消耗线性量的时间和内存，因此相当高效。如果需要进一步加速，可以从单词列表构建后缀树以减少候选集的大小。
如果需要处理非常大的连续字符串，则合理地分割字符串以避免过多的内存使用。例如，您可以以 10000 个字符的块形式处理文本，并在两侧留出 1000 个字符的边距，以避免边界效应。这将使内存使用量保持在最低限度，并且几乎肯定不会对质量产生影响。
