Zwykły generator/reduktor ekspresji?

Question

Zostałem postawiony przez kolegę interesujące pytanie o operacyjny punkt bólu, który mamy obecnie i jestem ciekawy, czy jest tam coś (narzędzie/biblioteka/algorytm), które może pomóc w automatyzacji tego.

Powiedz, że masz listę wartości literalnych (w naszych przypadkach są to adresy URL). Chcemy, na podstawie tej listy, wymyślić pojedyncze wyrażenie regularne pasujące do wszystkich tych literalnych elementów.

Tak więc, jeśli moja lista:

http://www.example.com 
http://www.example.com/subdir 
http://foo.example.com 

Najprostszą odpowiedzią jest

^(http://www.example.com|http://www.example.com/subdir|http://foo.example.com)$ 

ale ten dostaje duży dla dużej ilości danych, a mamy limit długości Próbujemy zatrzymać pod.

Obecnie ręcznie zapisujemy wyrażenia regularne, ale nie skalują się zbyt dobrze ani nie są doskonałym wykorzystaniem czasu. Czy istnieje bardziej zautomatyzowany sposób dekomponowania danych źródłowych w celu uzyskania optymalnego pod względem długości wyrażenia dopasowującego wszystkie wartości źródłowe?

Answer 1

Algorytm dopasowujący Aho-Corasick konstruuje skończony automat do dopasowania wielu ciągów. Możesz przekonwertować automat na równoważny regex, ale prostsze jest korzystanie z niego bezpośrednio (to właśnie robi algorytm).

Answer 2

Myślę, że byłoby rozsądnie cofnąć się o krok i pomyśleć o tym, co robisz i dlaczego.

Aby dopasować wszystkie te adresy URL, tylko te adresy URL i żadne inne, nie potrzebujesz wyrażeń regularnych; Prawdopodobnie można uzyskać akceptowalną wydajność, wykonując dokładne porównania ciągów znaków dla każdego elementu na liście adresów URL.

Jeśli potrzebujesz wyrażeń regularnych, to jakie są różnice, które chcesz spełnić? To znaczy. która część danych wejściowych musi dokładnie odpowiadać, a gdzie jest pokój?

Jeśli naprawdę chcesz użyć wyrażenia regularnego, aby dopasować ustaloną listę ciągów, być może ze względu na wydajność, to powinno być wystarczająco proste, aby napisać metodę, która skleja wszystkie twoje ciągi wejściowe razem jako alternatywne, jak w twoim przykładzie . Maszyna stanowa wykonująca dopasowanie regexp za kulisami jest dość sprytna i nie będzie działała wolniej, jeśli alternatywne opcje dopasowania mają wspólne (i w związku z tym prawdopodobnie nadmiarowe) podciągi.

Answer 3

Biorąc wskazówkę z pozostałych dwóch odpowiedzi, wszystko, co musisz dopasować, to tylko ciągi dostarczony, prawdopodobnie lepiej zrobić proste dopasowanie ciąg (wolno) lub skonstruować prosty FSM, który pasuje do tych ciągów (szybko).

Regex w rzeczywistości tworzy FSM, a następnie dopasowuje swoje wejście do niego, więc jeśli dane wejściowe pochodzą z zestawu wcześniej znanego zestawu, możliwe jest i często łatwiejsze wykonanie FSM zamiast próbować automatycznego generowania regex.

Aho-Corasick został już zasugerowany. Jest szybki, ale może być trudny do wdrożenia. Co powiesz na umieszczenie wszystkich łańcuchów w Trie, a następnie na zapytanie na ten temat (ponieważ dopasowujesz całe ciągi, nie szukając podłańcuchów)?

Answer 4

Jeśli chcesz porównać ze wszystkimi ciągami w zestawie i tylko przeciwko nim, użyj trie lub compressed trie lub jeszcze lepiej directed acyclic word graph. Te ostatnie powinny być szczególnie skuteczne w przypadku IMO adresów URL.

Należy jednak zrezygnować z wyrażeń regularnych.

Answer 5

Funkcja narzędzia Emacs regexp-opt (source code) nie wykonuje dokładnie tego, czego potrzebujesz (działa tylko na stałych ciągach znaków), ale może być przydatnym punktem początkowym.

Answer 6

Dzisiaj tego szukałem. Nie znalazłem go, więc tworzę narzędzie: kemio.com.ar/tools/lst-trie-re.php

Położysz listę po prawej stronie, przesłać ją i uzyskać wyrażenie regularne po lewej stronie.

Próbowałem z listy 6kB słów, a produkowane regexp z 4KB (który kładę na pliku JS) jak: var re=new RegExp(/..../,"mib");

nie nadużywaj go, proszę.

Answer 7

Dostępny jest automatyczny generator wyrażeń regularnych here. Narzędzie ma interfejs sieciowy i używa Genetic Programming do generowania wyrażeń regularnych z zestawu kilku przykładów: możesz wybrać między składnią gotową dla silników regex Java lub JavaScript. Został opracowany przez naszą grupę badawczą i został zaprezentowany na konferencji GECCO 2012.

Answer 8

Łatwym sposobem, aby to zrobić jest użycie Pythona hachoir_regex moduł:

urls = ['http://www.example.com','http://www.example.com/subdir','http://foo.example.com'] 
as_regex = [hachoir_regex.parse(url) for url in urls] 
reduce(lambda x, y: x | y, as_regex) 

tworzy uproszczonego wyrażenia regularnego

http://(www.example.com(|/subdir)|foo.example.com) 

Pierwszy kod tworzy prosty typ regex dla każdego adresu URL, a następnie skleja te z | w kroku redukcji.