4

我有大量的单词和短语（词典或字典），其中包括通配符。我需要在更小的字符串（目前约 150 个字符）中找到这些单词和短语的所有实例。

最初，我想反向运行该操作；那就是检查我的较小字符串中的每个单词是否存在于词典中，这可以实现为哈希表。问题是我的 Lexicon 中的一些值不是单个单词，而且很多是通配符（例如 substri*）。

我正在考虑使用Rabin-Karp 算法，但我不确定这是最佳选择。

执行此操作的有效算法或方法是什么？

样本数据：

该词典包含数百个单词，并且可能会扩展。这些词可能以通配符（星号）结尾。以下是一些随机示例：

  • 好的
  • 坏的
  • 释放*
  • 粗心*
  • 损失惨重

我们正在分析的文本（此时）是简短的、非正式的（语法方面的）英语陈述。文本的主要示例（同样，此时此刻）将是 Twitter 推文。这些限制为大约 140 个字符。例如：

Just got the Google nexus without a contract. Hands down its the best phone 
I've ever had and the only thing that could've followed my N900.

虽然注意到我们正在对本文进行非常简单的情绪分析可能会有所帮助；我们的情绪分析技术不是我关心的。我只是将现有解决方案迁移到“实时”处理系统，并且需要执行一些优化。

4

7 回答 7

6

我认为这是Aho-Corasick 字符串匹配算法的一个很好的用例，它专门设计用于在单个字符串中查找大量字符串的所有匹配项。它分两个阶段运行 - 第一个阶段是创建匹配自动机（可以提前完成并且只需要线性时间），第二个阶段是使用自动机查找所有匹配项（只需要线性时间，加上与匹配总数成正比的时间）。该算法也可以适用于支持通配符搜索。

希望这可以帮助！

于 2013-04-04T16:50:08.783 回答
3

我想抛出的一个答案是Boyer-Moore搜索算法。它是grep使用的算法。Grep 可能是最快的搜索工具之一。此外，您可以使用GNU Parallel之类的东西让 grep 并行运行，从而真正加快算法速度。

此外，这是一篇您可能会感兴趣的好文章。

于 2013-04-04T18:37:20.850 回答
2

您可能仍会使用您最初的想法，即根据字典检查文本中的每个单词。但是，为了有效地运行它，您需要为字典编制索引，以使查找速度非常快。信息检索系统中使用的一个技巧是存储所谓的permuterm 索引( http://nlp.stanford.edu/IR-book/html/htmledition/permuterm-indexes-1.html )。

基本上你想要做的是在字典中存储单词的所有可能排列（例如对于房子）：

house$
ouse$h
use$ho
...
e$hous

然后可以使用此索引快速检查通配符查询。例如，如果您有 ho*e，您可以在 permuterm 索引中查找以 开头的术语e$ho，您会很快找到与 house 的匹配项。

搜索本身通常使用一些对数搜索策略（二进制搜索或 b 树）完成，因此通常非常快。

于 2013-04-04T18:22:48.690 回答
2

只要模式是完整的单词：你不想or匹配storage；空格和标点符号是匹配锚，那么一个简单的方法是将您的词典转换为扫描仪生成器输入（例如您可以使用flex），生成一个扫描仪，然后在您的输入上运行它。

扫描器生成器旨在识别输入中出现的标记，其中每个标记类型由正则表达式描述。Flex 和类似程序可以快速创建扫描仪。默认情况下，Flex 最多可以处理 8k 条规则（在您的情况下是词典条目），并且可以扩展。生成的扫描仪以线性时间运行，实际上速度非常快。

在内部，令牌正则表达式在标准的“Kleene 定理”管道中进行转换：首先转换为 NFA，然后转换为 DFA。然后将 DFA 转换为其唯一的最小形式。这是在 HLL 表中编码的，该表在通过引用表来实现扫描器的包装器内发出。这就是 flex 所做的，但其他策略也是可能的。例如，可以将 DFA 转换为goto代码，其中 DFA 状态在代码运行时由指令指针隐式表示。

space-as-anchors 警告的原因是，由像 Flex 这样的程序创建的扫描仪通常无法识别重叠匹配： 例如，strangers不能同时匹配strangers和range。

这是一个与您提供的示例词典相匹配的 flex 扫描器：

%option noyywrap
%%
"good"                    { return 1; }
"bad"                     { return 2; }
"freed"[[:alpha:]]*       { return 3; }
"careless"[[:alpha:]]*    { return 4; }
"great"[[:space:]]+"loss" { return 5; }
.                         { /* match anything else except newline */ }
"\n"                      { /* match newline */ }
<<EOF>>                   { return -1; }
%%
int main(int argc, char *argv[])
{
  yyin = argc > 1 ? fopen(argv[1], "r") : stdin;
  for (;;) {
    int found = yylex();
    if (found < 0) return 0;
    printf("matched pattern %d with '%s'\n", found, yytext);
  }
}

并运行它：

$ flex -i foo.l
$ gcc lex.yy.c
$ ./a.out
Good men can only lose freedom to bad
matched pattern 1 with 'Good'
matched pattern 3 with 'freedom'
matched pattern 2 with 'bad'
through carelessness or apathy.
matched pattern 4 with 'carelessness'
于 2013-04-06T16:57:42.163 回答
1

这并不能准确回答算法问题，但请查看re2库。Python、Ruby 和其他各种编程语言都有很好的接口。以我的经验，它的速度非常快，并且在我的代码中消除了非常相似的瓶颈，几乎没有大惊小怪，而且我几乎没有额外的代码。

唯一的复杂性来自重叠模式。如果您希望模式从单词边界开始，您应该能够将字典划分为一组正则表达式r_1, r_2, ..., r_k，\b(foobar|baz baz\S*|...)其中每个组 inr_{i+1}都有一个前缀 in r_i。然后您可以短路评估，因为如果r_{i+1}匹配则r_i必须匹配。

除非您在高度优化的 C 中实现您的算法，否则我敢打赌，这种方法将比该线程中其他地方的任何（算法上优越的）答案更快。

于 2013-04-05T07:13:30.310 回答
0

让我说清楚。您有一大组查询和一个小字符串，您想在该字符串中查找所有这些查询的实例。

在这种情况下，我建议您疯狂地索引该小文档，以便您的搜索时间尽可能短。地狱。有了这样的文档大小，我什至会考虑做一些小的突变（匹配通配符等）并且也会对它们进行索引。

于 2013-03-28T19:48:46.373 回答
-1

我有一个非常相似的任务。这是我解决它的方法，性能令人难以置信 http://www.foibg.com/ijita/vol17/ijita17-2-p03.pdf

于 2015-03-18T08:05:03.497 回答