Encontrar a expressão regular mais simples que corresponde a todas as strings dadas
Existe um algoritmo que pode produzir uma expressão regular (talvez limitada a uma gramática simplificada) a partir de um conjunto de strings de modo que a avaliação de todas as strings possíveis que correspondam à expressão regular reproduza o conjunto inicial de strings?
É provavelmente irrealista encontrar tal algoritmo para gramáticas de expressões regulares com uma sintaxe muito "complicada" (incluindo repetições arbitrárias, afirmações, etc.), então vamos começar com uma simplificada que permita apenas umaOR de substrings:
foo(a|b|cd)bar deve corresponderfooabar, foobbar efoocdbar.
Dado o conjunto de cordash_q1_a, h_q1_b, h_q1_c, h_p2_a, h_p2_b, h_p2_c, a saída desejada do algoritmo seriah_(q1|p2)_(a|b|c).
Dado o conjunto de cordash_q1_a, h_q1_b, h_p2_a, a saída desejada do algoritmo seriah_(q1_(a|b)|p2_a). Observe queh_(q1|p2)_(a|b) seria nãoestar correto porque isso se expande para 4 cordas, incluindoh_p2_b, que não estava no conjunto original de strings.
Eu tenho uma longa lista de rótulos que foram todos produzidos pela montagem de substrings. Em vez de imprimir a vasta lista de strings, eu gostaria de ter uma saída compacta indicando quais rótulos estão na lista. Como a lista completa foi produzida programaticamente (usando um conjunto finito de pre e sufixos), espero que a notação compacta seja (potencialmente) muito menor do que a lista inicial.
(O regex (simplificado) deve ser o mais curto possível, embora eu esteja mais interessado em uma solução prática do que a melhor. A resposta trivial é, obviamente, apenas concatenar todas as strings como A | B | C | D | ... que não é, no entanto, útil.)