我有 N 个字符串。 此外，还有 K 个正则表达式，我不知道。每个字符串要么匹配一个正则表达式，要么就是垃圾。集合中共有 L 个垃圾字符串。 K 和 L 均未知。
我想推导正则表达式。显然，这个问题有无穷多个解。我需要找到一个“相当好的解决方案”，这
1) 最小化 K
2) 最小化 L
3) 最大化正则表达式的“细节”。我不知道这种质量的正确术语是什么。例如，字符串“ab123”可以描述为/ab\d+/或/\w+.+/，但第一个正则表达式更“具体”。
所有 3 个要求都需要作为一个复合标准，并具有一定的合理权重。
针对一种特殊情况的解决方案:如果 L = 0 且 K = 1(只有一个正则表达式，没有垃圾)，那么我们可以找到字符串的 LCS(最长公共(public)子序列)并从中得出相应的正则表达式那里。但是，当我们有“噪声”(L > 0) 时，这种方法就不起作用了。
非常感谢任何想法(或对现有工作的指示)。
最佳答案
您正在尝试做的是语言学习或语言推理，但不是通过一组给定示例概括(以及可能的反例)，您希望推断出一种具有小而特定语法的语言。
我不确定对此进行了多少研究。但是，如果您也有兴趣找到接受所有 n 字符串的最小(= 一般)正则表达式，请在 MDL 上搜索论文。 (最小描述长度)和 FSMs (有限状态机)。
两个有趣的查询 Google Scholar :
关于regex - 自动正则表达式生成器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/895425/