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

Вероятно, нереально найти такой алгоритм для грамматик регулярных выражений с очень «сложным» синтаксисом (включая произвольные повторения, утверждения и т. Д.), Поэтому давайте начнем с упрощенного, который допускает толькоOR подстрок:

foo(a|b|cd)bar должен соответствоватьfooabar, foobbar а такжеfoocdbar.

Примеры

Учитывая набор строкh_q1_a, h_q1_b, h_q1_c, h_p2_a, h_p2_b, h_p2_cжелаемый результат алгоритма будетh_(q1|p2)_(a|b|c).

Учитывая набор строкh_q1_a, h_q1_b, h_p2_aжелаемый результат алгоритма будетh_(q1_(a|b)|p2_a). Обратите внимание, чтоh_(q1|p2)_(a|b) было бы небыть правильным, потому что расширить до 4 строк, в том числеh_p2_b, которого не было в исходном наборе строк.

Случай использования

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

((Упрощенное) регулярное выражение должно быть как можно более коротким, хотя меня больше интересует практическое решение, чем лучшее. Конечно, простой ответ - просто объединить все строки, такие как A | B | C | D | ..., которые однако, это не полезно.)