python - 如何将没有空格的文本拆分为单词列表

Question

输入: "tableapplechairtablecupboard..."很多单词

将此类文本拆分为单词列表并获取的有效算法是什么:

输出: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], .. .]

首先想到的是遍历所有可能的单词(从第一个字母开始)并找到可能的最长单词，从 position=word_position+len(word)

继续

附言
我们有一个所有可能单词的列表。
单词“cupboard”可以是“cup”和“board”，选择最长的。
语言:python，但主要是算法本身。

Answer 1

简单的算法在应用于实际数据时不会产生好的结果。这是一个 20 行的算法，它利用相对词频来为真实词文本提供准确的结果。

(如果您想得到不使用词频的原始问题的答案，则需要细化“最长词”的确切含义:最好有 20 个字母的词和 10 个 3 - 字母词，还是最好有 5 个 10 字母词？一旦确定了精确的定义，您只需更改定义 wordcost 的行以反射(reflect)预期的含义。)

想法

最好的方法是建模输出的分布。一个好的初步近似是假设所有单词都是独立分布的。那么你只需要知道所有单词的相对频率。可以合理地假设它们遵循 Zipf 定律，即单词列表中排名为 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))

---

结果

我正在使用 this quick-and-dirty 125k-word dictionary I put together来自维基百科的一小部分。

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

Before: thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery whetherthewordisreasonablesowhatsthefastestwayofextractionthxalot.

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.

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.

如您所见，它基本上完美无缺。最重要的部分是确保你的单词列表被训练成一个与你实际遇到的相似的语料库，否则结果会很糟糕。

---

优化

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

如果您需要处理一个非常大的连续字符串，拆分字符串以避免过多的内存使用是合理的。例如，您可以处理 10000 个字符的 block 加上两侧 1000 个字符的边距以避免边界效应。这将使内存使用量降至最低，并且几乎可以肯定对质量没有影响。