5

私はちょうどperlで正規表現を始めました。さまざまなオンライン チュートリアルを試した後、大文字と小文字を区別しない単語の一致を指定した順序に一致する正規表現を書きたいと思いました。

文字列「A」が文字列「B」の単語または一連の単語で構成されているかどうかを判断しようとしていますが、これを大文字と小文字を区別せずに行いたいと考えています。

たとえば、文字列 "B" が "John Von Neumann" の場合、"JOhn"、"Von Neumann"、"VoN"、"john neuMann" は一致しますが、"Joh"、"NeumaNn VoN"、 「ボン」は一致しません。

正規表現でこれを行う方法がわかりません。何か考えはありますか?

4

2 に答える 2

9

大文字と小文字を区別しないでください。

John Von Neumann

で一致させることができます

John Von Neumann    1 1 1
John Von            1 1 0
John     Neumann    1 0 1
John                1 0 0
     Von Neumann    0 1 1
     Von            0 1 0
         Neumann    0 0 1

したがって、探している正規表現パターンは

/^(?:John Von Neumann|John Von|John Newmann|John|...)\z/i

リストを作成する方法は次のとおりです。

sub true_indexes {
   my ($n) = @_;
   my $i = 0;
   my @indexes;
   while ($n) {
      push @indexes, $i if $n & 1;
      ++$i;
      $n >>= 1;
   }
   return @indexes;
}

my @words = split(' ', 'John Von Neumann');

my @patterns;
unshift @patterns, join ' ', @words[ true_indexes($_) ]
   for 1 .. (2**@words)-1;

最後に、パターンを生成できます。

my $pat = join '|', map quotemeta, @patterns;
my $re = qr/$pat/i;

次のように使用します。

if ($input =~ /^$re\z/) {
   print "match\n";
} else {
   print "no match\n";
}
于 2013-02-10T18:25:07.763 に答える
3

ikegami のソリューションは、正規表現に変換される前に文字列を格納するために指数空間を占有します (各単語は 2 n - 1回表示されます。n は単語の数であるため、合計スペースは少なくとも 2 n - 1 * 合計です)。 （単語の長さ））。これは正規表現エンジンとは関係ありません。問題は文字列が正規表現に変換される前にあるためです。

(一致する文字列のセットに関して) ikegami のソリューションに相当する正規表現の構築は次のようになります。

^(?=[^ ])(?:(?: |^)John(?= |\z))?+(?:(?: |^)Von(?= |\z))?+(?:(?: |^)Neumann(?= |\z))?+\z

これは、単語数とすべての単語の合計の長さに関して、線形スペースしか占有しません。

明確にするために：

^
(?=[^ ])
(?:(?: |^)John(?= |\z))?+
(?:(?: |^)Von(?= |\z))?+
(?:(?: |^)Neumann(?= |\z))?+
\z

先読みアサーション(?=[^ ])には 2 つの目的があります。空の文字列が一致しないようにすることと、最初の文字が空白文字でないことを確認することです。

ここではバックトラックが必要ないため?+、量指定子を所有(またはアトミック) にする に注意してください。なんで？これを通常どおり行うと、単語のリストをループして、入力の左端の単語と比較します。一致が見つかったら、入力内のすべての単語が見つかるか、単語のリストのループが終了するまで、ループを続けて入力内の次の単語と比較します。

所有量指定子は、後戻り地獄の発生も防ぎます。単語が一致すると見なされた場合、その単語が再検討されることはありません。

各単語の前にスペースを入れるか、文字列の先頭にすることができます。先読みアサーション(?= |\z)には、同じプレフィックスを持つ単語が最初の試行で間違って一致しないようにする目的があります (たとえば"John Von Vone"、一致を試行し"John Vone"ます)。

バックトラッキングがないため、最悪の場合のパフォーマンスは、すべての単語の長さと入力文字列の長さに関して線形になります (正規表現を使用しない場合と同じです)。

正規表現を少し変更して、柔軟な間隔を許可できます。

^(?= *+[^ ])(?: *+John(?= |\z))?+(?: *+Von(?= |\z))?+(?: *+Neumann(?= |\z))?+ *+\z

明確にするために（先頭のスペースは重要です）：

^
(?= *+[^ ])
(?: *+John(?= |\z))?+
(?: *+Von(?= |\z))?+
(?: *+Neumann(?= |\z))?+
 *+
\z

先頭の先読み(?= *+[^ ])により、入力文字列にスペースだけが含まれていないことが確認されます。

正規表現は、単語の前に任意の量のスペースを許可するように変更されます (所有量指定子によるバックトラッキングは許可されません)。*単語が文字列の先頭にある場合は、0 個以上の量指定子が使用されます。先読みアサーションにより、2 つの単語が衝突する可能性はありません(?= |\z)。

文字列を作成するとき (正規表現エンジンに入力する前) に、依然として線形スペースを占有します。最悪の場合のパフォーマンスも線形です。

極端なケース

  1. 元の言葉：

    aaaaaaaaaaaaaaaaaaa0 aaaaaaaaaaaaaaaaaaa1 ... aaaaaaaaaaaaaaaaaaa9 aaaaaaaaaaaaaaaaaaaa ... aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaaA ... aaaaaaaaaaaaaaaaaaaZ

    (各単語は 20 文字で、最後の文字は0-9、次にa-z、次に に変わりますA-Z)

    検索する文字列 (一致しない):

    aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay

    (y前にのみ来てくださいz)

  2. 元の言葉：

    patterns used in Perl pattern matching evolved from those supplied

    (ちょっと普通の言葉)

    検索する文字列 (一致しない):

    patterns used in Perl pattern matching evolved from those suppliedd

    (最後におまけd)

  3. 元の言葉：

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa

    (Word には のみが含まれa、長さが異なります。)

    検索する文字列 (一致しない):

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa

    (最後におまけa)

  4. 元の言葉：

    performance abc xyz performance 456 !@# performance

    (同じ言葉が何度も出てくる)

    検索する文字列 (一致しない):

    performance performance performance performance
于 2013-02-11T11:21:06.220 に答える