7

文字列として表される 2D マトリックスでパターンを検索しようとしています。以下を想像してください。

// horizontal line
String pat1 =
    "............." +
    "............." +
    "............." +
    "....XXXX....." +
    "............." +
    ".............";

// vertical line
String pat2 =
    "............." +
    "......X......" +
    "......X......" +
    "......X......" +
    "......X......" +
    ".............";

最初のパターンを検索するのは簡単です。正規表現は次のようになります。

X+

2 番目のケースでは、行列の列と行の数がわかっているため、少しトリッキーですが実行可能です。

(X.{`WIDTH - 1`})+

次のパターンを認識する方法を見つけようとしているときに、正しい正規表現を思いつくのに問題が発生しました。

// fixed but unknown number of columns
String pat3 =
    "............." +
    ".....XXX....." +
    ".....XXX....." +
    ".....XXX....." +
    ".....XXX....." +
    ".............";

// variable number of columns
String pat4 =
    "............." +
    ".....XXX....." +
    "....XXXXX...." +
    "...XXXXXXX..." +
    ".....XXX....." +
    ".............";

私が探しているのは、次の正規表現パターンを作成する方法です。

(X.{`WIDTH - PREVCOUNT`})+

最後に一致したパターンの長さはどこですかPREVCOUNT(pat4 の 4 行目の最初の X が欠落していることは承知していますが、それで問題ありません)。正規表現に先読みがあることは知っていますが、私が達成しようとしていることがまったく可能かどうか疑問に思っています。可能だったとしても、先読みが内部でどのように機能するかを完全には理解していないため、先読みを使用することによるパフォーマンスへの影響についても心配しています。

単一の正規表現検証でこれを行う方法はありますか、または行ごとに検索してから、X がすべて連続しているかどうかを確認する必要がありますか?

編集：明確にするために、Xの「ブロブ」を検索しようとしています。列/行全体で連続した X がある限り、ブロブに属していると見なすことができます。いくつかの例:

String blob1 =
    "............." +
    "......XX....." +
    "....XXXX....." +
    "...XXXXX....." +
    ".....XXX....." +
    ".............";

String blob2 =
    "............." +
    ".....XXX....." +
    "....XXXXX....." +
    "...XXXXXXX..." +
    "....XXXXX...." +
    ".....XXX.....";


String blob3 =
    "............." +
    ".....XXX....." +
    ".....XXX......" +
    ".....XXX....." +
    "............." +
    ".............";


String notblob =
    "............." +
    "..XXX........" +
    "......XXX....." +
    "..XXX........." +
    ".............." +
    ".............";

私の解決策は正確である必要はないため、おそらくお粗末な正規表現アプローチを使用しようとしています。

4

3 に答える 3

0

私はあなたがここで何をしようとしているのか理解できると思います。定義する「prevcount」は、パターンに一致するのに十分な情報ではありません。チェックするドットの数を決定するには、「次の幅」を考慮する必要があります。ただし、些細なパターンでさえ本当に検証しているかどうかはわかりません。X+ は 5 つの X と連続して一致します。2 番目のパターンでは、最初または最後の行が 2 つの X である可能性がありますが、それは検出されません。

そうは言っても、pat3 で同様の検証を提供する方法は次のとおりです。

(X{3}.{`WIDTH-3`})+

Xパターンを繰り返すことで、おそらく別のタブーを破りましたが、「Xブロック」の開始と終了に合わせて繰り返しパターンを維持するには、それを行う必要があります.

pat4 はさらにトリッキーです。一度に 1 行ずつチェックする検証の順序を保持する実際の方法はありません。あなたはこれを行うことができます：

(X{3}.{`WIDTH-4`}|X{5}.{`WIDTH-6`}|X{5}.{`WIDTH-6`}|X{3}.{`WIDTH-5`})+

ただし、行が入れ替わったマトリックスを検証することは脆弱であり、対応するために X ブロックの両側でドットが変更されます。ただし、一度にすべての行をチェックしてみることができます。

(X{3}.{`WIDTH-4`}X{5}.{`WIDTH-6`}X{5}.{`WIDTH-6`}X{3}.{`WIDTH-5`})

そして、それはパフォーマンスに余分な影響を与えることはありません。正規表現パターンのコンパイルと照合を 1 回だけ開始するオーバーヘッドが発生するだけなので、おそらくより効率的です。

些細な補足: 複数行の文字列にマトリックスの幅を使用している場合、機能しません。改行文字を考慮して、1 つ追加する必要があります。次に、「。」を確認する必要があります。改行文字もキャプチャします。Java では、これに Pattern.DOTALL を使用できます。

于 2013-11-03T06:33:33.663 に答える