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

Question

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

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

1) минимизирует K

2) минимизирует L

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

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

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

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

Answer 1

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

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

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

• автоматы "минимальной длины описания"
• автоматы "языкового вывода"

Answer 2

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

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

Answer 3

Ничего умного, может быть, я не до конца понимаю проблему?

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