Объединение нескольких регулярных выражений в один автомат

Question

Допустим, у меня есть список регулярных выражений (чтение из внешнего источника - файла, базы данных и т. Д.). Я хочу проверить, какому из этих регулярных выражений соответствует строка.

Я могу создать итерации по всем этим регулярным выражениям и сопоставить их, но список может быть огромным, и это критическая операция.

Я могу объединить все эти регулярные выражения в одно (с | между ними), но тогда проблема в том, что я могу идентифицировать только первое сопоставленное регулярное выражение, а не все.

Другая идея может состоять в том, чтобы создать автомат для всех этих регулярных выражений и пометить конечные состояния, скажем, индексами соответствующего регулярного выражения. Я искал 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

Как видите, сопоставляется только первая группа, и я не вижу способа сопоставить две другие.

Дополнительные выводы - Используя приведенную выше библиотеку автоматов, проблема сводится к следующему: если вы объединяете два или более автоматов, как вы можете определить для конечного состояния, какой из исходных автоматов соответствует?

Answer 1

http://www.brics.dk/automaton/ не поддерживает это напрямую, но вы можете обобщить представление автоматов (и соответствующих операций автоматов), чтобы различать различные типы принимаемых состояний. Начните с добавления поля int, например, в класс State, и используйте это поле всякий раз, когда установлено 'accept'.

Answer 2

Я реализовал такое решение на основе dk.brics.automaton, вы можете найти его здесь. https://github.com/fulmicoton/multiregexp

Answer 3

Для окончательного ответа (если он есть) нам понадобится дополнительная информация, например:

1. Вы говорите, что список регулярных выражений огромен; Вы можете быть более конкретным? Тысячи? Миллионы? Миллиарды и миллиарды?

2. Кто написал эти регулярные выражения, и знают ли они, что они делают? Проверены ли регулярные выражения (на корректность и производительность) перед добавлением в список?

3. В вашем примере кода вы используете matches() метод, который требует регулярного выражения для описания всей строки. Это действует так, как будто регулярное выражение действительно
   \A(?:(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c)))\z
   который соответствует "aba" но нет "aaba" или же "abaa", Если вы использовали регулярные выражения в других инструментах или языках до перехода на Java, это может вас удивить. Традиционно считается, что строка "соответствует" регулярному выражению, если регулярное выражение описывает любую подстроку в строке, даже подстроку нулевой длины. Чтобы получить такое поведение в Java, вы должны использовать Matcher's find() метод.

4. Существуют ли какие-либо общие факторы, которые вы можете извлечь из всех регулярных выражений в списке, такие как минимальная или максимальная длина, общие подстроки или общие подмножества символов? Например, любая строка, которая соответствует одному из ваших образцов, также должна соответствовать [abc]{3}, Если есть, вы можете создать фильтры на их основе (может быть, регулярное выражение, а может и нет), чтобы они запускались до того, как начнется серьезное сопоставление. (Я бы не советовал этого, если бы вы использовали Perl, который является choc-a-block с уже подобными оптимизациями, но Java не слишком горда, чтобы принять небольшую помощь. ☺)

Но я чувствую себя довольно безопасно, советуя вам использовать отдельные регулярные выражения, а не объединять их все в одно. Frankenregex не обязательно будет работать лучше, и устранение неполадок будет кошмаром! Вы можете предварительно скомпилировать все объекты Pattern, и вы можете заранее создать объект Matcher и повторно использовать его для всех совпадений, например, так:

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

Вот демо. Я не могу дать никаких гарантий (вы все еще во власти того, кто бы ни написал регулярные выражения, во-первых), но если решение возможно, я думаю, что это самый многообещающий подход.