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

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

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

Примеры

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

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

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

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

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