Mam wiele wzorów regex. Kiedy wprowadzany jest ciąg znaków, muszę znaleźć wszystkie wzorce pasujące do tego ciągu. To jest zwykle O (n) operacja:Baza danych lub struktura odpowiednia do dopasowywania ciągów do wyrażeń regularnych
SELECT regex FROM regexes WHERE 'string' RLIKE regex
Jaki jest najszybszy sposób to zrobić? Czy istnieją struktury bazy danych lub systemy pamięci masowej zoptymalizowane do wykonywania takiej operacji?
Krótka odpowiedź brzmi "Nie". Na żadnej platformie DBMS nie ma obecnie struktury indeksu, która będzie indeksować częściowe dopasowania takiego wyrażenia.
Długa odpowiedź jest taka, że wiodąca stała na dopasowaniu z symbolem wieloznacznym (np. 'foo_') może być używana jako prefiks dla dopasowań indeksu. Wiele platform DBMS zoptymalizuje to i użyje indeksu (jeśli jest dostępny), aby rozwiązać prefiks. Jednak nie jest to coś tak sprytnego jak pełne wyrażenie regularne, a indeksowanie może być używane tylko wtedy, gdy masz stały prefiks.
Jeszcze dłuższą odpowiedzią jest to, że istnieją algorytmy, takie jak RETE, które optymalizują częściowe dopasowania w ten sposób. Może to mieć zastosowanie, jeśli możesz wyrazić swoje dopasowania jako reguły dotyczące łączenia łańcuchowego, a nie wyrażenia regularne.
Rete działa przez obliczanie częściowych dopasowań i przedstawia tylko reguły, które można osiągnąć dzięki temu częściowemu dopasowaniu, więc jest bardziej efektywny niż O (n) (bardziej jak O (log n), ale nie jestem pewien dokładnego czas złożoności) dla dopasowania n reguł wobec faktu.
Jeden optymalizacji można wdrożyć, jeśli dotyczy przypadku, byłoby kategoryzować regexes i zorganizować je w hierarchii tak, że:
masz tylko do testowania garstkę najbardziej ogólnym regexes.
dla każdego ogólnego wyrażenia regularnego, które pasuje, a następnie przejdź do przetestowania ciągu w odniesieniu do wszystkich wyrażeń tylko tej samej kategorii.
Na przykład, jeśli struny wejściowe mogą być cokolwiek dowolnie skomplikowane i masz tysiące regexes, można zorganizować je w kategoriach takich jak:
kategorii \d+, które przetestować modele numeryczne (SSN, numery telefonów itp)
kategoria <.*?>, który będzie testować obecność znaczników HTML
kategoria \[email protected]\w+, które mogłyby testować obecność emaili adresów
itp
Jeżeli którykolwiek wzór korzeń nie pasuje, wtedy można uniknąć konieczności przetestować cały zakresy wzorców, które i tak nie uda .
Nie wiem, czy pasowałoby to do Twojej domeny, ale jest to możliwa optymalizacja.