3

可能重复：
如何将没有空格的文本拆分为单词列表？

人们的评论中有大量的文本信息是从html中解析出来的，但其中没有分隔符。例如：thumbgreenappleactiveassignmentweeklymetaphor。显然，字符串中有'thumb'、'green'、'apple'等。我也有一本大字典来查询这个词是否合理。那么，提取这些单词的最快方法是什么？

4

2 回答 2

8

正如 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 单词的快速而肮脏的词典。

之前： thumbgreenappleactiveassignmentweekly 比喻。
之后：拇指青苹果活动作业每周比喻。

之前：存在从 html 中解析出来的人们评论的软文本信息，但其中包含有定界符的字符，例如拇指青苹果活动分配每周一次的比喻很明显，字符串中有拇指青苹果等，还有一个大字典来查询该词是否合理，那么提取 thxalot 的最快方法是什么。

之后：有大量从 html 解析的人们评论的文本信息，但其中没有分隔字符，例如拇指青苹果活动分配每周隐喻显然在字符串中有拇指青苹果等我也有一个大字典查询这个词是否合理，那么最快的提取方法是什么？很多。

之前：这是一个黑暗和暴风雨的夜晚，除了偶尔的间歇，当它被猛烈的狂风刮到伦敦的街道上时，我们的风景在屋顶上嘎嘎作响，并在激烈地搅动着与黑暗作斗争的灯的微弱火焰。

之后：那是一个黑暗而暴风雨的夜晚，雨倾盆而下，只是偶尔一阵狂风刮过街道，因为在伦敦，我们的场景在屋顶上嘎嘎作响，猛烈地搅动着整个街道。在黑暗中挣扎的灯火微弱。

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

优化

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

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

于 2012-07-21T00:03:16.367 回答
4

“显然”对人类有益，而不是对计算机……</p> 

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和中的可能单词for j in xrange(3, len(s) - i):（最小单词长度为 3），它发现：

thumb
hum
green
nap
apple
plea
lea
act
active
ass
assign
assignment
sign
men
twee
wee
week
weekly
met
eta
tap
于 2012-07-20T09:45:34.503 回答