针对预定义种子列表进行字符串测试的最快C++算法(不区分大小写)

Question

我有种子字符串列表,大约100个预定义字符串.所有字符串仅包含ASCII字符.

std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"};

我的应用程序不断收到很多字符串,可以包含任何字符.我需要检查每个收到的行并确定它是否包含任何种子.比较必须不区分大小写.

我需要最快的算法来测试收到的字符串.

现在我的应用程序使用这个算法:

std::wstring testedStr;
for (auto & seed : seeds)
{
    if (boost::icontains(testedStr, seed))
    {
        return true;
    }
}
return false;

它运作良好,但我不确定这是最有效的方法.

为了获得更好的性能,如何实现该算法？

这是一个Windows应用程序.应用接收有效std::wstring字符串.

---

更新

为此,我实施了Aho-Corasick算法.如果有人可以查看我的代码那就太棒了 - 我对这些算法没有太大的经验.链接到实施:gist.github.com

Answer 1

如果存在有限数量的匹配字符串,这意味着您可以构造一个树,从根到叶读取,类似的字符串将占用类似的分支.

这也称为trie或Radix Tree.

例如,我们可能有字符串cat, coach, con, conch以及dark, dad, dank, do.他们的特里可能看起来像这样:

搜索树中的一个单词将从根开始搜索树.使它成为叶子将对应于与种子的匹配.无论如何,字符串中的每个字符都应与其中一个孩子匹配.如果没有,您可以终止搜索(例如,您不会考虑以"g"开头的任何单词或以"cu"开头的任何单词).

有各种算法用于构建树以及搜索它以及在运行中修改它,但我想我会给出解决方案的概念性概述而不是特定的,因为我不知道最好的算法它.

从概念上讲,您可能用于搜索树的算法将与字符串中的字符在给定时间点可能采用的固定数量的类别或值的基数排序背后的想法相关.

这使您可以根据单词列表检查一个单词.因为你正在寻找这个单词列表作为输入字符串的子字符串,所以它会比这更多.

编辑:正如其他答案所提到的,用于字符串匹配的Aho-Corasick算法是一种用于执行字符串匹配的复杂算法,包括带有附加链接的trie,用于在树中获取"快捷方式"并具有不同的搜索模式.(作为一个有趣的说明,Alfred Aho也是流行的编译器教科书,编译器:原理,技术和工具以及算法教科书,计算机算法的设计和分析的贡献者.他也是贝尔的前成员实验室.玛格丽特J.科拉西克似乎没有太多关于她自己的公共信息.)

Answer 2

您可以使用Aho-Corasick算法

它构建了trie/automaton,其中一些顶点标记为终点,这意味着字符串有种子.

它内置O(sum of dictionary word lengths)并给出答案 O(test string length)

好处:

• 它特别适用于几个词典单词,检查时间不依赖于单词的数量(如果我们不考虑它不适合内存的情况等)
• 该算法并不难实现(至少比较后缀结构)

如果它是ASCII(非ASCII字符无论如何都不匹配),你可以通过降低每个符号使它不区分大小写

Answer 3

您应该尝试预先存在的正则表达式实用程序,它可能比您的手动滚动算法慢,但正则表达式是关于匹配多种可能性,因此它可能已经比哈希映射快几倍或者对所有字符串进行简单比较.我相信正则表达式实现可能已经使用了RiaD提到的Aho-Corasick算法,所以基本上你可以随意使用经过良好测试和快速实现.

如果你有C++ 11,你已经有了一个标准的正则表达式库

#include <string>
#include <regex>

int main(){
     std::regex self_regex("google|yahoo|stackoverflow");
     regex_match(input_string ,self_regex);
}

我希望这能生成最好的最小匹配树,所以我希望它真的很快(可靠!)

Answer 4

其中一种更快的方法是使用后缀树https://en.wikipedia.org/wiki/Suffix_tree,但这种方法有很大的缺点 - 难以构建数据结构.该算法允许从线性复杂度的字符串构建树https://en.m.wikipedia.org/wiki/Ukkonen%27s_algorithm

Answer 5

编辑:正如Matthieu M.指出的那样,OP询问字符串是否包含关键字.我的答案仅在字符串等于关键字时才有效,或者您可以通过空格字符拆分字符串.

特别是对于大量可能的候选者并且在编译时使用像gperf这样的工具使用完美的哈希函数来了解它们是值得一试的.主要原则是,您使用种子生成一个生成器,并生成一个包含散列函数的函数,该函数不会对所有种子值发生冲突.在运行时,您为函数提供一个字符串,它计算哈希值,然后检查它是否是唯一可能与哈希值对应的候选项.

运行时成本是对字符串进行哈希处理,然后与唯一可能的候选项进行比较(种子大小为O(1),字符串长度为O(1)).

要使比较大小写不敏感,只需在种子和字符串上使用tolower即可.