如何确定一个正则表达式是否与另一个正则表达式正交? [英] How to determine if a regex is orthogonal to another regex?

问题描述

我想我的问题最好用一个(简化的)例子来解释.

I guess my question is best explained with an (simplified) example.

正则表达式 1:

^\d+_[a-z]+$

正则表达式 2:

^\d*$

Regex 1 将从不匹配 regex 2 匹配的字符串.因此，假设正则表达式 1 与正则表达式 2 正交.

Regex 1 will never match a string where regex 2 matches. So let's say that regex 1 is orthogonal to regex 2.

许多人问我正交是什么意思，我会尽力澄清:

As many people asked what I meant by orthogonal I'll try to clarify it:

让 S1 成为正则表达式 1 匹配的(无限)字符串集.S2 是正则表达式 2 匹配的字符串集.正则表达式 2 与正则表达式 1 正交 iff S1 和 S2 的交集为空.正则表达式 ^\d_a$ 将不正交，因为字符串 '2_a' 在集合 S1 和 S2 中.

Let S1 be the (infinite) set of strings where regex 1 matches. S2 is the set of strings where regex 2 matches. Regex 2 is orthogonal to regex 1 iff the intersection of S1 and S2 is empty. The regex ^\d_a$ would be not orthogonal as the string '2_a' is in the set S1 and S2.

如果两个正则表达式彼此正交，如何以编程方式确定?

How can it be programmatically determined, if two regexes are orthogonal to each other?

最好的情况是一些实现如下方法的库:

Best case would be some library that implements a method like:

/**
 * @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
 */
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);

推荐答案

我终于找到了我正在寻找的图书馆:

I finally found exactly the library that I was looking for:

dk.brics.automaton

用法:

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

应该注意的是，该实现不支持也不能支持复杂的 RegEx 功能，例如反向引用.请参阅博客文章 更快的 Java 正则表达式包"其中介绍了 dk.brics.automaton.

It should be noted that the implementation doesn't and can't support complex RegEx features like back references. See the blog post "A Faster Java Regex Package" which introduces dk.brics.automaton.

这篇关于如何确定一个正则表达式是否与另一个正则表达式正交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！