4

これらの正規表現のほとんどが次のようにかなり単純になることを知って、GBのテキストから何千もの正規表現を効率的に照合できるようにしたいと思います。

\ bBarack \ s（Hussein \ s）？Obama \ b
\ b（John | J \。）\ sBoehner \ b

等

私の現在のアイデアは、各正規表現からある種の最長の部分文字列を抽出し、Aho-Corasickを使用してこれらの部分文字列を照合し、ほとんどの正規表現を削除してから、残りのすべての正規表現を組み合わせて照合することです。誰かがもっと良いことを考えることができますか？

4

4 に答える 4

2

（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入力から生成できます。

于 2012-01-03T14:35:21.230 に答える
0

If you need really fast implementation of some specific case, you can implement suffix tree of Aho–Corasick algorithm yourself. But in most cases union of all your regexes into single regex, as recommended earlier, will be not bad too

于 2012-01-03T13:30:48.617 に答える
0

正規表現のサイズ制限を破るかどうかはわかりませんが、それらすべてを OR して 1 つの巨大な正規表現にすることができます。

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

制限に達した場合は、一度に 100 個のチャンクで、または管理できる数でこれを行うことができます

于 2012-01-03T00:58:43.783 に答える