logo标签列表

将多个正则表达式合并为一个自动机

javaregexautomaton
11
假设我有一个正则表达式列表(从外部源-文件、数据库等读取)。我想检查哪些正则表达式与一个字符串匹配。
我可以遍历所有这些正则表达式并进行匹配，但列表可能很大，这是一个关键操作。
我可以将所有这些正则表达式合并为一个(用|分隔)，但问题是我只能识别第一个匹配的正则表达式，而无法得到全部匹配的结果。
另一个想法是为所有这些正则表达式创建一个自动机，并使用相应正则表达式的索引标记最终状态。我看了一下http://cs.au.dk/~amoeller/automaton/，这个库似乎能够处理正则表达式和自动机，但不确定它是否可以扩展来解决我的问题。
你还有其他想法吗？
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class PatternTest {
    public static void main(String[] args) {
        Pattern p = Pattern.compile("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))");     
        Matcher m = p.matcher("aba");
        System.out.println(m.matches());
        System.out.println(m.groupCount());
        for (int i = 0, n = m.groupCount(); i < n; i++) {
            System.out.println(m.group(i));
        }
    }
}

将会打印出

true
3
aba
aba
null

正如您所看到的，只有第一组匹配成功，我没有找到一种方法来匹配另外两个。

更多发现 - 使用上述的自动机库，问题将归结为以下：如果将两个或多个自动机串联起来，如何确定最终状态对应于哪个原始自动机？

你是否考虑为每个 | 连接的表达式添加命名组？这样你就可以检查哪些匹配了。 - Michael W
这些听起来像是你在Java中的选项。但在Perl中，这会更容易。你可以轻松地交替所有表达式，并在每个表达式（称为 X）的末尾添加例如 (?{ $matched{X} = 1 })(?!)。这将标记表达式 X 为匹配，并失败匹配，允许其他表达式也进行匹配。（为了优化它，你还可以将每个表达式放入一个原子捕获组中。） - Qtax
@MichaelW：是的，我也考虑过这个。问题在于Java中的正则表达式只匹配第一个组（命名或未命名）。 - Adrian Ber
@Qtax：问题是我是否可以在Java中做这样的事情。 - Adrian Ber
即使这是可能的，它似乎并不是更好的设计，甚至可能比分别完成还要慢。 - Alb
1
如果使用自动机实现正则表达式，则算法复杂度将取决于自动机的深度。将它们组合在一起将导致复杂度取决于这些正则表达式的最大长度，而不是迭代它们将导致总和。 - Adrian Ber
3个回答
6
3

dk.brics.automaton不直接支持此功能，但您可以将自动机的表示（和相关的自动机操作）泛化以区分不同类型的接受状态。首先，在State类中添加一个int字段，并在设置“accept”时使用此字段。

3

如果有确定的答案（如果有的话），我们需要更多的信息，例如：

  1. 你说正则表达式列表很大，能更具体一些吗？是千个、百万个、十亿个还是更多？

  2. 谁编写了这些正则表达式？他们知道自己在做什么吗？这些正则表达式在加入列表之前是否经过了彻底的测试（包括正确性和性能）？

  3. 在你的示例代码中，你使用了matches()方法，它要求正则表达式描述整个字符串。它的行为就像正则表达式实际上是
    \A(?:(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c)))\z
    该正则表达式匹配"aba"但不匹配"aaba"或"abaa"。如果你在使用Java之前已经在其他工具或语言中使用过正则表达式，这种行为可能会让你感到惊讶。传统上，如果正则表达式描述了字符串中的任何子字符串，甚至是零长度子字符串，那么该字符串就被认为与正则表达式“匹配”。要在Java中获得这种行为，必须使用Matcher的find()方法。

  4. 是否有任何常见因素可以从列表中的所有正则表达式中提取出来，比如最小或最大长度、共同子字符串或共享字符子集？例如，与你的示例模式之一匹配的任何字符串也必须匹配[abc]{3}。如果有的话，你可能需要基于它们创建过滤器（可能是正则表达式，也可能不是），在严格匹配开始之前运行。（如果你使用Perl，我不会建议这样做，因为它已经充满了这样的优化，但Java并不太骄傲，接受一点帮助也无妨。☺）

但我认为最好使用单独的正则表达式，而不是将它们全部连接成一个。强制拼接的 Frankenregex 不一定会有更好的性能，并且排除故障将是一场噩梦！你可以预编译所有的 Pattern 对象，并提前创建 Matcher 对象并重复使用它来进行所有匹配，像这样：

m.reset(s).usePattern(p);

这里有一个演示。我不能保证（你仍然受制于编写正则表达式的人），但如果有解决方案，我认为这是最有希望的方法。
很棒的答案。也许是因为这正是我想的，但附加的演示很好，我学到了之前没有考虑过的reset(x)功能。 - Omertron
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接