Генератор / редуктор регулярных выражений?

Question

Мне был задан интересный вопрос от коллеги по поводу операционной боли, которая у нас есть в настоящее время, и мне любопытно, есть ли что-нибудь (утилита / библиотека / алгоритм), которая может помочь автоматизировать это.

Скажите, что выиметь список литеральных значений (в наших случаях это URL).На основании этого списка мы хотим создать одно регулярное выражение, которое соответствует всем этим буквальным элементам.

Итак, если мой список:

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

Самый простойответ:

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

, но это становится большим для большого количества данных, и у нас есть ограничение длины, к которому мы стремимся остаться.

В настоящее время мы вручную пишем регулярные выражения, но это не 'Это очень хорошо масштабируется, и при этом никому не нужно тратить время.Существует ли более автоматизированный способ декомпозиции исходных данных для получения регулярного выражения с оптимальной длиной, которое соответствует всем исходным значениям?

Answer 1

Алгоритм сопоставления Aho-Corasick создает конечный автомат для сопоставления нескольких строк.Вы можете преобразовать автомат в его эквивалентное регулярное выражение, но проще использовать автомат напрямую (это то, что делает алгоритм).

Answer 2

Автоматический генератор для регулярного выражения доступен здесь .Инструмент имеет веб-интерфейс и использует Генетическое программирование для генерации регулярных выражений из нескольких примеров: вы можете выбирать между готовым синтаксисом для Java или JavaScript-обработчиков регулярных выражений.Он был разработан нашей исследовательской группой и представлен на конференции GECCO 2012 .

Answer 3

Сегодня я искал это. Я не нашел его, поэтому я создал инструмент: kemio.com.ar / tools / lst-trie-re.php

Вы помещаете список с правой стороны, отправляете его, а слева получаете регулярное выражение.

Я попытался использовать список слов размером 6 КБ и произвел регулярное выражение размером 4 КБ (которое я поместил в файл JS), например: var re=new RegExp(/..../,"mib");

Не злоупотребляйте этим, пожалуйста.

Answer 4

Утилита Emacs regexp-opt ( исходный код ) не делает то, что вам нужно (она работает только с фиксированными строками), но может быть полезной отправной точкой .

Answer 5

Если вы хотите сравнить все строки в наборе и только с ними, используйте trie или сжатый trie или, что еще лучше, направленное ациклическое слово график . Последний должен быть особенно эффективным для URL-адресов IMO.

Вы должны были бы отказаться от регулярных выражений, хотя.

Answer 6

Если взять реплики из двух других ответов, все, что вам нужно для сопоставления, это только предоставленные строки, вам, вероятно, лучше выполнить прямое сопоставление строк (медленно) или создать простой FSM, соответствующий этим строкам (быстро).

Регулярное выражение на самом деле создает FSM, а затем сопоставляет ваши входные данные с ним, поэтому, если входные данные взяты из набора ранее известных наборов, можно и часто проще сделать FSM самостоятельно, чем пытаться автоматически генерироватьрегулярное выражение.

Ахо-Корасик уже был предложен.Это быстро, но может быть сложно реализовать.Как насчет помещения всех строк в Trie и последующего запроса вместо этого (так как вы сопоставляете целые строки, а не ищете подстроки)?

Answer 7

Я думаю, что имеет смысл сделать шаг назад и подумать о том, что вы делаете и почему.

Чтобы соответствовать всем этим URL, только этим URL и никаким другим, вам не нужнорегулярное выражение;Вы, вероятно, сможете добиться приемлемой производительности, выполняя точные сравнения строк для каждого элемента в своем списке URL-адресов.

Если вам нужно регулярное выражение, то какие различия переменных вы пытаетесь учесть?Т.е. какая часть ввода должна соответствовать дословно и где есть место для маневра?

Если вы действительно хотите использовать регулярное выражение для сопоставления с фиксированным списком строк, возможно, из соображений производительности, тогда это должно быть простодостаточно написать метод, который склеит все ваши входные строки вместе в качестве альтернативы, как в вашем примере.Конечный автомат, выполняющий сопоставление регулярных выражений за кулисами, довольно умен и не будет работать медленнее, если у ваших альтернатив совпадений есть общие (и, следовательно, возможно, избыточные) подстроки.

Answer 8

Простой способ сделать это - использовать модуль Python hachoir_regex :

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)

создает упрощенное регулярное выражение

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

Код сначала создает простой тип регулярного выражения для каждого URL, а затем объединяет их с | на шаге сокращения.