10

我们可以计算正则表达式之间的某种距离吗？

这个想法是要测量两个正则表达式在哪方面是相似的。

4

6 回答 6

6

您可以为两个正则表达式构建确定性有限状态机并比较转换。然后可以使用两个转换的差异来测量这些正则表达式的距离。

于 2010-01-25T09:29:27.323 回答
5

您可以使用一些指标：

  1. 有效匹配的长度。一些正则表达式有固定的大小，一些有上限，一些有下限。比较它们的长度或可能的长度有多相似。

  2. 匹配的字符。任何正则表达式都会有一组匹配可以包含的字符（可能是所有字符）。比较包含的字符集。

  3. 使用一个大文档，看看每个正则表达式有多少匹配，其中有多少是相同的。

你在寻找严格的对等吗？

于 2010-01-25T09:25:11.503 回答
2

如果您有两个正则表达式并有一组示例输入，您可以尝试将每个输入与每个正则表达式进行匹配。对于每个输入：

  • 如果它们都匹配或都不匹配，则得分 0。
  • 如果一个匹配而另一个不匹配，则得分 1。

将此分数与所有输入相加，这将为您提供正则表达式之间的“距离”。这将使您了解两个正则表达式对于典型输入的不同频率。如果您的样本输入集很大，计算将非常缓慢。如果两个正则表达式都无法匹配几乎所有随机字符串并且您的预期输入完全是随机的，则它根本不起作用。例如，如果在随机输入上进行测试，正则表达式 'sgjlkwren' 和正则表达式 'ueuenwbkaalf' 可能都不会匹配任何东西，所以这个指标会说它们之间的距离为零。这可能是也可能不是您想要的（可能不是）。

您可能能够分析正则表达式的结构并使用有偏随机抽样来故意命中匹配频率高于完全随机输入的字符串。例如，如果两个正则表达式都要求字符串以 'foo' 开头，您可以确保您的测试输入也始终以 foo 开头，以避免浪费时间测试您知道两者都会失败的字符串。

总而言之：除非您有一个非常特殊的情况，即输入集受限和/或正则表达式语言受限，否则我会说这是不可能的。如果您确实对输入和正则表达式有一些限制，那么它可能是可能的。请说明这些限制是什么，也许我可以想出更好的办法。

于 2010-01-25T09:31:03.610 回答
2

我想您可以计算实际正则表达式字符串之间的Levenshtein 距离。这当然是衡量两个不同正则表达式字符串之间“距离”的一种方法。

当然，我认为这里可能根本不需要正则表达式，并且计算正则表达式将应用于的实际“值”字符串的 Levenshtein 距离可能会产生更好的结果。

于 2010-01-25T09:35:50.850 回答
2

SO： Generating strings from regexes的较早问题中隐藏了一个答案。您可以通过使用一个正则表达式生成字符串并检查其中有多少与另一个正则表达式匹配来计算（不对称）距离度量。

这可以通过去除共享的前缀/后缀来优化。例如a[0-9]*并a[0-7]*共享前缀，因此您可以计算与之间的a距离。[0-9]*[0-7]*

于 2010-01-25T12:07:51.083 回答
1

我认为首先您需要自己了解如何看待两个表达式之间的“差异”。基本上，定义一个距离度量。

在一般情况下，制作起来会完全不同。根据您需要做什么，您可能会认为在某个地方允许一个不同的角色是一个很大的不同。在另一种情况下，允许任意数量的后续但相同的字符可能不会产生太大差异。

我还想强调的是，通常当他们谈论距离函数时，他们会将它们应用于......，好吧，我们称它们为令牌。在我们的例子中，字符序列。您愿意做的是将这种方法应用到那些令牌上，而不是应用到规则上，大量的令牌将匹配。我不太确定这是否有意义。

尽管如此，我相信我们可以想到一些东西，但不是一般的，而是针对一个特定且非常有限的情况。你有什么例子可以给我们看吗？

于 2010-01-25T09:25:12.667 回答