Wyrażenie regularne Wildcard Matching

Question

Mam listę około 120 tysięcy angielskich słów (w zasadzie każde słowo w języku).

Potrzebuję wyrażeń regularnych, które umożliwiałyby przeszukiwanie tych słów za pomocą znaków wieloznacznych, a.k.a. * i ?.

Kilka przykładów:

• jeśli użytkownik wyszukuje m?st*, to pasuje na przykład master lub mister lub mistery.
• jeśli użytkownik wyszukuje *ind (Każde słowo kończące się ind), to pasuje wind lub bind lub blind lub grind.

Teraz większość użytkowników (szczególnie tych, którzy nie są zaznajomieni z wyrażeń regularnych) wie, że ? zastępuje dokładnie jeden znak, a * jest zamiennikiem 0, 1 lub więcej znaków. Absolutnie chcę na tej podstawie zbudować funkcję wyszukiwania.

Moje pytania brzmią: Jak przekonwertować typ użytkownika (na przykład m?st*) na wyrażenie regularne?

Przeszukałem internet (oczywiście włączając tę ​​stronę) i wszystko, co mogłem znaleźć, to tutoriale, które próbowały mnie nauczyć zbyt wiele lub pytania, które były nieco podobne, ale niewystarczające, aby dostarczyć odpowiedzi na mój własny problem.

Wszystko, co mogłem wymyślić, to to, że muszę wymienić ? na .. Tak więc m?st* staje się m.st*. Jednak nie mam pojęcia, co zastąpić * z.

Każda pomoc zostanie bardzo doceniona. Dziękuję Ci.

PS: Jestem całkowicie nowy w wyrażeniach regularnych. Wiem, jak potężni mogą być, ale wiem też, że mogą być bardzo trudne do nauczenia. Więc nigdy nie poświęcałem czasu na to ...

Answer 1

ile chcesz trochę śmieszne zachowania, polecam użyć \w zamiast .

. dopasowuje białe znaki i inne symbole non-słowo, które możesz nie chcieć to zrobić.

Więc chciałbym wymienić ? z \w i zastąpić * z \w*

Także jeśli chcesz * dopasować co najmniej jeden znak, zastąpić go \w+ zamiast. Oznaczałoby to, że ben* pasowałaby do bend i bending, ale nie do Ciebie, zależy to tylko od Twoich wymagań.

Answer 2

. to wyrażenie, które pasuje do dowolnej litery, jak już odkryłeś. Podczas twoich godzin poszukiwania niewątpliwie natknąłeś się także na *, który jest operatorem powtarzania, którego użycie po wyrażeniu odpowiada poprzedniemu wyrażeniu zero lub więcej razy z rzędu.

Tak więc, równoważne z twoim znaczeniem * jest umieszczenie tych dwóch razem: .*. Oznacza to "dowolny znak zero lub więcej razy".

Zobacz Regex Tutorial on repetition operators.

Answer 3

Zastąp * z .* (odpowiednikiem wyrażenia "0 lub więcej dowolnych znaków").

Answer 4

Wymień ? na . i * na .*.

Answer 5

1. Wymień wszystkie "?" znaków z '\ W'
2. Replace all '*' znaki z '\ w *'

Operator '*' powtarza poprzedni element '' (dowolny znak) 0 lub więcej razy.

Zakłada się, że żadne ze słów nie zawiera ".", "*" I "?".

To jest dobre referencje

http://www.regular-expressions.info/reference.html

Answer 6

function matchWild(wild,name) 
{ 
    if (wild == '*') return true; 

    wild = wild.replace(/\./g,'\\.'); 
    wild = wild.replace(/\?/g,'.'); 
    wild = wild.replace(/\\/g,'\\\\'); 
    wild = wild.replace(/\//g,'\\/'); 
    wild = wild.replace(/\*/g,'(.+?)'); 

    var re = new RegExp(wild,'i'); 
    return re.test(name); 
} 

Answer 7

Oto sposób, aby przekształcić wieloznaczny w regex:

1. Prepend wszystko special characters([{\^- = $! |]}). + z \ - więc są one dopasowane jako znaki i nie powodują niespodziewanego doświadczenia użytkownika. Możesz go również zamknąć w numerze \ Q (który rozpoczyna cytat) i \ E (co kończy się). Zobacz także akapit dotyczący bezpieczeństwa.
2. Zastąp symbol wieloznaczny symbolem \ S *
3. Zastąpić? wildcard z \ S?
4. Opcjonalnie: wzór wstępny z ^ - to wymusi dokładne dopasowanie z początkiem.

5. Opcjonalnie: dodaj $ do wzoru - to wymusi dokładne dopasowanie z końcem.

   \ S - oznacza znak spoza przestrzeni, co dzieje się zero lub więcej razy.

Rozważmy using reluctant (non-greedy) quantifiers jeśli masz postacie pasujące do po * lub +. Można to zrobić, dodając ? po * lub + w ten sposób: \ S *? i \ S * +?

Rozważmy bezpieczeństwa: użytkownik wyśle ​​Ci kod do uruchomienia (bo regex to rodzaj kodu zbyt, a ciąg użytkownika służy jako regex). Powinieneś unikać przesyłania prostokąta z wyrażeniem regularnym do innych części aplikacji i używać go tylko do filtrowania danych pobranych w inny sposób. Ponieważ jeśli robisz, użytkownik może wpływać na szybkość twojego kodu, dostarczając różne wyrażenia za pomocą łańcucha wieloznacznego - może to być użyte w atakach DoS.

Przykład pokazać prędkość wykonanie podobnych wzorów:

seq 1 50000000 > ~/1 
du -sh ~/1 
563M 
time grep -P '.*' ~/1 &>/dev/null 
6.65s 
time grep -P '.*.*.*.*.*.*.*.*' ~/1 &>/dev/null 
12.55s 
time grep -P '.*..*..*..*..*.*' ~/1 &>/dev/null 
31.14s 
time grep -P '\S*.\S*.\S*.\S*.\S*\S*' ~/1 &>/dev/null 
31.27s 

sugeruję przed użyciem * po prostu dlatego, że może dopasować wszystko, i zwykle rzeczy są oddzielone spacjami..

Answer 8

To co mam użyć:

String wildcardToRegex(String wildcardString) { 
    // The 12 is arbitrary, you may adjust it to fit your needs depending 
    // on how many special characters you expect in a single pattern. 
    StringBuilder sb = new StringBuilder(wildcardString.length() + 12); 
    sb.append('^'); 
    for (int i = 0; i < wildcardString.length(); ++i) { 
     char c = wildcardString.charAt(i); 
     if (c == '*') { 
      sb.append(".*"); 
     } else if (c == '?') { 
      sb.append('.'); 
     } else if ("\\.[]{}()+-^$|".indexOf(c) >= 0) { 
      sb.append('\\'); 
      sb.append(c); 
     } else { 
      sb.append(c); 
     } 
    } 
    sb.append('$'); 
    return sb.toString(); 
} 

specjalną listę znaków z https://stackoverflow.com/a/26228852/1808989.