regex - 从大量文本中提取数千个简单模式的快速算法

Question

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

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

等等

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

Answer 1

您可以使用 (f)lex 生成 DFA，它并行识别所有文字。如果存在太多通配符，这可能会变得棘手，但它适用于多达大约 100 个文字(对于 4 个字母的字母表；对于自然文本可能更多)。您可能想要抑制默认操作 (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 输入生成类似于上面的脚本。