如何检查正则表达式的相关性？

Question

假设我们有两个正则表达式：

1234.*

和

.*

输入：

1234567

显然它们都匹配，但 1234.* 匹配得更好，因为它更具体。 ie 更相关。 是否有标准方法来检查哪个更相关？

编辑：

一些澄清。 我想通过检查哪个正则表达式与输入最匹配来做出决定。 在这种情况下，我只匹配数字。

电话号码示例：

输入：

31882481337

我们对以下每个正则表达式都有一个规则：

31.*
.*

在这种情况下，我希望使用绑定到 31.* 的规则，因为这对于给定的输入来说更具体。 如果我没有使用正则表达式，那就很容易，因为我可以使用评分机制来检查它的匹配程度，但是这些规则可能有一些更高级的正则表达式，例如：

31[89].*

Answer 1

我认为没有简单的方法可以做到这一点。 如果您查看更复杂的示例，您很快就会意识到很难准确定义“更相关”。 所有诸如断言和反向引用之类的东西都会发挥作用。

我可以想出两种方法来粗略地估计“相关性”。

1. 随机修改输入并比较有多少修改导致每个表达式失败。

2. 分析表达式本身。 计算并比较终结符号与通配符的数量、断言的数量以及您喜欢的任何内容。

特别是在第二个解决方案中，您必须意识到实际匹配未使用的许多替代方案可能会使结果变得无关紧要。

h.*|verylongtext|anotherverylongtext

hell.*|v.*

当匹配“hello”时，第二个表达式“更相关”，但第一个表达式包含更多终端符号，并且第二个解决方案可能会获得更好的排名。 但对于匹配“verylongtext”，第一个是“更相关”。 这表明“相关性”在很大程度上取决于实际输入，您必须分析实际匹配路径 - 这是第一个解决方案隐式完成的事情。 但是随机修改输入是一项非常艰巨的任务，因为可能的输入空间非常大。 我认为这也不会起到很好的作用。

Answer 2

我能想到的一个因素是一种语言是否是无限的。 非无限肯定比无限更相关，因为语言中可接受的单词数量有限。

如果像你的例子一样测量无限的语言，两者都会永远持续下去，你可以继续计算语言中的每个单词，直到你脸色发青，你永远不会得出结论。

直到您认为第一个正则表达式的语言是第二个正则表达式的语言的真子集。 那么你可能会说其中一个更相关。

我不确定如何衡量正则表达式相关性的任何标准。

为了阐述真子集的概念，您可能会问您的语言是什么，您的正则表达式是否接受该语言之外的单词？ 你的表达可能仍然有效，但它的单词范围比你预期的要广泛……当然，如果你的输入受到控制，这可能并不重要，但这是你可以衡量相关性的一种方法。 它是否完全接受我的语言？

你的就是一个很好的例子，也许你想接受以 1234 开头的数字。1234.* 就像一个魅力......但这不是你指定的语言。 `1234\d* 更具体，并且与您指定的语言完全匹配......因此更相关。

但这完全是从纯粹的理论角度出发，可能不会帮助您以编程方式确定一个正则表达式是否比另一个更好。

Answer 3

自从我问这个问题以来已经很长时间了，但我想让你知道我最终想到了什么。 我采用了一种更简单的方法，我只是在正则表达式中添加了一个权重因子。 所以你可以说我自己定义了正则表达式的相关性，而不是尝试使用正则表达式来定义它：

Expression      Relevance
31.*              1
.*              0

Answer 4

我不知道“相关性”是否是真正的问题。 正如您所建议的，每个都是相关的，并且每个都将匹配“1234567”。 然而，正如您所说，一个（“1234.*”）更具体。 对于正则表达式，特异性非常好（在像这样的简单情况下），有时您可以磨练它直到您意识到您根本不需要一个（正则表达式）。 正则表达式的规则#1：如果不需要，就不要使用它们。 例如，要匹配“1234567”，我会选择：

$source = '1234567';
if ( stripos( $source, '1234' ) === 0 ) {
  $foo = substr( $source, 4 );
  // $source began with '1234' and $foo holds the rest
} else {
  // it didn't begin with '1234'
}

这是一个 PHP 示例，但其想法是，由于您已经如此严格地磨练了可接受的值，因此您甚至不再需要 PCRE。 “相关性”并不会真正告诉您有关正则表达式的更多信息（在这种情况下您如何定义“相关性”？），但是我认为特异性是一个更客观的衡量标准，并且能够使用非正则表达式字符串函数肯定会非常具体（事实上，它是布尔值 - 是否有正则表达式？）。

除了能够减少等式之外的正则表达式之外：要测量给定正则表达式的特异性，只需比较（如果需要，试探性地）有多少个不同的值可以满足该表达式。 在这个测试中得分最低的表达将被证明是最具体的。