如何确定一个正则表达式是否与另一个正则表达式正交？

发布于 2024-07-12 08:08:12 字数 746 浏览 11 评论 0原文

我想我的问题最好用一个（简化的）例子来解释。

正则表达式 1：

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

正则表达式 2：

^\d*$

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

正如许多人问我所说的正交是什么意思，我将尝试澄清它：

让 S1 em> 是正则表达式 1 匹配的（无限）字符串集。 S2 是正则表达式 2 匹配的字符串集。正则表达式 2 与正则表达式 1 正交当 S1 和 S2 的交集为空。正则表达式 ^\d_a$ 将不正交，因为字符串“2_a”位于集合 S1 和 S2 中。

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

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

/**
 * @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 guess my question is best explained with an (simplified) example.

Regex 1:

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

Regex 2:

^\d*$

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:

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);

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

我很OK 2024-07-19 08:08:12

我所说的“正交”是指“交集是空集”吗？

我会构造交集的正则表达式，然后转换为正常形式的正则语法，看看它是否是空语言......

话又说回来，我是一个理论家......

回复收藏 0 原文

弥枳 2024-07-19 08:08:12

我会构造交集的正则表达式，然后转换为正常形式的正则语法，看看它是否是空语言...

这就像用大炮射麻雀一样。为什么不直接构建产品自动机并检查是否可以从初始状态到达接受状态？这也将立即在交集中为您提供一个字符串，而无需先构建正则表达式。

当我得知存在多项式时间解决方案时，我会感到有点惊讶，而当我得知它相当于停止问题时，我一点也不感到惊讶。

我只知道一种方法，涉及从正则表达式创建 DFA，这是指数时间（在退化情况下）。它可以简化为停机问题，因为一切都是如此，但停机问题不能可以简化为它。

如果是最后一个，那么您可以利用任何 RE 都可以转换为有限状态机的事实。如果两个有限状态机具有相同的节点集，并且连接这些节点的弧相同，则它们是相等的。
因此，考虑到您使用的正交定义，如果您将 RE 转换为 FSM，并且这些 FSM 不相等，则 RE 是正交的。

这是不正确的。您可以拥有两个在边缘标记多图意义上非同构的 DFA (FSM)，但接受相同的语言。另外，如果不是这种情况，您的测试将检查两个正则表达式是否接受不相同的语言，而 OP 需要非重叠的语言（空交集）。

另外，请注意 \1、\2、...、\9 结构不是规则的：它不能用串联、并集和 *（Kleene 星号）来表示。如果你想包括回替换，我不知道答案是什么。同样有趣的是，上下文无关语言的相应问题是不可判定的：不存在采用两个上下文无关文法 G1 和 G2 并返回 true iff L(G1) ∩ L(g2) ≠ Ø 的算法。

回复收藏 0 原文

一直在等你来 2024-07-19 08:08:12

这个问题发布已经两年了，但我很高兴地说，现在只需在此处调用“genex”程序即可确定：https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex '^\d+_[a-z]+
空输出意味着没有与两个正则表达式匹配的字符串。   如果它们有任何重叠，它将输出整个重叠列表：
$ runghc Main.hs '\d' '[123abc]' 
1.00000000      "2"
1.00000000      "3"
1.00000000      "1"

希望这有帮助！
 '^\d*
空输出意味着没有与两个正则表达式匹配的字符串。   如果它们有任何重叠，它将输出整个重叠列表：

希望这有帮助！

$

空输出意味着没有与两个正则表达式匹配的字符串。如果它们有任何重叠，它将输出整个重叠列表：

希望这有帮助！

It's been two years since this question was posted, but I'm happy to say this can be determined now simply by calling the "genex" program here: https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex '^\d+_[a-z]+
The empty output means there is no strings that matches both regex.  If they have any overlap, it will output the entire list of overlaps:
$ runghc Main.hs '\d' '[123abc]' 
1.00000000      "2"
1.00000000      "3"
1.00000000      "1"

Hope this helps!
 '^\d*
The empty output means there is no strings that matches both regex.  If they have any overlap, it will output the entire list of overlaps:

Hope this helps!

$

The empty output means there is no strings that matches both regex. If they have any overlap, it will output the entire list of overlaps:

Hope this helps!

回复收藏 0 原文

染火枫林 2024-07-19 08:08:12

fsmtools 可以在有限状态机上执行各种操作，这是您唯一的问题是将正则表达式的字符串表示形式转换为 fsmtools 可以使用的格式。这对于简单的情况来说绝对是可能的，但在存在高级功能（例如look{ahead,behind}）的情况下会很棘手。

您也可以看看 OpenFst，尽管我从未使用过它。不过它支持交叉。

回复收藏 0 原文

疯狂的代价 2024-07-19 08:08:12

关于 \1、\2 位的要点...这是上下文无关的，因此无法解决。小一点：并不是所有的事情都可以简化为“停止”...例如程序等价.. – Brian Postow

[我正在回复评论]

IIRC，a^nb^ma^nb^m 不是上下文无关，因此 (a\*)(b\*)\1\2 也不是，因为它是相同的。 ISTR <代码>{ ww | w ∈ L } 即使 L 是“nice”，也不是“nice”，因为nice 是常规、上下文无关之一。

我修改我的声明：RE 中的所有内容都可以简化为停止问题;-)

回复收藏 0 原文

北斗星光 2024-07-19 08:08:12

我终于找到了我正在寻找的库：

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();
}

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

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

dk.brics.automaton

Usage:

/**
 * @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();
}

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.

回复收藏 0 原文

黎夕旧梦 2024-07-19 08:08:12

您也许可以使用类似 Regexp::Genex< /a> 生成测试字符串来匹配指定的正则表达式，然后使用第二个正则表达式上的测试字符串来确定这两个正则表达式是否正交。

回复收藏 0 原文

姐不稀罕 2024-07-19 08:08:12

在某些情况下，证明一个正则表达式与另一个正则表达式正交可能很简单，例如同一位置中互斥的字符组。对于除最简单的正则表达式之外的任何正则表达式来说，这都是一个不平凡的问题。对于带有分组和反向引用的严肃表达式，我什至会说这可能是不可能的。

回复收藏 0 原文

╰◇生如夏花灿烂 2024-07-19 08:08:12

我相信 kdgregory 是正确，您使用正交来表示补充。

这是正确的吗？

回复收藏 0 原文

情丝乱 2024-07-19 08:08:12

首先我要说的是，我不知道如何构建这样的算法，也不知道有任何库可以实现它。然而，如果得知任意复杂度的一般正则表达式不存在这样的情况，我一点也不感到惊讶。

每个正则表达式都定义了可以由该表达式生成的所有字符串的正则语言，或者如果您愿意，也可以定义与该正则表达式“匹配”的所有字符串的正则语言。将语言视为一组字符串。在大多数情况下，该集合将无限大。您的问题询问正则表达式给出的两个集合的交集是否为空。

至少对于第一个近似，我无法想象在不计算集合的情况下回答这个问题的方法，对于无限集合来说，这将花费比你更长的时间。我认为可能有一种方法可以计算有限集并确定何时对模式进行详细说明超出其他正则表达式的要求，但这并不简单。

例如，只需考虑简单的表达式 (ab)* 和 (aba)*b。什么算法将决定从第一个表达式生成 abab 然后停止，而不检查 ababab、abababab 等，因为它们会从来不工作？您不能只生成字符串并检查直到找到匹配项，因为当语言不相交时，这永远不会完成。我无法想象在一般情况下有什么可行的方法，但是在这种事情上有人比我更好。

总而言之，这是一个难题。如果我知道存在多项式时间解决方案，我会感到有点惊讶，而如果我知道它相当于停止问题，我一点也不感到惊讶。尽管考虑到正则表达式不是图灵完备的，但似乎至少有可能存在解决方案。

回复收藏 0 原文

小情绪 2024-07-19 08:08:12

我将执行以下操作：

使用类似以下结构的内容将每个正则表达式转换为 FSA：

结构 FSANode 
  { 
      布尔接受； 
      映射   链接; 
  } 
  列表   节点； 
  FSA节点启动；

请注意，这并不简单，但对于简单的正则表达式来说应该不会那么困难。

创建一个新的组合节点，例如：

类组合节点 
  { 
      组合节点（FSANode 左，FSANode 右） 
      { 
          this.left = 左； 
          this.right = 正确； 
      } 

      Map<字符，组合节点>   链接; 
      bool valid { get { return !left.accept ||   ！对。接受；   } } 

      公共 FSANode 离开； 
      公共 FSANode 权利； 
  }

根据左侧和右侧相同的字符构建链接，您将获得两个 FSANode，这两个 FSANode 构成一个新的组合节点。

然后从CombinedNode(leftStart, rightStart)开始，找到生成集，如果有任何无效的CombinedNode，则该集不是“正交的”。

I would do the following:

convert each regex to a FSA, using something like the following structure:

struct FSANode
{
    bool accept;
    Map<char, FSANode> links;
}
List<FSANode> nodes;
FSANode start;

Note that this isn't trivial, but for simple regex shouldn't be that difficult.

Make a new Combined Node like:

class CombinedNode
{
    CombinedNode(FSANode left, FSANode right)
    {
        this.left = left;
        this.right = right;
    }

    Map<char, CombinedNode> links;
    bool valid { get { return !left.accept || !right.accept; } }

    public FSANode left;
    public FSANode right;
}

Build up links based on following the same char on the left and right sides, and you get two FSANodes which make a new CombinedNode.

Then start at CombinedNode(leftStart, rightStart), and find the spanning set, and if there are any non-valid CombinedNodes, the set isn't "orthogonal."

回复收藏 0 原文

爱殇璃 2024-07-19 08:08:12

将每个正则表达式转换为 DFA。从一个 DFA 的接受状态创建到第二个 DFA 的开始状态的 epsilon 转换。您实际上已经通过添加 epsilon 转换创建了 NFA。然后将NFA转换为DFA。如果起始状态不是接受状态，并且接受状态是可达的，则两个正则表达式不是“正交的”。（因为它们的交集非空。）

存在将正则表达式转换为 DFA 以及将 NFA 转换为 DFA 的已知过程。你可以看看Sipser的《Introduction to the Theory of Computation》之类的书来了解程序，或者直接在网上搜索。毫无疑问，许多本科生和研究生必须在一门或另一门“理论”课程中这样做。

回复收藏 0 原文