First thing that cames to mind is to go through all possible words (starting with first letter) and find the longest word possible, continue from position=word_position+len(word)

P.S。 我们拥有的所有可能的单词列表。 词橱柜可以是杯具和板，选择最长的。照片 语言：Python的，但主要的是算法本身。

P.S. We have a list of all possible words. Word "cupboard" can be "cup" and "board", select longest. Language: python, but main thing is the algorithm itself.

推荐答案

当应用到真实世界的数据一个天真的算法不会给良好的效果。这是一个20行的算法，利用相对词频给出准确的结果实字文本。

A naive algorithm won't give good results when applied to real-world data. Here is a 20-line algorithm that exploits relative word frequency to give accurate results for real-word text.

（如果你想要的答案，您不使用词频原来的问题，需要改进究竟是最长的单词的含义：这是最好有一个20个字母和10个3 -letter的话，还是更是有五10字母的单词？一旦你看中一个precise定义，你只需要改变该行定义 wordcost 来反映预期的含义。）的

(If you want an answer to your original question which does not use word frequency, you need to refine what exactly is meant by "longest word": is it better to have a 20-letter word and ten 3-letter words, or is it better to have five 10-letter words? Once you settle on a precise definition, you just have to change the line defining wordcost to reflect the intended meaning.)

要进行的最好的办法是的模式的输出分配。一个良好的第一近似值是假设所有的词都独立分布。然后，你只需要知道的所有词的相对频​​率。这是合理的假设，他们遵循齐普夫定律，那就是在单词列表排名的 N 的这个词的概率约为1 /（ N 的日志的 N ）其中的 N 的是单词在字典中的数量。

The best way to proceed is to model the distribution of the output. A good first approximation is to assume all words are independently distributed. Then you only need to know the relative frequency of all words. It is reasonable to assume that they follow Zipf's law, that is the word with rank n in the list of words has probability roughly 1/(n log N) where N is the number of words in the dictionary.

一旦你有固定的模式，你可以使用动态编程来推断空间的位置。最有可能的一句话是一个最大化每个单词的概率的乘积，并且很容易与动态规划计算它。而不是直接使用，我们使用定义为概率的倒数的对数成本的概率，以避免溢出。

Once you have fixed the model, you can use dynamic programming to infer the position of the spaces. The most likely sentence is the one that maximizes the product of the probability of each individual word, and it's easy to compute it with dynamic programming. Instead of directly using the probability we use a cost defined as the logarithm of the inverse of the probability to avoid overflows.

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字字典我放在一起从维基百科的一小部分的。

The results

I am using this quick-and-dirty 125k-word dictionary I put together from a small subset of Wikipedia.

之前： thumbgreenappleactiveassignmentweeklymetaphor 。   之后：拇指青苹果主动分配每周比喻

Before: thumbgreenappleactiveassignmentweeklymetaphor. After: thumb green apple active assignment weekly metaphor.

之前： thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen   odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho   rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery   whetherthewordisreasonablesowhatsthefastestwayofextractionthxalot。

Before: thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery whetherthewordisreasonablesowhatsthefastestwayofextractionthxalot.

之后：有群众的它是由HTML解析，但没有分隔的人物在其中，例如拇指青苹果主动分配每周比喻人民意见的文本信息显然是有经验的青苹果等在字符串中我也有一个大词典查询单词是否合理，什么;提取THX的最快的方法有很多。

After: there is masses of text information of peoples comments which is parsed from html but there are no delimited characters in them for example thumb green apple active assignment weekly metaphor apparently there are thumb green apple etc in the string i also have a large dictionary to query whether the word is reasonable so what s the fastest way of extraction thx a lot.

之前： itwasadarkandstormynighttherainfellintorrentsexceptatoccasionalintervalswhenitwascheckedbyaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatoursceneliesrattlingalongthehousetopsandfiercelyagitatingthescantyflameofthelampsthatstruggledagainstthedarkness.

Before: 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.

的实施消耗时间和存储器的线性量，因此它是相当有效的。如果您需要进一步的加速，可以构建从词汇列表中的后缀树，以减少候选集的大小。

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.

如果你需要处理一个连续的非常大的字符串，它是合理的分割字符串，以避免过多的内存使用情况。例如，你可以处理在10000字块的文字加上1000字两边保证金，以避免边界效应。这将保持存储器使用到最低限度，将具有几乎肯定的质量没有影响

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.