Case-insenstive uporządkowane wyszukiwanie słów za pomocą wyrażenia regularnego

Question

Zacząłem od zwykłego wyrażenia w perlu. Po obejrzeniu różnych samouczków online chciałem napisać wyrażenie regularne, które pasuje do rozróżnianego według wielkości liter nierozróżnialnego dopasowania słów.

Próbuję ustalić, czy ciąg "A" składa się ze słowa lub sekwencji słów ciągu "B", i chcę to zrobić bez rozróżniania wielkości liter.

Na przykład, jeśli ciąg znaków "B" jest "John Von Neumann", a następnie "Jan", "von Neumanna", "von", "Jan Neumann" będzie mecz, ale struny jak "Joh" , "NeumaNn VoN", "Vonn" będzie nie być dopasowanie.

Nie jestem pewien, jak to zrobić za pomocą wyrażeń regularnych, jakiegokolwiek pomysłu?

Answer 1

Zignorujmy sprawę na sekundę.

John Von Neumann 

może być dopasowana przez

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 

Więc regex wzór dla którego szukasz jest

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

Oto w jaki sposób można zbudować listę:

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; 

I na koniec możemy wygenerować wzór:

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

Można by użyć go jak takie: rozwiązanie

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

Answer 2

Ikegami odbędzie się wykładniczy przestrzeń do przechowywania ciąg zanim zostanie on przekształcony regex (pojawi się każde słowo 2 ^{n - 1} razy, gdzie n jest liczbą słów, więc całkowita powierzchnia wynosi co najmniej 2 ^{n - 1} * Suma (długość słów)). Jest to nie związane z silnikiem regex - ponieważ problem występuje przed przekształceniem ciągu w wyrażenie regularne.

---

równoważną budowa regex (w perspektywie zestawu strun że pasuje) do roztworu Ikegami byłoby:

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

To zajmuje tylko przestrzeń liniową, w okresie obowiązywania liczby słów i całkowita długość wszystkich słów.

Dla jasności:

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

Spojrzenie wyprzedzeniem twierdzenie (?=[^ ]) ma 2 cele: zapobieganie pusty łańcuch przed dopasowane i upewnij się, że pierwszy znak nie jest spacja.

Zanotuj ?+, co sprawia, że ​​kwantyfikator zaborczy (lub atomowy), ponieważ nie musimy backtracking tutaj. Dlaczego? Jeśli mielibyśmy to zrobić normalnie, przejdziemy przez listę słów i porównamy je z lewym słowem na wejściu. Po znalezieniu dopasowania, kontynuujemy pętlę, aby porównać ją z następnym słowem na wejściu, dopóki wszystkie słowa w danych wejściowych nie zostaną znalezione lub skończyliśmy zapętlać listę słów.

Kwantyfikator dzierżawy o wartościrównież zapobiega powstawaniu piekła wstecznego. Jeśli słowo zostanie uznane za dopasowanie, nigdy nie zostanie ponownie rozpatrzone.

Dla każdego słowa można je poprzedzić spacją lub jest początkiem ciągu. Twierdzenie wyprzedzające o numerze (?= |\z) ma na celu upewnienie się, że słowa z tym samym prefiksem nie zostaną niepoprawnie dopasowane przy pierwszym podejściu (np. "John Von Vone", spróbuj dopasować "John Vone").

Ponieważ nie ma wstecznego śledzenia, najgorszy przypadek jest liniowy pod względem długości wszystkich słów i długości wprowadzanego ciągu znaków (tak samo, jak można to zrobić bez wyrażeń regularnych).

---

Możemy zmienić regex trochę, aby umożliwić elastyczne rozstaw

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

Dla jasności (prowadzące przestrzeń jest istotne):

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

Spojrzenie wyprzedzeniem (?= *+[^ ]) u Początek sprawia, że ​​ciąg wejściowy nie zawiera tylko spacji.

Wyrażenie regularne zostaje zmienione, aby dozwolona była jakakolwiek ilość spacji przed słowem (wycofanie zabronione przez kwantyfikator dzierżawczy). Zastosowano 0 lub więcej kwantyfikatorów *, dla przypadku, gdy słowo znajduje się na samym początku łańcucha. Nie ma szans, aby zderzyły się 2 słowa, ze względu na stwierdzenie wyprzedzające (?= |\z).

Ciągle zajmuje liniową przestrzeń podczas konstruowania napisu (przed wprowadzeniem go do silnika regex). Najgorsza wydajność jest również liniowa.

---

skrajnych przypadkach

1. Oryginalne słów:

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

   (Każde słowo jest 20 znaków, ostatnich zmian postać z 0-9, potem a-z, następnie A-Z)

   Struny do wyszukiwania (nie pasujące):

   aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay 
   

   (y może przyjść tylko przed z)

2. Oryginalny słowo:

   patterns used in Perl pattern matching evolved from those supplied 
   

   (Niektóre normalne słowa)

   Ciągi do wyszukiwania (nie pasujące):

   patterns used in Perl pattern matching evolved from those suppliedd 
   

   (Extra d na końcu)

3. Oryginalny słowo:

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa 
   

   (. Słowo zawiera tylko a, o różnej długości)

   Struny do poszukiwania (nie pasujące):

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa 
   

   (Dodatkowe a na końcu)

4. Oryginalny słowo:

   performance abc xyz performance 456 !@# performance 
   

   (samo słowo pojawia się wielokrotnie)

   Struny do wyszukiwania (nie pasujące):

   performance performance performance performance