Эффективный запрос одной строки к нескольким регулярным выражениям - PullRequest
Новая
       84

Эффективный запрос одной строки к нескольким регулярным выражениям

45 голосов
/ 11 октября 2008

Допустим, у меня есть 10000 регулярных выражений и одна строка, и я хочу выяснить, соответствует ли строка любому из них, и получить все совпадения. Тривиальный способ сделать это - просто запросить строку один за другим для всех регулярных выражений. Есть ли более быстрый и эффективный способ сделать это?

EDIT: Я попытался заменить его DFA (лекс) Проблема здесь в том, что это даст вам только один шаблон. Если у меня есть строка "hello" и шаблоны "[H | h] ello" и ". {0,20} ello", DFA будет соответствовать только одному из них, но я хочу, чтобы они оба ударили.

Ответы [ 17 ]

2 голосов
/ 11 октября 2008

Если вы используете реальные регулярные выражения (те, которые соответствуют регулярным языкам из теории формальных языков, а не каким-то нерегулярным Perl-вещам), то вам повезло, потому что регулярные языки закрыты на объединение , В большинстве языков регулярных выражений pipe (|) - это union. Таким образом, вы должны иметь возможность построить строку (представляющую нужное вам регулярное выражение) следующим образом: 

(r1)|(r2)|(r3)|...|(r10000)

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

1 голос
/ 11 октября 2008

Вы можете скомпилировать регулярное выражение в гибридный DFA / Автомат Bucchi , где каждый раз, когда БА входит в состояние принятия, вы отмечаете, что правило регулярного выражения "срабатывает".

Bucchi немного излишне для этого, но изменение способа работы вашего DFA может помочь.

0 голосов
/ 01 сентября 2009

Самый быстрый способ сделать это, кажется, что-то вроде этого (код C #): 

public static List<Regex> FindAllMatches(string s, List<Regex> regexes)
{
    List<Regex> matches = new List<Regex>();
    foreach (Regex r in regexes)
    {
        if (r.IsMatch(string))
        {
            matches.Add(r);
        }
    }
    return matches;
}

О, вы имели в виду самый быстрый код ? тогда я не знаю ....

0 голосов
/ 11 октября 2008

Я думаю, что краткий ответ таков: да, есть способ сделать это, и что это хорошо известно информатике, и что я не могу вспомнить, что это такое.

Краткий ответ: вы можете обнаружить, что ваш интерпретатор регулярных выражений уже эффективно справляется со всеми этими вопросами, когда | Если нет, то вам пора поискать в Google алгоритмы сопоставления строк и поиска.

0 голосов
/ 11 октября 2008

Я бы почти предложил написать механизм регулярных выражений "наизнанку" - тот, в котором "target" был регулярным выражением, а "term" был строкой.

Однако, похоже, что ваше решение попробовать каждый из них итеративно будет намного проще.

0 голосов
/ 19 марта 2018

Я использую Ragel с уходящим действием: 

action hello {...}
action ello {...}
action ello2 {...}
main := /[Hh]ello/  % hello |
        /.+ello/ % ello |
        any{0,20} "ello"  % ello2 ;

Строка "hello" будет вызывать код в блоке action hello, затем в блоке action ello и, наконец, в блоке action ello2.

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

0 голосов
/ 11 октября 2008

Попробуйте объединить их в одно большое регулярное выражение?

Страница:
...