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

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

Скажем, у вас есть список литеральных значений (в наших случаях это 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)$

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

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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

Я попробовал с 6Kb списком слов и создал regexp из 4Kb (который я поставил в JS файл), например: var re=new RegExp(/..../,"mib");

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

Ответ 8

Легкий способ сделать это - использовать Python hachoir_regex module:

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-адреса, а затем объединяет их с | на этапе уменьшения.