Проверьте, охватывает ли одно регулярное выражение другое регулярное выражение - PullRequest
Новая
       32

Проверьте, охватывает ли одно регулярное выражение другое регулярное выражение

8 голосов
/ 27 марта 2012

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

Предположим, что нас интересует только о регулярных выражениях с символами '*' и '+', т.е. '*'означает ноль или более вхождений алфавита, а «+» означает 1 или более вхождений алфавита.Также предположим, что набор символов ASCII.

Например: 

1. AB covers AB
      This is straightforward.
2. ABC* covers ABC
      Because ABC* can generate: ABC, ABCC, ABCCC etc.
3. A*B+C* covers AB+C*
      Because A*B+C* can generate ABBC, AABBC, AABBCC etc. which covers
      all strings generated by AB+C*.
4. A+M+BC* covers AMM+B+C+M+BC*
      Similar to case [3] above.

В основном я ищу эффективную реализацию следующего метода, который сообщает, если strA (может содержать регулярное выражение)обложки для strB (может содержать регулярное выражение).Обратите внимание, что также должен быть способ избежать символов регулярного выражения '*' и '+' во входных строках strA и strB.

Подпись метода в C ++: 

bool isParentRegex(const string& strA, const string& strB)

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

Ответы [ 4 ]

4 голосов
/ 27 марта 2012

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

Возьмите более сложный пример, A+M+BC* covers AMM+B+C+M+BC* Вы можете переписать его как A{1,}M{1,}B{1,1}C{0,} обложки A{1,1}M{2,}B{1,}C{1,}M{1,}B{1,1}C{0,}

Это приводит нас к простому правилу: R1 охватывает R2, если все символы появляются в одном и том же порядке, все нижние границы R1 меньше или равны таковым у R2, а верхние границы R1 больше или равно, чем у R2.

Теперь есть одна небольшая проблема с простым правилом. AB*C охватывает AC, т. Е. Существует вероятность того, что дополнительный символ появляется в R1, а не в R2. Вы можете решить это, вставив {0,0} в R2, когда в R1 есть (необязательный) символ, который не появляется в эквивалентной позиции в R2. Например. AB*C охватывает AB{0,0}C.

Правило «необязательный символ» - это оптимизация. Если символ в R1 не является обязательным, R1 определенно не охватывает R2. Например. AB+C не распространяется на AC. Поэтому нет необходимости вставлять B{0,0}. Но если вы это сделаете, вы увидите, что A{1,1}B{1,}C{1,1} не покрывает A{1,1}B{0,0}C{1,1}, поскольку нижняя граница R1 для B (1) больше, чем нижняя граница R2 для B (0)

2 голосов
/ 28 марта 2012

В Perl это было бы довольно просто.Первый шаг - нормализовать каждое регулярное выражение, изменив A+ на AA*, A*A на AA* и A*A* на A*: 

sub normalize_regex($)
{
    local $_ = shift;
    s/(.)\+/$1$1*/g;
    1 while s/(.)\*\1(?!\*)/$1$1*/g or s/(.\*)\1/$1/g;
    return $_;
}

Второй шаг - преобразование первогорегулярное выражение от регулярного выражения, которое соответствует самим строкам, к Perl-регулярному выражению, которое соответствует нормализованным регулярным выражениям, которые соответствуют этим строкам;например, AA*B будет преобразовано в ^AA*\*?B$, что означает «начало строки, за которым следует A, за которым следует ноль или более A, за которыми следует звездочка, за которой следует B, а затем конец строки": 

sub regex_to_metaregex($)
{
    local $_ = shift;
    s/(.)(\*?)/$2 ? "\Q$1\E*(\Q$1\E\\*)?" : "\Q$1"/eg;
    return qr/^$_$/;
}

Шаг третий не нуждается в объяснении: 

sub does_regex1_cover_regex2($$)
{
    my ($r1, $r2) = @_;
    $r1 = regex_to_metaregex normalize_regex $r1;
    $r2 = normalize_regex $r2;
    return scalar $r2 =~ m/$r1/;
}

Это возвращает истинное значение для ваших дел # 1–3.Однако он возвращает ложное значение для вашего случая №4, потому что, если я действительно что-то упустил, A+M+BC* не не обложка AMM+B+C+M+BC*?

Обратите внимание, что тамтакже должен быть способ избежать символов регулярного выражения '*' и '+' во входных строках strA и strB.

Я не беспокоился об этом в приведенном выше коде, но так как выБеспокоясь только о ASCII, шаг предварительной обработки может обрабатывать \*, означающий *, \+, означающий +, и \\, означающий \, переводя их в отдельные символы вне диапазона ASCII: 

sub process_escapes($)
{
    local $_ = shift;
    s/\\\\/\x80/g;
    s/\\\+/\x81/g;
    s/\\\*/\x82/g;
    s/\x80/\\/g;
    return $_;
}

(хотя это, очевидно, довольно хакерски).

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

2 голосов
/ 27 марта 2012

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

DFA GetMinimalDFA (Regex r1) делает это.

bool isParentRegex(Regex r1, Regex r2) {
    DFA a = GetMinimalDFA(r1);
    DFA b = GetMinimalDFA(Regex.OR(r1,r2))
    return a.Equals(b);
}
0 голосов
/ 27 марта 2012

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

...