Construtor automático de regex
Tenho N strings. Além disso, existem K expressões regulares, desconhecidas para mim. Cada sequência corresponde a uma das expressões regulares ou é lixo. Há um total de L seqüências de lixo no conjunto. K e L são desconhecidos.
Eu gostaria de deduzir as expressões regulares. Obviamente, esse problema tem um número infinito de soluções. Preciso encontrar uma "solução razoavelmente boa", que
1) minimiza K
2) minimiza L
3) maximiza "detalhes" das expressões regulares. Não sei qual é o termo certo para essa qualidade. Por exemplo, a cadeia "ab123" pode ser descrita como / ab \ d + / ou /\w+.+/, mas o primeiro regex é mais "específico".
odos os três requisitos precisam ser tomados como um critério composto, com certos pesos razoávei
Uma solução para um caso em particular: se L = 0 e K = 1 (apenas um regex e sem lixo), podemos encontrar o LCS (subsequência comum mais longa) para as strings e criar um regex correspondente a partir daí. No entanto, quando temos "ruído" (L> 0), essa abordagem não funciona.
odas as idéias (ou sugestões para o trabalho existente) são muito apreciada