如何有效地从连续字符串中提取文字单词？

Question

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

人们的评论中有大量的文本信息,这些信息是从html中解析出来的,但它们中没有分隔字符.例如:thumbgreenappleactiveassignmentweeklymetaphor.显然,字符串中有"拇指","绿色","苹果"等.我还有一个大词典来查询这个词是否合理.那么,提取这些单词的最快方法是什么？

Answer 1

我不太确定一个天真的算法能很好地满足你的目的,正如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字词典,我从维基百科的一小部分组合在一起.

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

之前: thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery whetherthewordisreasonablesowhatsthefastestwayofextractionthxalot.

:以后也有存在的是从HTML解析人民意见的文本信息,群众但是在他们没有分隔字符例如拇指青苹果主动分配每周比喻显然有字符串中的拇指青苹果等我大词典查询这个词是否合理,那么最快的提取方法是什么.

之前: itwasadarkandstormynighttherainfellintorrentsexceptatoccasionalintervalswhenitwascheckedbyaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatoursceneliesrattlingalongthehousetopsandfiercelyagitatingthescantyflameofthelampsthatstruggledagainstthedarkness.

后:这是一个夜黑风高的大雨如注,除了在当它是由风的猛烈阵风席卷了大街小巷,因为这是在伦敦,我们的现场位于沿房顶剑拔弩张检查偶有间隔激烈搅动在黑暗中挣扎的灯的火焰很少.

如你所见,它基本上完美无瑕.最重要的部分是确保您的单词列表训练成类似于您实际遇到的语料库,否则结果将非常糟糕.

优化

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

如果需要处理非常大的连续字符串,则拆分字符串以避免过多的内存使用是合理的.例如,您可以处理10000个字符的块中的文本以及两侧的1000个字符的边距,以避免边界效应.这将使内存使用量降至最低,几乎肯定不会影响质量.