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

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

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

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

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

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

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

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

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

Ответы на вопрос(3)

Ваш ответ на вопрос