php - ASCII「画像」で一致する「垂直」正規表現

Question

注: これは、最新の正規表現フレーバーの可能性についての質問です。これは、他の方法を使用してこれを解決する最善の方法ではありません。以前の質問に触発されましたが、その質問は正規表現に限定されません。

問題

次のような ASCII "image"/art/map/string で:

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

X3 つの s の単純な垂直線の構成を見つけたいと思います。

X
X
X

画像内の線の数は可変で、各線の幅も可変です。

質問）

正規表現 (PCRE/PHP、Perl、.NET など) を使用すると、次のことが可能になります。

そのようなフォーメーションが存在するかどうかを判断する
そのようなフォーメーションの数を数えます/それらすべての開始点を一致させます（上記の例では4つ）

score 39 · Accepted Answer

質問 1 への回答

最初の質問に答えるには、次を使用できます。

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except \n
    (?=                  # lookahead
        .*+\n            # go to next line
        ( \1?+ . )       # add a character to the 1st capturing group
        .*+\n            # next line
        ( \2?+ . )       # add a character to the 2nd capturing group
    )
)*?                      # repeat as few times as needed
X .*+\n                  # X on the first line and advance to next line
\1?+                     # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+\n                  # X on the 2nd line and advance to next line
\2?+                     # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X                        # X on the 3rd line

Online demo

この式は Perl、PCRE、Java で機能し、.NET でも機能するはずです。

この式は、自己参照キャプチャグループで先読みを使用して、先読みの繰り返しごとに文字を追加します (これは "カウント" に使用されます)。

\1?+一致する (または定義されている) 場合\1はそれを消費し、返さない (バックトラックしない) ことを意味します。この場合、と同等(?(1) \1 )です。つまり、定義されている\1場合に一致します。\1

polygenelubricantsは、 How can we match a^nb^n with Java regex?に対する彼の回答で、後方参照を使用したこの種の先読みについて非常にうまく説明しています。. (彼は、後方参照とルックアラウンドを含む Java 正規表現の他の印象的なトリックについても書いています。)

質問 2 への回答

プレーンマッチング

マッチングのみを使用し、一致数で回答 (カウント) を要求する場合、質問 2 の回答は次のようになります。

後読みが制限されている正規表現フレーバーでは直接解決できません。Java や .NET などの他のフレーバーでも可能ですが (たとえば、m.buettner の .NET ソリューションなど)。

したがって、Perl および PCRE (PHP など) での単純な正規表現の一致は、この場合、この質問に直接答えることができません。

（半？）プルーフ

可変長後読みが使用できないと仮定します。

.の前の行の文字数を何らかの方法でカウントする必要がありXます。
これを行う唯一の方法は、それらを一致させることです。可変長の後読みは使用できないため、(少なくとも) 行頭で一致を開始する必要があります。
行の先頭で一致を開始すると、行ごとに最大 1 つの一致しか取得できません。

1 行に複数回出現する可能性があるため、これではすべてがカウントされず、正しい答えが得られません。

長さ/間接的な解決策

一方、答えを試合の長さまたは交代結果として受け入れる場合、2番目の質問はPCREとPerl（およびその他のフレーバー）で答えることができます。

このソリューションは、m.buettner の「部分的 PCRE ソリューション」に基づいています。

次の式のすべての一致をに置き換えるだけ$3で、結果の文字列の長さとして質問 2 (関心のあるパターンの数) の答えが得られます。

^
(?:
    (?:                   # match .+? characters
        .
        (?=               # counting the same number on the following two lines
            .*+\n
            ( \1?+ . )
            .*+\n
            ( \2?+ . )
        )
    )+?
    (?<= X )              # till the above consumes an X
    (?=                   # that matches the following conditions
        .*+\n
        \1?+
        (?<= X )
        .*+\n
        \2?+
        (?<= X )
    )
    (?=                   # count the number of matches
        .*+\n
        ( \3?+ . )        # the number of matches = length of $3
    )
)*                        # repeat as long as there are matches on this line
.*\n?                     # remove the rest of the line

Perl では次のように記述できます。

$in =~ s/regex/$3/gmx;
$count = length $in;

Online demo

この式は、上記の質問 1 の解決策に似ていますが、最初の先読みで一致した文字に含めるためのいくつかの変更がありX、量指定子でラップされ、量指定子の一致数がカウントされます。

直接一致を除いて、これは可能な限り近いものであり (正規表現以外の追加のコードに関して)、質問 2 に対する受け入れ可能な回答になる可能性があります。

テストケース

上記のソリューションのいくつかのテストケースと結果。数値の回答 (結果の文字列の長さ) を示す結果と、置換後の結果の文字列を括弧内に示します。

Test #0:
--------------------
X
X
X

result: 1 (X)


Test #1:
--------------------
..X....
..X....
..X....

result: 1 (.)


Test #2:
--------------------
..X.X..
..X.X..
....X..

result: 1 (.)


Test #3:
--------------------
..X....
..X....
...X...

result: 0 ()


Test #4:
--------------------
..X....
...X...
..X....

result: 0 ()


Test #5:
--------------------
....X..
.X..X..
.X.....

result: 0 ()


Test #6:
--------------------
.X..X..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

result: 5 (XXXXX)


Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)

score 28 · Accepted Answer

編集

次の解決策には、2 つの重大な問題があります。

進行しすぎるためXXX、同じ行で始まる複数のシーケンスに一致することはできません。pos
X2 番目の解決策は正しくありません。2 つの行が互いに上にある連続した行に一致します。必ずしも3つ連続する必要はありません。

したがって、すべての賛成票 (および報奨金) は、m.buettnerの包括的な .NET 回答またはQtax自身からの魅力的な PCRE 回答のいずれかに送られる必要があります。

元の回答

これは、正規表現への Perl コードの埋め込みを使用した回答です。Perl 正規表現は、コードを使用して正規表現内の任意の条件をアサートしたり、部分的な正規表現を発行したりできるため、通常の言語または文脈自由言語の一致に限定されず、チョムスキー階層の上位にある言語の一部と一致できます。

一致させたい言語は、正規表現で次のように記述できます。

^ .{n} X .*\n
  .{n} X .*\n
  .{n} X

はn数字です。これは、文脈依存言語の標準的な例である a n b n c n 言語に一致^させる^のと^同じくらい複雑です。

最初の行は簡単に照合でき、Perl コードを使用して他の行の正規表現を発行できます。

    /^ (.*?) X
       (?: .*\n (??{"." x length($1)}) X){2}
    /mx

短かった！それは何をするためのものか？

^ (.*?) X行の先頭にアンカーを置き、できるだけ少ない非改行文字に一致させ、次に . に一致させますX。Xas capture groupまでのラインナップを覚えています$1。
行の残りの改行に一致するグループを 2 回繰り返し、と同じ長さの文字列に一致する正規表現を挿入します$1。その後、X.

この正規表現は、3 つが重なっているすべての文字列に一致するようになりXました。

そのようなシーケンスをすべて抽出したい場合は、気の利いたものにする必要があります。シーケンスが重複する可能性があるため、たとえば

.X
XX
XX
X.

次の試合が始まる位置は、最初の試合を過ぎてはなりませんX。これは、後読みと先読みを介して行うことができます。Perl は一定長の後読みのみをサポートしますが、 \K同様のセマンティクスを提供するエスケープを備えています。したがって

/^ (.*?) \K X
   (?=( (?: .*\n (??{"."x length($1)}) X ){2} ))
/gmx

3 つの垂直Xes のすべてのシーケンスに一致します。試験時間:

$ perl -E'my$_=join"",<>; say "===\n$1X$2" while /^(.*?)\KX(?=((?:.*\n(??{"."x length($1)})X){2}))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXX
===
X.X...X..X.....
X....XXXXXX.....
X
===
X....XXXXXX.....
X..XXX...........
.....X
===
..............X
..X...........X....
..X...........X

注: これは、少なくとも Perl 5、v10 以降で利用可能な実験的な正規表現機能に依存しています。コードは v16 perl でテストされました。

コードを埋め込まないソリューション

行を見てみましょう

...X...\n
...X..\n

...各行の先頭部分は同じ長さであると断言したい。base case を使用した再帰によってこれを行うことができますX.*\n。

(X.*\n|.(?-1).)X

それを行頭に固定すると、2 つの垂直Xes を一致させることができます。2 行以上を一致させるには、先読みで再帰を実行してから、一致位置を次の行に進めて繰り返す必要があります。このために、単純にを一致させ.*\nます。

Xこれにより、3 つの垂直esを持つ文字列に一致する次の正規表現が得られます。

/ ^
  (?:
    (?=( X.*\n | .(?-1). ) X)
    .*\n # go to next line
  ){2}
/mx

しかし、このようなすべてのシーケンスに一致させたいので、これでは十分ではありません。これを行うために、基本的に正規表現全体を先読みに入れます。正規表現エンジンは、新しい一致を生成するたびに位置を確実に進めます。

/ ^
  (?=
    (
      (?:
          (?= (X.*\n | .(?-1). ) X)
          .*\n # go to next line
      ){2}
      .* # include next line in $1
    )
  )
/mx

試験時間:

$ perl -E'my$_=join"",<>; say "===\n$1" while /^(?=((?:(?=(X.*\n|.(?-1).)X).*\n){2}.*))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
===
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
===
X....XXXXXX.....
X..XXX...........
.....X..........
===
..............X
..X...........X....
..X...........X....X...

したがって、これは埋め込みコードを使用したソリューションと同様に機能します。つまり、Xes の各グループではなく、行の各グループを垂直 es に一致させXます。(実際、このソリューションは、埋め込みコードよりも壊れやすいようです)

score 11 · Accepted Answer

単一の「垂直」パターンを見つけたい場合は、次の解決策があります。「水平」パターンも一致させたい場合は、別の一致で試してみてください。おそらく、重複する一致位置を確認してください。コンピュータは線が何であるかを認識していないことに注意してください。人間が勝手に作ったものです。文字列は、いくつかの文字を行末に指定する 1 次元のシーケンスです。

#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;

my $pattern = qr/XXX/p;

my $string =<<'HERE';
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
HERE


$transposed = transpose_string( $string );

open my $tfh, '<', \ $transposed;
while( <$tfh> ) {
    while( /$pattern/g ) {
        my $pos = pos() - length( ${^MATCH} );
        push @found, { row => $pos, col => $. - 1 };
        pos = $pos + 1; # for overlapping matches
        }
    }

# row and col are 0 based
print Dumper( \@found ); use Data::Dumper;

sub transpose_string {
    my( $string ) = @_;

    open my $sfh, '<', \ $string;

    my @transposed;
    while( <$sfh> ) {
        state $row = 0;
        chomp;
        my @chars = split //;

        while( my( $col, $char ) = each @chars ) {
            $transposed[$col][$row] = $char;
            }

        $row++;
        }

    my @line_end_positions = ( 0 );
    foreach my $col ( 0 .. $#transposed ) {
        $transposed .= join '', @{ $transposed[$col] };
        $transposed .= "\n";
        }
    close $sfh;

    return $transposed;
    }

score 2 · Accepted Answer

2

画像を回転させて、を検索できますXXX。

于 2013-06-11T08:35:47.573 に答える

score 0 · Accepted Answer

PHPを使用して垂直パターンを一致させる私のアプローチ。

まず、入力を 90° 回転させます。

// assuming $input contains your string
$input = explode("\n", $input);
$rotated = array();
foreach ($input as $line)
{
    $l = strlen($line);
    for ($i = 0; $i < $l; $i++)
    {
        if (isset($rotated[$i]))
            $rotated[$i] .= $line[$i];
        else
            $rotated[$i] = $line[$i];
    }
}
$rotated = implode("\n", $rotated);

これにより、

..XXX.....
..........
.XX....XX.
....X.....
X...X....X
.X.XXX....
..XX......
...X......
...X......
.XXX......
...X.....
.........
........
........
....XXX
.....
...
..
..
X
.
.
.

これは奇妙に見えるかもしれませんが、実際には簡単に処理できるようになったので、実際に近づくことができますpreg_match_all()。

if (preg_match_all('/\bXXX\b/', $rotated, $m))
var_dump($m[0]);

出来上がり：

array(4) {
  [0] =>
  string(3) "XXX"
  [1] =>
  string(3) "XXX"
  [2] =>
  string(3) "XXX"
  [3] =>
  string(3) "XXX"
}

同じ水平パターンも一致させたい場合は、回転していない入力で同じ式を使用するだけです。