Я работаю над анализом большого публичного набора данных с множеством многозначимых человекочитаемых строк, которые были четко сформированы некоторой регулярной (в формальном смысле слова) грамматикой.
Не слишком сложно смотреть на наборы этих строк один за другим, чтобы увидеть шаблоны; к сожалению, около 24 000 из этих уникальных строк разбиты на 33 категории и 1714 подкатегорий, поэтому несколько больно делать это вручную.
В принципе, я ищу существующий алгоритм (желательно с существующей ссылочной реализацией), чтобы взять произвольный список строк и try, чтобы вывести минимальное (для некоторого разумного определения минимальное) spanning набор регулярных выражений, которые могут быть использованы для их создания (т.е. вывести регулярную грамматику из конечного набора строк из языка, порожденного этой грамматикой).
Я рассмотрел повторение жадного алгоритма с длинной общей подстрокой, но это происходит только потому, что оно не скроет ничего, кроме точных совпадений, поэтому не будет обнаруживать, скажем, общую картину различных числовых строк в конкретном положение в грамматике.
Возможно принудительное принудительное форматирование всего, что не выпадает из общего устранения подстроки, но, вероятно, невозможно вычислить. (Кроме того, я подумал об этом, и может возникнуть проблема "упорядочения фаз" и/или "локального минимума" с устранением подстроки, поскольку вы можете сделать жадное подстрочное соответствие, которое в конечном итоге заставляет последнюю грамматику быть менее сжатой/минимальный, хотя он, по-видимому, является лучшим сокращением изначально).
