5

所以这对 RegEx 的使用有点不寻常；我想计算将由特定模式匹配的不同字符串的数量（或在合适的情况下指示无限）。

例如，让我们考虑[a-zA-Z]哪个会产生 52，[a-zA-Z]{1,2}哪个会产生 2652（52+52×52−52×2；对于类似 的字符串减去 52×2 aa，MM它们不是不同的）或者[a-zA-Z]+哪个会是 ∞。

当然，我希望这种机制能够处理比这更复杂的正则表达式。我对 PHP 和 Ruby 的解决方案特别感兴趣。这甚至可能吗？

4

2 回答 2

3

正则表达式用于通过将给定字符串与给定模式进行比较来匹配给定字符串。任何给定的正则表达式都可以匹配大量的字符串，正则表达式越长，它可以匹配的字符串就越多。

在我看来，你所追求的不能用正则表达式来完成。您可以编写一个程序来解构正则表达式并尝试猜测您可以匹配的字符串数量。然而，话虽如此，这样的程序的构建很可能不是微不足道的。

例如，在您的情况下， [a-zA-Z] 不仅会匹配a（z对于大写变体也是如此），而且它还会匹配包含这些字母的任何字符串，这基本上是您可以使用的任何字符串想象其中至少包含这些字母中的一个。

添加^和$锚点可能会减少点击量，但话又说回来，你仍然会有超过 48 个，因为有时，你也可以争辩说它{EmptyString}a{EmptyString}也可以匹配^a$，这使得可能的结果数量非常大。

于 2012-09-14T14:18:24.563 回答
2

为了完成这项任务，我认为您需要一个比正则表达式引擎本身更复杂的解决方案。正则表达式引擎只是“测试”（和“捕获”，但其复杂性是微不足道的），而在您的任务中，您希望测试潜在输入的整个话语（当然，完全不切实际），或者推断出数学上的潜在输入。但请注意，为了推断潜在输入的数量，您最终不可避免地不得不逐步完成与正则表达式引擎所做的或多或少相同的步骤，除了在每一步询问“这个原子的潜在输入？”

我不确定你想要这样一个计数器的目的是什么，但如果你想要做的只是比较两个正则表达式的潜在输入的大小，那么我建议使用抽样方法，即生成一个大集合随机字符串，并计算其中有多少与每个正则表达式匹配。（这太过分了，而且是高度推测性的，但由于纯随机字符串不太可能表现出自然语言所具有的分组模式，因此您可能必须使用分形技术（如曼德布洛特）生成样本。 )

现在，如果你想走演绎计数的道路，这里有两个想法可能有助于简化问题：

  1. 如果您找到一个*或+（未转义且不在字符类中），那么您知道答案是无穷大。也一样{M,}。编辑：好吧，除非量词在“不可能”的正则表达式中，例如(.*(?=a)(?=b))，已经断言下一个字符必须是“a”和“b”！

  2. 您可以将许多表达式扩展为交替语句，以便无论您的最终解决方案是什么，它都可以完全忽略字符类和量词，只关注每个交替组的原子数（可以相乘），例如

    1. 像这样的字符类[0-9a-f]可以扩展为0123456789abcdef，而后者又可以扩展为(?:0|1|2|...|d|e|f).

    2. 有限量词如x?( aka x{0,1} ), x{M,N}, andx{,N}可以扩展为(?:|x), (?:x|xx|xxx|...), 等等。

祝你好运！

于 2012-09-14T15:04:17.207 回答