regex - онлайн - регулярные выражения примеры




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

Я читал идею проекта Java, описанную здесь :

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

Для меня это очень интересная идея. Кто-нибудь имеет представление о том, как это сделать? Моя первая идея была чем-то вроде генетического алгоритма, но мне хотелось бы получить от вас какие-то результаты.


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

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

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

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


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

PS

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


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

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


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

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

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

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


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

Регулярное выражение эквивалентно 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. для вероятностных автоматов. Это означает, что вы можете связать вероятность с каждой строкой, и я сделал программу на C ++, которая «учит» Weighted Automata.

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

из положительных примеров: {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.

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





design