如何确定列表中哪些正则表达式可能重叠

Question

我有一个包含正则表达式的表，这些正则表达式位于一个MySQL表中，我根据这些正则表达式匹配文本。

有没有一种方法，使用MySQL或任何其他语言(最好是Perl)，我可以获得这个表达式列表，并确定它们中的哪些可以重叠。这应该独立于可能提供给表达式的任何文本。

所有的表达式都有锚点。

下面是我想要得到的一个例子：

表达式：

^a$
^b$
^ab
^b.*c
^batch
^catch

结果：'^b.*c' and '^batch' MAY overlap

有什么想法？

谢谢，斯科特

进一步解释：

我有一个用户创建的正则表达式列表和一个要与正则表达式匹配的导入字符串列表。在这种情况下，字符串是“干净的”数据(即它们不是用户创建的，而是从另一个源导入的-它们不能更改)。

当用户添加到正则表达式列表时，我不希望在现有的字符串列表或任何未来的字符串上发生任何冲突(这是不能提前猜到的-唯一的限制是它们是长度不超过255个字符的ASCII可打印字符)。

一种暴力方法是创建一个包含所有字符串排列的“彩虹”表，每次添加正则表达式时，对彩虹表运行所有的正则表达式。然而，我想要避免这种情况(我甚至不确定成本)，所以我想知道是否有一种算法可以至少显示列表中的哪些正则表达式可能发生冲突。

Answer 1

我将在全速赛艇上划船。即使限制到BRE和/或MySQL-8.0之前的版本也是具有挑战性的。这里有一些想法。

• 如果是末端锚定，并且没有+或*，则计算长度。固定长度可以用作鉴别器。此外，为了简单起见，它还可以用于调节“蛮力”，方法可能是先使用magnitude.
• Anything，然后使用+，或者将*转换为.*。(Re“可能冲突”规则。)
• 任何带有显式字符(包括后跟+的字符)的RE在某些情况下会成为鉴别器。例如，^a.*c$.
• For vs. ^a.*b$那些锚定在最后的，颠倒模式，并以这种方式测试它。(我不知道颠倒过来有多难。)
• 如果你可以说一个特定的字符必须在任何位置，那么就把它作为一个鉴别器：^a.b.*c$ --位置1中的a；位置3中的b；结尾位置c。也许这可以扩展到字符类：^\w可能匹配，但^\d和^a.*\d$不匹配。