2

ここに入力ファイル(解凍してください) と以下のコードがあります。print "pat=\n"; の直後。Windows タスク マネージャー Perl(v5.010000) で 25% の CPU 時間を使用しているのを確認しながら、パターン マッチでハングします。

use strict;
open FP, "<default.php" or die "can't read";

$/ = undef;    

my $content = <FP>;

while ( $content =~ /(['"])([^\s\x00-\x1f]{300,})\1/gs ) {
#looks like we've found base encoded string etc
    my $subpat = $2;
    print "pat=<$subpat>\n";
    if ( $subpat =~ m#(?:(....).{5,30}(?=\1)){50}#s ) {
      print "hello world";
    } else {
      die("");
    }
    exit;
}

編集: 理想的には、各グループのサイズが最大 4 + 30 バイト、最小 4 + 5 バイトである連続したグループ (最大 50) 内のバイト (長さ:4) の均一な繰り返しパターンを把握したいものです。

例 (サイズが 1 から 30 バイトの各グループで「=>」を繰り返す):

'cs'=>'チェコ語','da'=>'デンマーク語','nl'=>'オランダ語','fi'=>'フィンランド語','fr'=>'フランス語','de'=> 'ドイツ語','el'=>'ギリシャ語',

行: print "pat=\n"; 以下を出力してハングします。

pat=<,'hr'=>'クロアチア語','cs'=>'チェコ語','da'=>'デンマーク語','nl'=>'オランダ語','fi'=>'フィンランド語',' fr'=>'French','de'=>'German','el'=>'Greek','hi'=>'Hindi','it'=>'Italian','ja'=>'日本語','ko'=>'韓国語','no'=>'ノルウェー語','pl'=>'ポーランド語','pt'=>'ポルトガル語','ro'=>'ルーマニア語','ru '=>'ロシア語','es'=>'スペイン語','sv'=>'スウェーデン語','ca'=>'カタロニア語','tl'=>'フィリピン語','iw'=>'ヘブライ語','id'=>'インドネシア語','lv'=>'ラトビア語','lt'=>'リトアニア語','sr'=>'セルビア語','sk'=>'スロバキア語','sl'=>'スロベニア語','uk'=>'ウクライナ語','vi'=>'ベトナム語' ,'sq'=>'アルバニア語','et'=>'エストニア語','gl'=>'ガリシア語','hu'=>'ハンガリー語','mt'=>'マルタ語','th'= >'タイ語','tr'=>'トルコ語','fa'=>'ペルシャ語','af'=>'アフリカーンス語','ms'=>'マレー語','sw'=>'スワヒリ語', 'ga'=>'アイルランド語','cy'=>'ウェールズ語','be'=>'ベラルーシ語','is'=>'アイスランド語','mk'=>'マケドニア語','yi'=> 'イディッシュ語','hy'=>'アルメニア語','az'=>'アゼルバイジャン語','eu'=>'バスク語','ka'=>'グルジア語','ht'=>>

4

2 に答える 2

5

Perl の正規表現は特に賢いわけではありません。パターンはバックトラッキングを使用して実装されます。基本的に、各決定ポイント (例: 固定されていない開始点または{5,30}) で、正規表現はその状態をスタックに保存し、可能な限り最小の一致に進みます。行き詰まると、スタックから 1 レベルポップします。

入力のサイズが制限されているため、通常、これは非常にうまく機能します。リテラルまたは文字クラスの一致があり、失敗した一致を早期に遮断し、ネストされた変数繰り返しディレクティブの使用が制限されています。さらに、バックトラッキングが存在しない場合、正規表現は (理論的には、perl はこれを行いませんが) 効率的に実行できる決定論的有限オートマトンに変換できます。

ここでは、多数のワイルドカード マッチ、大きな入力文字列に加えて、実質的に 50 回の反復ループがあり、真ん中に 25 層の分岐があり、その周りにループがあり、一致の開始と終了を見つけようとします。 . 最悪の場合、正規表現は 25^50 回バックトラックする必要があるかもしれません。これは、開始アンカーまたは終了アンカーがないことを考慮していません。

したがって、このアルゴリズムを機能させるためのより賢い方法を見つける必要があります。文字列のすべての 4 文字の部分文字列を生成し、出現回数を数えてみてください。複数回出現する部分文字列ごとに、見つかった一致のオフセットを調べて、パターンがあるかどうかを確認します。

于 2012-10-13T09:50:32.123 に答える
1

バックトラッキングとそのコストを視覚的に確認する良い方法は、正規表現をRegexp::Debuggerでモデル化することです

バックトラッキングについて詳しく説明している Jeffrey Friedl の「Mastering Regular Expressions」は優れた参考資料です。

于 2012-10-13T13:36:27.573 に答える