搜索文本中单词列表的算法

还有是不是一个哈希表更好的解决方案.如果您要在大量文本中搜索一组固定的单词,那么您使用Aho-Corasick字符串匹配算法的方式就是这样.

该算法根据您要搜索的单词构建状态机,然后通过该状态机运行输入文本,在找到匹配项时输出匹配项.因为构建状态机需要一些时间,所以该算法最适合搜索非常大的文本体.

你可以用正则表达式做类似的事情.例如,您可能希望在某些文本中找到"dog","cat","horse"和"skunk"等字样.您可以构建正则表达式:

"dog|cat|horse|skunk"

然后在文本上运行正则表达式匹配.如何获得所有匹配将取决于您的特定正则表达式库,但它确实有效.对于非常大的单词列表,您将需要编写读取单词并生成正则表达式的代码,但这并不是非常困难,而且效果非常好.

但是,正则表达式的结果和Aho-Corasick算法的结果存在差异.例如,如果你在字符串"我的业力吃了你的教条"中搜索"dog"和"dogma"这两个词.正则表达式库搜索将报告发现"教条".Aho-Corasick实施将报告在同一位置找到"狗"和"教条".

如果您希望Aho-Corasick算法仅报告整个单词,则必须稍微修改算法.

正则表达式也将报告部分单词的匹配.也就是说,如果你正在寻找"狗",它会在"教条"中找到它.但是你可以修改正则表达式只给出整个单词.通常情况下,这完成了\b,如:

"\b(cat|dog|horse|skunk)\b"

您选择的算法很大程度上取决于输入文本的大小.如果输入文本不是太大,您可以创建您要查找的单词的哈希表.然后浏览输入文本,将其分解为单词,并检查哈希表以查看该单词是否在表中.在伪代码中:

hashTable = Build hash table from target words
for each word in input text
    if word in hashTable then
        output word

或者,如果您需要输入文本中匹配单词的列表:

hashTable = Build hash table from target words
foundWords = empty hash table
for each word in input text
    if word in hashTable then
        add word to foundWords