如何识别文本中的一组关键词

我有一大组关键词。给定一个文本，我希望能够只识别那些出现在关键字列表中的单词，并忽略所有其他单词。解决这个问题的最好方法是什么？如何识别文本中的一组关键词

2011-05-20 kc3

Aho-Corasick algorithm是用于识别较大源串中一组模式字符串的快速算法。由于它运行时间为O（m + n + z），其中n是您尝试匹配的所有模式字符串的总大小，因此它由多个搜索实用程序以及许多防病毒程序使用，m是要搜索的字符串，z是匹配的总数。此外，如果您事先知道要搜索的字符串，则可以离线执行O（n）工作，并将搜索时间缩短为O（m + z）。

来源

2011-05-20 16:07:41 templatetypedef

字符串和单词之间有区别。该算法的一个关键思想是，当你不能匹配'foo'时，它知道你可能会匹配'oof'。但是，如果你想匹配整个单词，那不是真的。 – btilly 2011-05-20 16:55:58

这是一个好点。你可以在字符串之前和之后存储空格（例如，“HELLO”存储为“HELLO”，或者也可以使用句点和点作为边界） – templatetypedef 2011-05-20 22:28:07

实际上是愚蠢的错误当你不能匹配foo ''你可能会匹配'''，但不* *'oof'。反正只是略过算法的复杂性并且只使用一个trie。 – btilly 2011-05-20 22:34:09

把你的关键字放入一个数据结构，以便于查找。例如，一个哈希表或二叉树。如果你是核心人物，你可以从你的关键字创建一个完美的散列。
使用DFA将输入分解为“单词”。这可以使用正则表达式库或简单的状态机来完成。
查找每个“单词”以查看它是否是您的关键字之一。

来源

2011-05-20 16:13:22

将您的文字存储在trie中。

走你的文字。每当你开始一个单词时，开始走路。如果你在单词结尾的单词结尾，这是你感兴趣的单词，否则它不是。

围绕单词的定义，你会有轻微的复杂化。特别是非单词字符通常以单词结尾，但也有例外，如don't。

请注意，某些正则表达式引擎（Perl的任何最新版本的Perl）都足够智能，可以自动构建一个树并尝试与其匹配。因此，你很有可能只用管道将你的单词连接起来，然后将它放在正则表达式引擎中，并获得良好的性能。

如果这不起作用，您可以构造一个正则表达式来编码一个trie。例如，给定列表foo,bar,baz,blat正则表达式/\b(foo|b(?:a(?:r|z)|lat))\b/应该匹配那些词并且仅匹配那些词。它可能不会像手动C那样高效（例如在Perl的引擎中，你会遇到对慢性能复杂正则表达式的检查，并且它可能会做一些愚蠢的回溯操作，它不需要做）但将很多放在一起工作较少。

来源

2011-05-20 17:10:57 btilly

如果我的关键词列表是10000左右。方法仍然有效吗？ – kc3 2011-05-20 17:52:30

@ kc3：是的，建立一个trie的努力大致与你所有单词中的字母总数成正比，一旦建立，匹配的时间大致与文本的大小成比例。大概是因为你存储可以引入各种因素的trie的一些实现细节。 – btilly 2011-05-20 18:19:25

如何识别文本中的一组关键词

回答

相关问题