1

Adblock Plus ルールの一連の正規表現を、C++ から呼び出すことができる最適化された関数に変換しようとしています。

Ragel などのレクサー ジェネレーターを使用してこれを行うことができると期待していましたが、非常に小さな正規表現のセットで試してみると、メモリ使用量が 30 GB を超えて非常に高くなり、Ragel はエラー メッセージも出力ファイルも生成せずに終了しました。

問題を解決するために最適化できる愚かなことをしているのかどうかを理解しようとしています。

#include <string.h>
namespace xab{
 %%{
machine lexer;
WILDCARD = /[A-Za-z0-9;\/\?:@=&$_\.\+!\*'~#^,%:\-]/*;
SUBDOMAIN = /([A-Za-z]([A-Za-z0-9\-]*[A-Za-z0-9])?\.)+/;
SEPERATOR = /[:\/\?=&]/;
main := 
(WILDCARD '&prvtof=' WILDCARD '&poru=' WILDCARD) |
(WILDCARD '.a3s?n=' WILDCARD '&zone_id=' WILDCARD) |
(WILDCARD '/addyn|' WILDCARD ';adtech;' WILDCARD) |
(WILDCARD '/addyn|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/adiframe|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/adserv|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/affiliates.' WILDCARD '.aspx?' WILDCARD) |
(WILDCARD '/affiliates/' WILDCARD '/show_banner.' WILDCARD) |
(WILDCARD '/banner_js.' WILDCARD '?' WILDCARD) |
(WILDCARD '/bannerframe.' WILDCARD '?' WILDCARD) |
(WILDCARD '/banners.' WILDCARD '&iframe=' WILDCARD) |
(WILDCARD '/bannerview.' WILDCARD '?' WILDCARD) |
(WILDCARD '/bannery/' WILDCARD '?banner=' WILDCARD) |
(WILDCARD '/cdn-cgi/pe/bag?r[]=' WILDCARD 'cpalead.com' WILDCARD) |
(WILDCARD '/delivery/' WILDCARD '?advplaces=' WILDCARD) |
(WILDCARD '/eas?camp=' WILDCARD ';cre=' WILDCARD) |
(WILDCARD '/eas?cu=' WILDCARD ';cre=' WILDCARD) |
(WILDCARD '/eas?cu=' WILDCARD ';ord=' WILDCARD) |
(WILDCARD '/ireel/ad' WILDCARD '.jpg' WILDCARD) |
(WILDCARD '/is.php?ipua_id=' WILDCARD '&search_id=' WILDCARD);
write data; 
}%%
bool matchBlacklist(const char *data) {
const char *p = data;

const char *pe = data + strlen(data);
int cs;
//write init
%% write init; 
// write exec
%% write exec;
if (cs >= lexer_first_final)
return true;
return false;
}
}
4

1 に答える 1

1

私の知る限り、あなたは「DFA宇宙爆発」に直面しています。

DFA は、文字列の1 回のパスですべてのルールを照合する必要があります。これを行うには、すべての状態に、1) すべてのルールの先頭へ、および 2) すべてのインターリーブ ルールの中間への遷移が必要です。

さらに、WILDCARDたとえば、WILDCARD '&prvtof=' WILDCARD '&poru=' WILDCARDルールではWILDCARDが に一致するため、 は「非決定論的動作」を作成している可能性があります&prvtof=。これと、 の膨大な量のオプションがWILDCARD、DFA をさらに爆発させる可能性があります。

Ragel 6.8 マニュアルの「2.5.5 連結」セクションと「4. 非決定性の制御」セクションに、DFA を単純化する方法に関するガイドラインがあります。

「DFA スペース爆発」を回避するには、スキャナーを使用して Ragel マシンを「最適化解除」し、「ステートレス」DFA からバックトラッキングに選択的に切り替えます。また、強い差分演算子を使用して、非決定性を減らしたい場合もあります。WILDCARDを単純化して、 に置き換えたいと思うかもしれませんany。

action matched {return true;}
main := |*
  '&prvtof=' (any* -- '&poru=') '&poru=' => matched;
  '.a3s?n=' (any* -- '&zone_id=') '&zone_id=' => matched;
  any;
*|
于 2014-04-28T15:16:21.937 に答える