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

У меня есть N строк. Кроме того, есть K регулярных выражений, неизвестных мне. Каждая строка соответствует либо одному из регулярных выражений, либо мусору. В комплекте есть всего L мусорных струн. И K и L неизвестны.Автоматическое построение регулярных выражений

Я бы хотел вывести регулярные выражения. Очевидно, эта задача имеет бесконечное число решений. Мне нужно найти "достаточно хорошее решение", которое

1) сводит к минимуму K

2) сводит к минимуму L

3) максимально "специфику" регулярных выражений. Я не знаю, каков правильный термин для этого качества. Например, строка «ab123» может быть описана как/ab \ d +/или /\w+.+/, но первое регулярное выражение более «специфично».

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

Решение для одного конкретного случая: если L = 0 и K = 1 (только одно регулярное выражение и без мусора), то мы можем просто найти LCS (самую длинную общую подпоследовательность) для строк и создать соответствующее регулярное выражение оттуда. Однако, когда у нас есть «шум» (L> 0), этот подход не работает.

Любые идеи (или указатели на существующую работу) приветствуются.

источник

2009-05-21 Igor Krivokon

Что дается информация? Только N строк?Является ли регулярное выражение уже решенным, но просто скрыто от вас? Вы можете легко создать регулярное выражение, которое соответствует определенному набору строк, присоединив их к «|». –

:), который будет обманывать. Наверное, мне нужны еще один критерий, чтобы предотвратить такое решение ... Ограничьте регулярное выражение, я думаю. –

Ваше условие №3 лучше описать как минимизирующее количество совпадающих строк, не входящих в заданный набор из N строк. Учитывая, что у вас есть 3 вещи, чтобы свести к минимуму (хотя вы могли бы так же легко требовать L = 0), вам нужно весить, какие факторы важнее. – user57368

Ничего умного здесь, возможно, я не совсем понимаю проблему?

Почему бы не просто уменьшить L до 0? Проверьте каждую строку на каждое регулярное выражение; если строка не соответствует ни одному из регулярных выражений, это мусор. если он соответствует, запомните регулярные выражения/строки (строки), которые соответствовали и выполняли LCS на каждом L = 0, K = 1, чтобы вывести каждое определение регулярного выражения.

источник

2009-05-21 22:46:11 benson

У меня нет никаких регулярных выражений. Проблема их вывода. –

Ключевые слова в академии - это «грамматический вывод». К сожалению, нет никаких эффективных, общих алгоритмов, которые бы делали то, что вы предлагаете. Какова ваша настоящая проблема?

Редактировать: похоже, вас могут заинтересовать языки описания данных. PADS (http://www.padsproj.org/) является типичным примером.

источник

2009-05-21 22:55:20 Dave

> Какая у вас настоящая проблема? Как хобби-проект, я реализую «волшебный редактор» для больших файлов, в основном данные (плюс случайные комментарии или «неровности»). Довольно часто мне нужно изменить форматирование или удалить столбец значений или что-то вроде этого. Обычно я делаю такие вещи с помощью быстрого perl-вкладыша. Однако я хотел создать более «визуальное» решение для людей, не знакомых с регулярными выражениями. Они просто отредактируют одну строку, а другие (похожие) строки в файле автоматически изменятся. –

Будет проверять PADS, спасибо! –

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

Я не уверен, сколько исследований делается на этом. Однако, если вы также заинтересованы в поиске минимального (= общего) регулярного выражения, которое принимает все строки n, поиск документов на MDL (минимальная длина описания) и FSMs (конечные государственные машины).

Два интересных запросов на Google Scholar:

источник

2009-05-21 22:56:09 Stephan202

Спасибо! Будут проверять документы на MDL. –

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

ответ

Смежные вопросы