4

我希望能够有效地匹配 GB 文本中的数千个正则表达式，因为我知道这些正则表达式中的大多数都相当简单，例如：

\b巴拉克\s（侯赛因\s）？奥巴马\b
\b(约翰|J\.)\sBoehner\b

等等

我目前的想法是尝试从每个正则表达式中提取某种最长的子字符串，然后使用 Aho-Corasick 匹配这些子字符串并消除大部分正则表达式，然后匹配所有剩余的正则表达式组合。谁能想到更好的东西？

4

4 回答 4

2

您可以使用 (f)lex 生成一个 DFA，它可以并行识别所有文字。如果存在太多通配符，这可能会变得很棘手，但它最多可用于大约 100 个文字（对于 4 个字母的 alfabet；对于自然文本可能更多）。您可能想要禁止默认操作 (ECHO)，并且只打印匹配项的行号和列号。

[我假设 grep -F 也差不多]

%{
/* C code to be copied verbatim */
#include <stdio.h>
%}

%%

"TTGATTCACCAGCGCGTATTGTC" { printf("@%d: %d:%s\n", yylineno, yycolumn, "OMG! the TTGA pattern again"  ); }


"AGGTATCTGCTTCAATCAGCG" { printf("@%d: %d:%s\n", yylineno, yycolumn, "WTF?!"  ); } 

... 
more lines
...

[bd-fh-su-z]+ {;}

[ \t\r\n]+ {;}

. {;}

%%

int main(void)
{
/* Call the lexer, then quit. */
yylex();
return 0;
}

可以使用 awk 或任何其他脚本语言从 txt 输入生成像上面这样的脚本。

于 2012-01-03T14:35:21.230 回答
0

如果您需要快速实现某些特定情况，您可以自己实现Aho-Corasick 算法的后缀树。但在大多数情况下，如前所述，将所有正则表达式合并为单个正则表达式也不错

于 2012-01-03T13:30:48.617 回答
0

比在每个文件上运行每个正则表达式更智能的实现：

For each regex:
    load regex into a regex engine
    assemble a list of regex engines
For each byte in the file:
    insert byte to every regex engine
      print results if there are matches

但我不知道有任何程序已经这样做了——你必须自己编写代码。这也意味着你有内存来保持正则表达式状态，并且你没有任何邪恶的正则表达式

于 2012-01-02T23:47:35.093 回答
0

我不确定你是否会打破一些正则表达式的大小限制，但你可以将它们全部组合成一个巨大的正则表达式：

((\bBarack\s(Hussein\s)?Obama\b)|(\b(John|J\.)\sBoehner\b)|(etc)|(etc))

如果你达到了一些限制，你可以一次用 100 个块来做这个，或者你可以管理多少个

于 2012-01-03T00:58:43.783 回答