Pertanyaan Case-insenstive memerintahkan pencarian kata melalui ekspresi reguler


Saya baru saja memulai dengan ekspresi reguler dalam perl. Setelah bermain-main melalui berbagai tutorial online, saya ingin menulis ekspresi reguler yang cocok dengan kecocokan kata kata yang tidak sensitif.

Saya mencoba untuk menentukan apakah string "A" terdiri dari sebuah kata atau rangkaian kata-kata string "B", dan saya ingin melakukan case-insensitive ini.

Misalnya, jika string "B" adalah "John Von Neumann", maka "JOhn", "Von NeumaNn", "VoN", "john neuMann" akan menjadi pertandingan, tetapi string seperti "Joh", "NeumaNn VoN", "Vonn" akan tidak jadilah pasangan.

Saya tidak yakin bagaimana melakukan ini dengan ekspresi reguler, ada ide?


5
2018-02-10 17:47


asal


Jawaban:


Mari kita abaikan saja sebentar.

John Von Neumann

bisa dicocokkan

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

Jadi pola regex yang Anda cari adalah

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

Inilah cara Anda membuat daftar:

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;

Dan akhirnya, kita bisa menghasilkan pola:

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

Anda akan menggunakannya seperti itu:

if ($input =~ /^$re\z/) {
   print "match\n";
} else {
   print "no match\n";
}

9
2018-02-10 18:25



Solusi ikegami akan mengambil ruang eksponensial untuk menyimpan string sebelum diubah menjadi regex (setiap kata akan muncul 2n - 1 kali, di mana n adalah jumlah kata, jadi total ruang setidaknya 2n - 1 * Jumlah (panjang kata)). Ini adalah tidak terkait dengan mesin regex - karena masalahnya adalah sebelum string diubah menjadi regex.


Sebuah persamaan konstruksi regex (dalam hal rangkaian string yang cocok) untuk solusi ikegami adalah:

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

Ini hanya membutuhkan ruang linear, dalam hal jumlah kata dan total panjang semua kata.

Untuk kejelasan:

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

Pernyataan depan (?=[^ ]) memiliki 2 tujuan: mencegah string kosong agar tidak dicocokkan, dan pastikan karakter pertama bukan karakter spasi.

Perhatikan ?+, yang membuat pengukur posesif (atau atomik), karena kita tidak perlu mundur ke sini. Mengapa? Jika kita melakukan ini secara normal, kita akan mengulang daftar kata-kata dan membandingkannya dengan kata paling kiri di dalam input. Setelah kami menemukan kecocokan, kami akan melanjutkan pengulangan untuk membandingkannya dengan kata berikutnya dalam masukan, sampai semua kata dalam masukan telah ditemukan atau kami telah selesai mengulang daftar kata.

Itu posesif quantifier juga mencegah backtracking hell terjadi. Jika sebuah kata dianggap cocok, itu tidak akan pernah dipertimbangkan lagi.

Untuk setiap kata, mereka dapat didahului oleh spasi, atau ini adalah awal dari string. Pernyataan depan (?= |\z) memiliki tujuan untuk memastikan kata-kata dengan awalan yang sama tidak dicocokkan secara salah pada percobaan pertama (mis. "John Von Vone", coba untuk mencocokkan "John Vone").

Karena tidak ada kemunduran, kinerja kasus terburuk adalah linear dalam hal panjang semua kata dan panjang string input (sama seperti bagaimana Anda melakukannya tanpa regex).


Kita dapat mengubah regex sedikit untuk memungkinkan jarak yang fleksibel:

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

Untuk kejelasan (ruang utama adalah signifikan):

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

Tampilan depan (?= *+[^ ])di awal memastikan string input tidak hanya berisi spasi.

Regex diubah untuk memungkinkan sejumlah spasi mendahului sebuah kata (backtracking dianulir oleh quantifier posesif). 0 atau lebih quantifier * digunakan, untuk kasus kata yang tepat di awal string. Tidak ada kesempatan untuk 2 kata bertabrakan, karena pernyataan yang terlihat (?= |\z).

Ini masih membutuhkan ruang linear saat membangun string (sebelum memasukkannya ke mesin regex). Kinerja kasus terburuk juga linear.


Kasus ekstrim

  1. Kata-kata asli:

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

    (Setiap kata adalah 20 karakter, karakter terakhir berubah dari 0-9, kemudian a-z, kemudian A-Z)

    String untuk mencari (tidak cocok):

    aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay
    

    (y hanya bisa datang sebelumnya z)

  2. Kata aslinya:

    patterns used in Perl pattern matching evolved from those supplied
    

    (Beberapa kata normal)

    String untuk mencari (tidak cocok):

    patterns used in Perl pattern matching evolved from those suppliedd
    

    (Tambahan d pada akhirnya)

  3. Kata aslinya:

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa
    

    (Word hanya berisi a, dengan panjang berbeda.)

    String untuk mencari (tidak cocok):

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa
    

    (Tambahan a pada akhirnya)

  4. Kata aslinya:

    performance abc xyz performance 456 !@# performance
    

    (Kata yang sama muncul beberapa kali)

    String untuk mencari (tidak cocok):

    performance performance performance performance
    

3
2018-02-11 11:21