Wyodrębnianie ciągów statycznych z wyrażenia regularnego

Question

Próbuję skutecznie wyodrębnić ciągi statyczne (ciągi, które MUST należy dopasować dla danego wyrażenia regularnego do dopasowania). Udało mi się to zrobić w najprostszych przypadkach, ale próbuję odkryć bardziej niezawodne rozwiązanie.

---

Biorąc regex takich jak ten poniżej

"fox jump(ed|ing|s)" 

dałaby nam

"fox,jumped,jumping,jumps" 

---

Innym przykładem jest

"fox jump(ed|ing|s)?" 

co dałoby nam

"fox,jump" 

powodu opcjonalnego operatora

---

Algorytm mam jest zbyt prosta do teraz. Zacznie się od końca wyrażeń regularnych i usunie grupy lub pojedynczy znak, po którym następują te operatory "*?" jak również "eksplodować" zgrupowane operatory OR "(|)". To działa całkiem dobrze, ale nie bierze pod uwagę pełnej składni wyrażenia regularnego. Można to traktować jako rodzaj procesu generowania minimalnego zestawu dla regex (minimalnego zestawu łańcuchów, które regex może "wygenerować/musi pasować").

DLACZEGO? Próbuję dopasować kilka tekstu do dużego zestawu wyrażeń regularnych. Jeśli mogę uzyskać listę "słów kluczowych" dla tych wyrażeń regularnych, które są "wymagane", mogę wykonać szybkie wyszukiwanie tekstowe tego słowa kluczowego, aby filtrować wyrażenia, na których mi zależy (zignoruj ​​te, których nie gwarantuję, że nie pasuję lub nawet pomiń ten tekst całkowicie skutecznie nie uruchamiać żadnych wyrażeń regularnych w tekście, ponieważ jesteśmy zgodni, że nie mamy dopasowania w naszym zestawie wyrażeń regularnych). Mogę zorganizować ten zestaw słów kluczowych w wydajną strukturę danych (Binary Search/Trie/Aho-Corasick), aby filtrować zestaw wyrażeń regularnych, zanim jeszcze spróbuję uruchomić tekst przez Finite Automata. Istnieją niezwykle szybkie algorytmy dopasowywania ciągów znaków, które mogę uruchomić jako etap filtrowania, zanim spróbuję uruchomić wyrażenie regularne. Byłem w stanie zwiększyć przepustowość wielu fałd wykonujących ten prosty proces.

Answer 1

Zobacz bibliotekę Xeger, która podając wyrażenie regularne da ci wszystkie możliwe ciągi pasujące do siebie.

Wygląda na to, że chcesz zachować wspólny przedrostek tych ciągów (część, w której powiedziałeś, aby ignorować opcjonalne operatory), ale jeśli to zrobisz, możesz przechwycić żądła, które mają ten wspólny przedrostek, ale nie mają żądanego zakończenia (na przykład "jumpy" w twoim przykładzie). Jeśli nie stanowi to problemu, po prostu znajdź najkrótszy ciąg znaków podany przez Xeger, zakładając, że operatory opcjonalne występują tylko na końcu wyrażenia regularnego.

Answer 2

Jeśli dobrze rozumiem twój problem, szukasz zestawu słów, które będą wszystkie te słowa (rozłączne) podciągami dowolnego słowa zaakceptowanego przez (dane) wyrażenie regularne.

Domyślam się, że taki zestaw będzie często pusty, ale mimo to można go znaleźć.

Aby znaleźć taki zestaw, proponuję następujący algorytm:

1. Znajdź FA odpowiadające swoim regex wejściowego.
2. Zidentyfikować mosty (https://en.wikipedia.org/wiki/Bridge_(graph_theory)) pomiędzy stanem początkowym S a stanem przyjmowania F. Można to zrobić na przykład przez usunięcie krawędzi E i pytanie, czy ścieżka istnieje od S do E w FA z E usuniętym - powtórz to dla wszystkich krawędzi.
3. Wszystkie krawędzie będące mostami muszą zostać trafione podczas biegu akceptacji, a każda krawędź odpowiada literie wejściowej.
4. Możesz teraz generować wymagane słowa, łącząc kolejne mostki od końca do końca.

Myślę, że z konstrukcji algorytmu wynika, że ​​FA (a nie DFA) wystarcza, aby to zadziałało. Ponownie, dowód byłby miły, ale myślę, że powinien zadziałać :)