用随机字符串计算英文单词

Question

假设我有一个随机生成的字符串s=t&^%JHGgfdteam*&HGEdfg,计算该字符串中英文单词数量的最佳方法是什么？(英语单词在某些词典文件中定义).显然蛮力不是一个好主意......后缀是否会起作用？二进制搜索？请注意,在这种情况下s,有两个词:"茶"和"团队".有任何想法吗？问候

Answer 1

我会在Trie结构中加载字典单词,然后从左到右读取字符串并检查子字符串是否在trie中.如果他们是,并且有孩子,继续前进.如果它们恰好是叶子或有效单词,请添加到出现计数.

在伪代码中:

Trie dict = ... // load dictionary
Dictionary occurences = {}

for i in length(string):
    j = i + 1
    # think of partial as string.Substring(i, j);
    while dict.hasChildren(partial):
        j++ 
        if isWord(partial):
            dict[partial]++

通过这种方式,您可以保证在寻找所有可能性的同时不会错过任何一场比赛.

您可以通过更改j已初始化的内容或通过拒绝isWord()方法中的短字来限制有效单词的最小长度(因此a不会是"有效"单词).

Answer 2

的阿霍Corasick串匹配算法构建在时间线性匹配结构在词典的大小和在时间线性中发现的输入文本+的匹配数目的尺寸相匹配的图案.