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

如您所见，只有第一组匹配，而我看不到匹配其他两组的方法。

更多发现 - 使用上面的自动机库，问题将简化为：如果连接两个或多个自动机，如何识别最终状态与原始自动机中的哪一个对应？

4

3 回答 3

6

我基于 dk.brics.automaton 实现了这样一个解决方案，你可以在这里找到它。 https://github.com/fulmicoton/multiregexp

于 2013-10-20T17:14:57.097 回答
3

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

  1. 你说正则表达式的列表很大；你可以说得更详细点吗？数千？百万？数十亿和数十亿？

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

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

  4. 您是否可以从列表中的所有正则表达式中提取任何共同因素，例如最小或最大长度、公共子字符串或共享字符子集？例如，与您的示例模式之一匹配的任何字符串也必须匹配[abc]{3}。如果有，您可能希望基于它们创建过滤器（可能是正则表达式，也可能不是），以便在严重匹配开始之前运行。（如果您使用的是 Perl，我不建议这样做，它是 choc-a-bloc 已经进行了类似的优化，但 Java 并不太自豪接受一点帮助。☺）

但我觉得建议您使用单独的正则表达式而不是将它们全部连接成一个非常安全。Frankenregex 不一定会表现得更好，而对其进行故障排除将是一场噩梦！您可以预编译所有 Pattern 对象，并且可以提前创建一个 Matcher 对象并将其重用于所有匹配项，如下所示：

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

这是一个演示。我无法做出任何保证（一方面，你仍然受制于编写正则表达式的人），但如果解决方案可行，我认为这是最有希望的方法。

于 2013-03-09T15:12:05.150 回答
3

dk.brics.automaton不直接支持这一点，但您可以概括自动机的表示（以及相关的自动机操作）以区分不同种类的接受状态。例如，首先将一个 int 字段添加到State类，并在设置了“accept”时使用此字段。

于 2013-03-09T15:24:18.167 回答