Jak skutecznie dopasować ciąg wejściowy do kilku wyrażeń regularnych jednocześnie?

Question

W jaki sposób jeden skutecznie dopasować jeden ciąg wejściowy do dowolnej liczby wyrażeń regularnych?

Jeden scenariusz, w którym może być przydatny, dotyczy usług internetowych REST. Załóżmy, że mam wymyślić wiele wzorców adresów URL do publicznego interfejsu REST Web Service za:

• /user/with-id/{userId}
• /user/with-id/{userId}/profile
• /user/with-id/{userId}/preferences
• /users
• /users/who-signed-up-on/{date}
• /users/who-signed-up-between/{fromDate}/and/{toDate}
• ...

gdzie {…} noszą nazwy zastępcze (jak wyrażenie regularne grupy przechwytywania).

_{Uwaga: to pytanie nie jest o tym, czy powyższy interfejs reszta jest dobrze zaprojektowany, czy nie. (To chyba nie jest, ale to nie powinno mieć znaczenia w kontekście tego pytania.)}

to można przyjąć, że zastępcze zwykle nie pojawiają się na samym początku wzorca (ale mogli). Można również bezpiecznie założyć, że żaden ciąg nie może pasować do więcej niż jednego wzoru.

Teraz usługa internetowa otrzymuje żądanie. Oczywiście można sekwencyjnie dopasować żądany URI do jednego wzorca URL, a następnie do następnego, i tak dalej; ale to prawdopodobnie nie będzie dobrze skalowane w przypadku większej liczby wzorów, które należy sprawdzić.

Czy istnieją skuteczne algorytmy?

Wejścia:

• Ciąg wejściowy
• Zestaw "wzajemnie wykluczających" wyrażeń regularnych (to znaczy nie ciąg wejściowy może pasować do więcej niż jednego wyrażenia.)

Output :

• Wyrażenie regularne (jeśli występuje), do którego dopasowano ciąg wejściowy.

Answer 1

Aho-Corasick algorithm to bardzo szybki algorytm dopasowujący ciąg wejściowy do zestawu wzorców (w rzeczywistości słów kluczowych), które są wstępnie przetworzone i zorganizowane w trie, aby przyspieszyć dopasowanie.

Istnieją odmiany algorytmu do obsługi wzorów regex (np. http://code.google.com/p/esmre/ tylko po to, żeby wymienić), które prawdopodobnie warto obejrzeć.

Można również podzielić adresy URL w częściach, uporządkować je w drzewie, a następnie podzielić adres URL, aby dopasować i przejść drzewo po jednym kawałku na raz. Identyfikator {userId} może być traktowany jako symbol wieloznaczny lub dopasowany do określonego formatu (np. Być int).

Po dotarciu liść, wiesz, który adres URL dopasowane

Answer 2

Użyj nazwanych wyrażeń i operatora OR, tj. "(?P<re1>...)|(?P<re2>...)|...".

Answer 3

Jeśli w strukturze adresu URL istnieje hierarchia, należy ją wykorzystać w celu maksymalizacji wydajności. Tylko adres URL rozpoczynający się od/user/może pasować do dowolnego z pierwszych trzech i tak dalej.

Sugeruję przechowywanie hierarchii w celu dopasowania w drzewie odpowiadającym hierarchii adresów URL, gdzie każdy węzeł odpowiada poziomowi w hierarchii. Aby dopasować adres URL, przetestuj adres URL na wszystkich źródłach drzewa, w których znajdują się tylko węzły z wyrażeń regularnych dla "użytkownika" i "użytkowników". Pasujące adresy URL: s są testowane względem elementów podrzędnych tych węzłów, aż do znalezienia dopasowania w węźle liści. Udane dopasowanie może zostać zwrócone jako lista węzłów z katalogu głównego do liścia. Nazwane grupy z wartościami właściwości, takimi jak {user-id}, mogą zostać pobrane z węzłów zakończonych pomyślnie.

Answer 4

Po pierwsze, nie widziałem żadnej dobrej optymalizacji tego procesu.

Jednakże, jeśli masz naprawdę dużą liczbę wyrażeń regularnych, możesz je podzielić (nie jestem pewien, czy to jest technicznie partycjonowanie).

Co mówię wam zrobić to:

Załóżmy, że masz 20 możliwych adresów URL, które zaczynają się user:

/user/with-id/X 
/user/with-id/X/preferences # instead of preferences, you could have another 10 possibilities like /friends, /history, etc 

Następnie trzeba również 20 możliwe adresy zaczynające się od users:

/users/who-signed-up-on 
/users/who-signed-up-on-between  #others: /registered-for, /i-might-like, etc 

Lista jest dostępna dla użytkowników /products, /companies itd.

W tym przypadku można zastosować "wielopoziomowy" pasujący do.

Najpierw dopasuj początek napisu. Pasowałbyś do /products, /companies, /users, pojedynczo i ignorując resztę łańcucha. W ten sposób nie musisz sprawdzać wszystkich 100 możliwości.

Gdy wiesz, że adres URL zaczyna się od /users, możesz dopasować tylko te adresy URL, które zaczynają się od użytkowników.

W ten sposób zmniejszysz liczbę niepotrzebnych dopasowań. Nie dopasujesz ciągu znaków do wszystkich możliwości /procucts.

Answer 5

Standardowe rozwiązanie dla dopasowania wielu wyrażeń regularnych przeciwko strumieniu wejściowym jest lexer-generator takich jak Flex (istnieje wiele tych avalable, zazwyczaj kilka dla każdego programowanie langauge).

Te narzędzia pobierają zestaw wyrażeń regularnych związanych z "tokenami" (pomyśl o tokenach jako po prostu nazwach dla wszystkich dopasowanych wyrażeniach regularnych) i generują wydajne automaty stanu skończonego, aby dopasować wszystkie wyrażenia w tym samym czasie. Jest to czas liniowy z bardzo małą stałą wielkości strumienia wejściowego; Trudno prosić o "szybsze" niż to. Nakarmisz go strumieniem znaków i emituje token nazwy regex, która pasuje do "best" (to obsługuje przypadek, w którym dwa wyrażenia regularne mogą pasować do tego samego ciągu znaków, zobacz generator reguł dla określenia tego) i rozwija strumień przez to, co zostało uznane. Możesz więc zastosować go wielokrotnie, aby dopasować strumień wejściowy do serii tokenów.

Różne generatory lexerów pozwolą na przechwytywanie różnych bitów rozpoznanego strumienia na różne sposoby, dzięki czemu możesz, po rozpoznaniu tokena, wybrać część, na której Ci zależy (np. Dla literowego ciągu w cudzysłowach, tylko dbają o zawartość napisów, a nie o cytaty).