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