Comprueba si una expresión regular cubre otra expresión regular

Question

Estoy intentando implementar un algoritmo de agrupamiento de texto. El algoritmo agrupa líneas similares de texto en bruto reemplazándolas por expresiones regulares y agrega el número de patrones que coinciden con cada expresión regular para proporcionar un resumen ordenado del texto de entrada en lugar de mostrar patrones repetitivos del texto de entrada. En este intento, me encontré con la necesidad de encontrar si una expresión regular cubre a otra.

Supongamos que nos interesa única acerca de las expresiones regulares con '*' y tarjetas '+' salvajes es decir, '*' significa cero o más ocurrencias de un alfabeto, y '+' significa 1 o más ocurrencias de un alfabeto. También suponga que el conjunto de caracteres es ASCII.

Por ejemplo:

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. 

Básicamente estoy buscando una implementación eficiente del método siguiente, que indica si strA (puede contener una expresión regular) fundas para strB (puede contener una expresión regular). Tenga en cuenta que también debería haber una forma de escapar de los caracteres regex '*' y '+' en las cadenas de entrada strA y strB.

método de firma en C++:

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

Mi pensamiento es que se requiere un enfoque recursivo para la aplicación y puede ser un poco complicado. Pero tengo curiosidad por saber si puedo reutilizar las implementaciones existentes en lugar de reinventar la rueda o si hay otras formas directas de hacerlo.

Answer 1

compruebe this perl module source pero recuerda que no funcionaría para todas las expresiones regulares (ya que dará lugar a la resolución del halting problem.

Answer 2

que haría algo así como la implementación de una función para encontrar el mínimo de DFA de una expresión regular dada. Vamos Supongamos que

DFA GetMinimalDFA (regex r1) hace eso.

bool isParentRegex(Regex r1, Regex r2) { 
    DFA a = GetMinimalDFA(r1); 
    DFA b = GetMinimalDFA(Regex.OR(r1,r2)) 
    return a.Equals(b); 
} 

Answer 3

Teniendo en cuenta la gramática simple expresión regular que se propone, la solución es bastante trivial.

Tomar su ejemplo más complejo, A+M+BC* covers AMM+B+C+M+BC* puede volver a escribir como A{1,}M{1,}B{1,1}C{0,} cubre A{1,1}M{2,}B{1,}C{1,}M{1,}B{1,1}C{0,}

Esto nos lleva a la regla simple: R1 cubre R2 si todos los símbolos aparecen en el mismo orden, todos los límites inferiores de R1 son menos o igual a los de R2, y los límites superiores de R1 son más o iguales que los de R2.

Ahora hay un pequeño problema con la regla simple. AB*C cubre AC, es decir, existe la posibilidad de que aparezca un símbolo opcional en R1 y no en R2. Puede resolverlo insertando un {0,0} en R2 cuando hay un símbolo (opcional) en R1 que no aparece en la posición equivalente en R2. P.ej. AB*C cubre AB{0,0}C.

La regla del "símbolo opcional" es una optimización. Si el símbolo en R1 no es opcional, R1 ciertamente no cubre R2. P.ej. AB+C no cubre AC.Por lo tanto, no es necesario insertar un B{0,0}. Pero si lo hace, verá que A{1,1}B{1,}C{1,1} no cubre A{1,1}B{0,0}C{1,1} ya que el límite inferior de R1B (1) es más que el límite inferior de R2B (0)

Answer 4

En Perl, esto sería bastante simple . El primer paso es para normalizar cada expresión regular cambiando A+-AA*, A*A-AA*, y 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 $_; 
} 

paso dos es para convertir la primera expresión regular de una expresión regular que coincide con los propios cuerdas, a una perl- regex que coincide con las expresiones regulares normalizadas que coinciden con esas cadenas; por ejemplo, AA*B se convertiría a ^AA*\*?B$, lo que significa "inicio de cadena, seguido de A, seguido de cero o más A, seguido de un asterisco, seguido de B, seguido por el final de la cadena":

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

Paso tres necesidades ninguna explicación:

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

Esto devuelve un valor verdadero para su casos # 1 – 3. Se devuelve un valor falso para su caso # 4, sin embargo, porque a menos que estoy realmente falta algo, A+M+BC* hace no tapa AMM+B+C+M+BC*?

Tenga en cuenta que también debería haber una forma de escapar de los caracteres de expresiones regulares '*' y '+' en las cadenas de entrada strA y strB.

No me preocupa que en el código anterior, pero ya que sólo estás preocupado por ASCII, un paso de preprocesamiento podría manejar \* significa *, \+ significa + y \\ significa \, traduciéndolos a un solo caracteres fuera del rango ASCII:

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

(aunque eso es obviamente bastante hackish).

En C++, puede usar el mismo enfoque — existen bibliotecas que implementan todas las características necesarias de Perl regexes — aunque obviamente sería un poco más trabajo.