将朴素的算法应用于实际数据时，效果不佳。这是一条20行的算法，该算法利用相对词频来为实词文本提供准确的结果。

（如果您想回答不使用词频的原始问题的答案，则需要完善“最长词”的确切含义：使用20个字母的单词和10个3个字母的单词会更好，还是最好有五个10个字母的单词？确定精确的定义后，只需更改定义的行wordcost即可反映出预期的含义。）

这个主意

最好的方法是对输出的分布进行 建模
。一个很好的第一近似是假设所有单词都是独立分布的。然后，您只需要知道所有单词的相对频率即可。合理地假设它们遵循齐普夫定律，即在单词列表中排名为 n
的单词的概率约为1 /（ n log 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))

结果

我正在使用从Wikipedia的一小部分中拼凑而成的这个快速且肮脏的125k字字典。

之前： thumbgreenappleactiveassignmentweekly隐喻。
之后： 拇指绿苹果积极分配每周的隐喻。

以前：有
一种从html解析出的软注释信息，但是却重新获得了有限的字符内阁，例如，thumbgreenappleactiveassignmentlymetapho
rapparentlytherearthumbgreenappleetc等 在 字符串中应以词义形式查询该词是否合理，这是最快的提取方法。

之后：
从html解析出大量的人民评论文本信息，但是其中没有定界字符，例如，拇指绿苹果活跃作业每周隐喻显然在字符串中有拇指绿苹果等，我也有一个大词典查询单词是否合理，那么提取最快的方法是什么。

之前： 夜晚是黑夜和暴风雨，除偶然的间隔外，当被狂风吹过一阵子检查风雨的时候，伦敦的街道扫荡着我们 在 伦敦的景象， 在
屋子顶上摇晃着，激烈地燃烧着那盏挣扎着的灯的火焰， 在 黑暗中挣扎着。

之后：
那是一个黑暗而暴风雨的夜晚，雨水倾盆而下，除了偶尔被狂风吹拂而扫过街道的间隔，因为在伦敦，我们的场景在房顶上晃动，剧烈地搅动着房屋。挣扎着黑暗的灯火。

如您所见，它本质上是完美的。最重要的部分是确保您的单词列表经过训练后的语料库与您将实际遇到的语料库相似，否则结果将非常糟糕。

优化

该实现消耗线性时间和内存，因此它是相当有效的。如果需要进一步提高速度，则可以从单词列表中构建后缀树，以减少候选集的大小。

如果您需要处理非常大的连续字符串，则合理的做法是将字符串拆分以避免过多的内存使用。例如，您可以按10000个字符的块处理文本，并在每侧加1000个字符的边距，以避免边界效应。这将使内存使用率降到最低，并且几乎可以肯定不会对质量产生任何影响。