Построение компоновщика регулярных выражений

Ответ 1

Собственно, это начинает все больше напоминать приложение-компилятор. На самом деле, если я правильно помню, книга компилятора Aho Dragon использует пример regex для создания компилятора DFA. Это место для начала. Это может быть действительно классный проект компилятора.

Если это слишком много, вы можете подойти к нему как к оптимизации в течение нескольких проходов, чтобы уточнить его все дальше и дальше, но сначала это будет предопределенный algo:

Первый проход: хотите найти Cat, Catches cans Результат:/Cat | Уловы | Банки /

Второй проход: Ищите аналогичные стартовые условия: Результат:/Ca (t | tches | ans)/

Второй проход: найдите аналогичные условия окончания: Результат:/Ca (t | tch | an) s */

Третий проход: найдите дополнительные улучшения, такие как повторения и отрицательные условия.

Ответ 2

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

Регулярное выражение эквивалентно DFA (Детерминированные конечные автоматы). Стратегия в основном всегда одна и та же:

Посмотрите на Alergia (для теории) и алгоритм MDI (для реального использования), если генерировать детерминированный автомат достаточно.

Алгоритм Alergia и MDI описаны здесь: http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf

Если вы хотите создать более мелкие модели, вы можете использовать другой алгоритм. Статья, описывающая это, приведена здесь: http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz

Его домашняя страница здесь: http://www.grappa.univ-lille3.fr/~lemay

Если вы хотите использовать отрицательный пример, я предлагаю вам использовать простое правило (раскраску), которое предотвращает объединение двух состояний DFA.

Если вы спросите этих людей, я уверен, что они поделятся своим источником кода.

Я сделал такой же алгоритм во время моего Ph.D. для вероятностных автоматов. Это означает, что вы можете связать вероятность с каждой строкой, и я сделал программу на С++, которая "учит" взвешенные автоматы.

В основном этот алгоритм работает следующим образом:

из положительных примеров: {abb, aba, abbb}

создайте простейший DFA, который принимает именно все эти примеры:

-> x -- a --> (y) -- b --> (z)
          \
            b --> t -- b --> (v)

x не удалось найти y, прочитав букву "a", например. Состояния x, y, z, t и v. (Z) означает, что это конечное состояние.

затем "слить" состояния DFA: (здесь, например, результат после слияния состояний y и t.

               _
              /  \
             v    | a,b     ( <- this is a loop :-) )
x -- a -> (y,t) _/

новое состояние (y, t) является конечным состоянием, получающимся путем слияния y и t. И вы можете прочитать письмо a и b от него. Теперь DFA может принять: a (a | b) * и легко построить регулярное выражение из DFA.

Какие состояния для слияния - это выбор, который делает основное различие между алгоритмами.

Ответ 3

Программа пытается вывести регулярное выражение что соответствует примерам

Я не думаю, что это полезный вопрос. Вы должны знать семантически то, что вам нужно представить, чтобы что-то вывести. Когда вы пишете регулярное выражение, у вас есть цель: принимать URL-адреса, принимать электронные письма, извлекать токены из кода и т.д. Я бы пересмотрел вопрос так: учитывая базу знаний и семантику для регулярного выражения, вычислите наименьшее регулярное выражение. Это еще один шаг, потому что у вас есть естественный язык, который пытается объяснить общее выражение, и мы все знаем, как он становится двусмысленным! У вас должно быть семантическое объяснение. Без этого самое лучшее, что вы можете сделать для примеров, - вычислить регулярное выражение, которое охватывает всю строку из списка ok.

Алгоритм покрытия:

Список заполнять Ok
Заполнять Не нормально Список
Проверка повторений
Проверьте наличие противоречий (одна и та же строка не может быть в обоих списках)
Создание детерминированных конечных автоматов (DFA) из списка Ok, где строки из списка являются конечными состояниями
Упростите DFA, исключив повторяющиеся состояния. ([1] 4.4)
Преобразование DFA в регулярное выражение. ([1] 3.2.2)
Test Ok list и не одобрен список

[1] Введение в теорию автоматов, язык и вычисления. J. Hopcroft, R. Motwani, J.D. Ullman, 2nd Edition, Pearson Education.

P.S.

У меня был некоторый опыт работы с генетическим программированием, и я думаю, что это действительно накладные расходы для вашей проблемы. Поскольку целевая функция действительно светлая, ее лучше оценивать с помощью одного процессора, и это может занять много времени. Чтобы иметь более короткое выражение, вам просто нужно свести к минимуму DFA. Но GA может дать интересный результат.

Ответ 4

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

Генетическое программирование (GP) - это метод эволюционного машинного обучения, в котором кандидат на решение кандидата для данной проблемы рассматривается как абстрактное синтаксическое дерево.

Было опубликовано несколько исследований о том, как использовать GP, чтобы найти регулярное выражение, соответствующее данному набору примеров. Вы можете найти статьи и подробности здесь

Webapp, который делает это, размещен на regex.inginf.units.it. Исходный код приложения был опубликован на github

Ответ 5

Вы можете попытаться использовать базовый алгоритм вывода, который использовался в других приложениях. Я реализовал очень простой подход, основанный на построении конечного автомата. Однако он учитывает только положительные образцы. Исходный код находится на http://github.com/mvaled/inferdtd

Может быть интересен AutomataInferrer.py, который очень прост.

Ответ 6

RegexBuilder, похоже, имеет много функций, которые вы ищете для.