regex - 生成匹配某个输入集的正则表达式是一个可解决的问题吗？

Question

我提供了一些包含已知分隔数量的文本块的输入集。

我想制作一个自动生成 1 个或多个正则表达式的程序，每个正则表达式都匹配输入集中的每个文本块。

我看到了一些相对简单的方法来实现蛮力搜索。但我不是编译器理论方面的专家。这就是为什么我很好奇：

1）这个问题可以解决吗？还是有一些原则上不可能做出这样的算法？

2）是否有可能实现该算法的多项式复杂度并避免暴力破解？

Answer 1

".*" is one-or-more regexp that will match every text block in the input set. ;-)

Answer 2

问题是，有大量的正则表达式（实际上是无限数量）将匹配给定的一组输入。它们的范围从匹配所有内容的非常“贪婪”的表达式

.*

对于将完全匹配输入集的非常非“贪婪”的表达式

InputA OR inputB OR inputC etc

在这两者之间，您可以通过多种方式改变表达式，使其变得越来越贪婪（例如，用匹配任何数字的表达式替换特定数字等）。

你必须告诉我们更多关于这个问题的信息，以便我们知道在可能的答案范围内哪里是正确的；）

Answer 3

好的，在评论中，您澄清说要匹配所有字符串，这些字符串要么等于输入集中的字符串之一，要么仅在给定的“变化”级别内与其中一个不同。由于您没有准确定义“变化”，我将使用Levenshtein distance。

给定一个字符串s和一个整数n，您可以构建正则表达式，它完全匹配与该字符串的 Levenshtein 距离为n或小于该字符串的所有字符串，如下所示：

首先，我们编写一个函数，它给出s并n返回一个简单的正则表达式列表，当它们一起匹配距离为n或小于的所有字符串时s。这里的“简单正则表达式”是指只包含文字字符和通配符的正则表达式。

对于n=0该函数，只需返回[s]. 否则，它会计算列表n-1，然后遍历其中的每个项目。对于每个项目r和每个位置iwhere 0 <= i < length(r)，它将以下正则表达式添加到列表中：

• .已添加到r位置的正则表达式i。
• 删除i第 th 个字符的正则表达式。r
• i的第 th 个字符r已被替换为的正则表达式.。

现在要计算给定字符串集和给定值的正则表达式n，我们计算每个字符串的列表，然后将or所有正则表达式组合成一个大正则表达式。

请注意，这将很快导致非常大的正则表达式。

Answer 4

http://txt2re.com/可能是你想要的。