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

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

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

Answer 2

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

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

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

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 не обязательно будет работать лучше, и устранение неполадок было бы кошмаром! Вы можете предварительно собрать все объекты шаблонных, и вы можете создать объект Сличитель загодя и использовать его для всех матчей, например, так:

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

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

Answer 3

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