regex - probar - Algoritmo para averiguar si las coincidencias de dos patrones de Glob(o expresiones regulares) se cruzan

probar expresiones regulares

Question

Estoy buscando patrones de estilo glob similares a los que acepta el comando Redis KEYS . Citando

• h? llo coincide con hola, hallo y hxllo
• h * llo coincide con hllo y heeeello
• h [ae] llo coincide con hola y hola, pero no con hillo

Pero no estoy comparando con una cadena de texto, sino comparando el patrón con otro patrón con todos los operadores siendo significativos en ambos extremos.

Por ejemplo, estos patrones deben coincidir entre sí en la misma fila:

prefix*       prefix:extended*
*suffix       *:extended:suffix
left*right    left*middle*right
a*b*c         a*b*d*b*c
hello*        *ok
pre[ab]fix*   pre[bc]fix*

Y estos no deben coincidir:

prefix*       wrong:prefix:*
*suffix       *suffix:wrong
left*right    right*middle*left
pre[ab]fix*   pre[xy]fix*
?*b*?         bcb

Así que me pregunto ...

• si es posible hacerlo (implementar un algoritmo de verificación), si es que lo hace?
• Si no es posible, ¿qué subconjunto de expresiones regulares sería posible? (es decir, no permitir * comodín?)
• Si es posible, ¿qué es un algoritmo eficiente?
• ¿Cuáles son los tiempos de complejidad requeridos?

EDITAR: Encontré esta otra pregunta en el subconjunto RegEx, pero esta no es exactamente la misma que las palabras que hello* y *ok coinciden, no es un subconjunto / superconjunto entre sí, pero sí se cruzan.

Así que supongo matemáticamente, esto podría ser expresado como; ¿es posible verificar de manera determinista que un conjunto de palabras que coincida con un patrón, que se intersecan con un conjunto de palabras que coincide con otro patrón, da como resultado un conjunto no vacío?

EDITAR: un amigo @neizod elaboró ​​esta tabla de eliminación que visualiza cuidadosamente lo que podría ser una solución potencial / parcial: regla de eliminación

EDITAR: Will agrega una recompensa adicional para aquellos que también pueden proporcionar código de trabajo (en cualquier idioma) y casos de prueba que lo demuestren.

EDITAR: Agregó el? * B *? Caso de prueba descubierto por @DanielGimenez en los comentarios.

Answer 1

¡Buena pregunta!

La principal complejidad aquí es el manejo de clases de caracteres ( [...] ). Mi enfoque es reemplazar cada uno con una expresión regular que busque exactamente uno de los caracteres especificados (o ? ) U otra clase de caracteres que incluya al menos uno de los caracteres especificados. Entonces para [xyz] , esto sería: ([xyz?]|/[[^/]]*[xyz].*?/]) - vea más abajo:

Luego, para "prefijos" (todo antes del primer * ), ponga ^ al principio o para "sufijos" (todo después del último * ), ponga $ al final.

Más detalles:-

1. También es necesario reemplazar todas las instancias de ? con (/[.*?/]|[^//]]) para que coincida con una clase de caracteres o un solo carácter (excluyendo un corchete de apertura).
2. ¿También es necesario reemplazar cada carácter individual que no está en una clase de carácter y no lo está ? para que coincida con el mismo personaje ? o una clase de personaje que incluye al personaje. Por ejemplo, a se convertiría en ([a?]|/[[^/]]*a.*?/]) . (Un poco largo, pero resultó ser necesario, vea los comentarios a continuación).
3. La prueba se debe realizar en ambos sentidos de la siguiente manera: el prefijo de prueba n . ° 1 se convirtió en regex frente al prefijo n. ° 2, luego el prefijo de prueba n. Si cualquiera de las dos coincidencias, se puede decir que los prefijos "se intersecan".
4. Repita el paso (3) para los sufijos: para obtener un resultado positivo, los prefijos y los sufijos deben intersecarse.

EDITAR: Además de lo anterior, hay un caso especial cuando uno de los patrones contiene al menos uno * pero el otro no. En este caso, todo el patrón con * debe convertirse en una expresión regular: * debe coincidir con cualquier cosa, pero con la condición de que solo incluya clases de caracteres completos . Esto se puede hacer reemplazando todas las instancias de * con (/[.*?/]|[^//]]) .

Para evitar que esta respuesta sea voluminosa, no publicaré el código completo, pero hay una demostración de trabajo con pruebas de unidad aquí: http://jsfiddle.net/mb3Hn/4/

EDICIÓN # 2 - Incompleto conocido: en su forma actual, la demostración no se ocupa de los caracteres escapados (por ejemplo, /[ ). No es una gran excusa, pero solo lo noté tarde en el día, no se mencionan en la pregunta, solo en el enlace . Para manejarlos, se necesitaría un poco de complejidad de expresiones regulares adicionales, por ejemplo, para verificar la no existencia de una barra invertida inmediatamente antes de [ . Esto debería ser bastante indoloro con un aspecto negativo, pero desafortunadamente, Javascript no lo admite. Existen soluciones alternativas, como revertir tanto la cadena como la expresión regular con lookahead negativo, pero no estoy interesado en hacer que el código sea menos legible con esta complejidad adicional y no estoy seguro de lo importante que es para el OP, por lo que lo dejaré como un "ejercicio para hay lector ". En retrospectiva, ¡quizás debería haber elegido un idioma con un soporte de expresiones regulares más completo!

Answer 2

Con su lenguaje de patrón muy reducido, el enlace de pastebin en su pregunta y los comentarios de jpmc26 están prácticamente al mismo nivel: la pregunta principal es si el extremo izquierdo y derecho literal de las cadenas de entrada coinciden. Si lo hacen, y ambos contienen al menos un * , las cadenas coinciden (porque siempre puedes hacer coincidir el texto literal intermedio de las otras cadenas con esa estrella). Hay un caso especial: si solo uno de ellos está vacío (después de eliminar el prefijo y el sufijo), aún pueden coincidir si el otro está compuesto completamente por * s.

Por supuesto, al verificar si los extremos de la cadena coinciden, ¿debe tener en cuenta el carácter comodín de un solo carácter ? y clases de personajes, también. El carácter comodín de un solo carácter es fácil: no puede fallar, porque siempre coincidirá con lo que sea el otro carácter. Si es una clase de personaje, y el otro es solo un personaje, debes verificar si el personaje está en la clase. Si son ambas clases, necesita verificar una intersección de las clases (que es una simple intersección de conjunto).

Aquí está todo eso en JavaScript (verifique los comentarios del código para ver cómo el algoritmo que describí anteriormente se asigna al código):

var trueInput = [
    { left: ''prefix*'', right: ''prefix:extended*'' },
    { left: ''*suffix'', right: ''*:extended:suffix'' },
    { left: ''left*right'', right: ''left*middle*right'' },
    { left: ''a*b*c'', right: ''a*b*d*b*c'' },
    { left: ''hello*'', right: ''*ok'' },
    { left: ''*'', right: ''*''},
    { left: ''*'', right: ''**''},
    { left: ''*'', right: ''''},
    { left: '''', right: ''''},
    { left: ''abc'', right: ''a*c''},
    { left: ''a*c'', right: ''a*c''},
    { left: ''a[bc]d'', right: ''acd''},
    { left: ''a[bc]d'', right: ''a[ce]d''},
    { left: ''a?d'', right: ''acd''},
    { left: ''a[bc]d*wyz'', right: ''abd*w[xy]z''},
];

var falseInput = [
    { left: ''prefix*'', right: ''wrong:prefix:*'' },
    { left: ''*suffix'', right: ''*suffix:wrong'' },
    { left: ''left*right'', right: ''right*middle*left'' },
    { left: ''abc'', right: ''abcde''},
    { left: ''abcde'', right: ''abc''},
    { left: ''a[bc]d'', right: ''aed''},
    { left: ''a[bc]d'', right: ''a[fe]d''},
    { left: ''a?e'', right: ''acd''},
    { left: ''a[bc]d*wyz'', right: ''abc*w[ab]z''},
];

// Expects either a single-character string (for literal strings
// and single-character wildcards) or an array (for character
// classes).
var characterIntersect = function(a,b) {
    // If one is a wildcard, there is an intersection.
    if (a === ''?'' || b === ''?'')
        return true;

    // If both are characters, they must be the same.
    if (typeof a === ''string'' && typeof b === ''string'')
        return a === b;

    // If one is a character class, we check that the other
    // is contained in the class.
    if (a instanceof Array && typeof b === ''string'')
        return (a.indexOf(b) > -1);
    if (b instanceof Array && typeof a === ''string'')
        return (b.indexOf(a) > -1);

    // Now both have to be arrays, so we need to check whether
    // they intersect.
    return a.filter(function(character) {
        return (b.indexOf(character) > -1);
    }).length > 0;
};

var patternIntersect = function(a,b) {
    // Turn the strings into character arrays because they are
    // easier to deal with.
    a = a.split("");
    b = b.split("");

    // Check the beginnings of the string (up until the first *
    // in either of them).
    while (a.length && b.length && a[0] !== ''*'' && b[0] !== ''*'')
    {
        // Remove the first character from each. If it''s a [,
        // extract an array of all characters in the class.
        aChar = a.shift();
        if (aChar == ''['')
        {
            aChar = a.splice(0, a.indexOf('']''));
            a.shift(); // remove the ]
        }
        bChar = b.shift();
        if (bChar == ''['')
        {
            bChar = b.splice(0, b.indexOf('']''));
            b.shift(); // remove the ]
        }

        // Check if the two characters or classes overlap.
        if (!characterIntersect(aChar, bChar))
            return false;
    }

    // Same thing, but for the end of the string.
    while (a.length && b.length && a[a.length-1] !== ''*'' && b[b.length-1] !== ''*'')
    {
        aChar = a.pop();
        if (aChar == '']'')
        {
            aChar = a.splice(a.indexOf(''['')+1, Number.MAX_VALUE);
            a.pop(); // remove the [
        }
        bChar = b.pop();
        if (bChar == '']'')
        {
            bChar = b.splice(b.indexOf(''['')+1, Number.MAX_VALUE);
            b.pop(); // remove the [
        }

        if (!characterIntersect(aChar, bChar))
            return false;
    }

    // If one string is empty, the other has to be empty, too, or
    // consist only of stars.
    if (!a.length && /[^*]/.test(b.join('''')) ||
        !b.length && /[^*]/.test(b.join('''')))
        return false;

    // The only case not covered above is that both strings contain
    // a * in which case they certainly overlap.
    return true;
};

console.log(''Should be all true:'');
console.log(trueInput.map(function(pair) {
    return patternIntersect(pair.left, pair.right);
}));

console.log(''Should be all false:'');
console.log(falseInput.map(function(pair) {
    return patternIntersect(pair.left, pair.right);
}));

No es la mejor implementación, pero funciona y es (con suerte) todavía bastante legible. Hay un poco de duplicación de código con la comprobación del principio y el final (lo que podría aliviarse con un simple reverse después de verificar el inicio, pero pensé que eso solo ocultaría las cosas). Y probablemente hay muchos otros bits que podrían mejorarse enormemente, pero creo que la lógica está en su lugar.

Algunas observaciones más: la implementación asume que los patrones están bien formateados (no hay paréntesis de apertura o cierre inigualables). Además, tomé el código de intersección de matriz de esta respuesta porque es compacto: ciertamente podría mejorar la eficiencia si fuera necesario.

Independientemente de los detalles de la implementación, creo que también puedo responder a su pregunta de complejidad: el bucle externo recorre ambas cadenas al mismo tiempo, un personaje a la vez. Así que eso es complejidad lineal. Todo dentro del bucle se puede hacer en tiempo constante, excepto las pruebas de clase de caracteres. Si un carácter es una clase de carácter y el otro no, necesita tiempo lineal (con el tamaño de la clase como parámetro) para verificar si el carácter está en la clase. Pero esto no lo hace cuadrático, porque cada personaje de la clase significa una iteración menos del bucle externo. Así que eso sigue siendo lineal. Lo más costoso es, por lo tanto, la intersección de dos clases de caracteres. Esto puede ser más complejo que el tiempo lineal, pero lo peor que puede obtener es O(N log N) : después de todo, puede clasificar ambas clases de caracteres y luego encontrar una intersección en el tiempo lineal. Creo que incluso podría ser capaz de obtener una complejidad de tiempo lineal total, al incluir los caracteres de la clase de caracteres en su punto de código Unicode ( .charCodeAt(0) en JS) o algún otro número, y encontrar una intersección en un conjunto de hash es posible en tiempo lineal. Entonces, si realmente quieres, creo que deberías poder llegar a O(N) .

¿Y qué es N ? El límite superior es la suma de la longitud de ambos patrones, pero en la mayoría de los casos será menor (dependiendo de la longitud de los prefijos y los sufijos de ambos patrones).

Por favor, indíqueme los casos de borde que faltan en mi algoritmo. También estoy contento con las mejoras sugeridas, si mejoran o al menos no reducen la claridad del código.

Aquí hay una demostración en vivo en JSBin (gracias a chakrit por pegarla allí).

EDITAR: Como señaló Daniel, hay un caso conceptual de borde que mi algoritmo pierde. Si (antes o después de la eliminación del principio y el final) una cadena no contiene * y la otra sí, existen casos en los que las dos siguen en conflicto. Desafortunadamente, no tengo tiempo ahora para ajustar mi fragmento de código para acomodar ese problema, pero puedo describir cómo resolverlo.

Después de eliminar ambos extremos de las cadenas, si ambas cadenas están vacías o contienen al menos * , siempre coincidirán (verán las posibles distribuciones * después de la eliminación completa para ver esto). El único caso que no es trivial es si una cadena aún contiene * , pero la otra no (sea vacía o no). Lo que ahora tenemos que hacer es caminar ambas cuerdas nuevamente de izquierda a derecha. Permítame llamar a la cadena que contiene * A y la que no contiene * B.

Caminamos A de izquierda a derecha, omitiendo todo * (prestando atención solo a ? Clases de caracteres y caracteres literales). Para cada uno de los tokens relevantes, verificamos de izquierda a derecha, si se puede hacer coincidir en B (parando en la primera aparición) y avanzamos nuestro cursor B a esa posición. Si alguna vez encontramos un token en A que ya no se puede encontrar en B, no coinciden. Si logramos encontrar una coincidencia para cada token en A, coinciden. De esta manera, todavía utilizamos el tiempo lineal, porque no hay retroceso involucrado. Aquí hay dos ejemplos. Estos dos deben coincidir:

A: *a*[bc]*?*d* --- B: db?bdfdc
    ^                    ^
A: *a*[bc]*?*d* --- B: db?bdfdc
      ^                   ^
A: *a*[bc]*?*d* --- B: db?bdfdc
           ^               ^
A: *a*[bc]*?*d* --- B: db?bdfdc
             ^               ^

Estos dos no deben coincidir:

A: *a*[bc]*?*d* --- B: dbabdfc
    ^                    ^
A: *a*[bc]*?*d* --- B: dbabdfc
      ^                   ^
A: *a*[bc]*?*d* --- B: dbabdfc
           ^               ^
A: *a*[bc]*?*d* --- B: dbabdfc
             !               

Falla, porque el ? posiblemente no puede coincidir antes de la segunda d , después de lo cual no hay más d en B para acomodar la última d en A.

Esto probablemente sería fácil de agregar a mi implementación actual, si me hubiera tomado el tiempo de analizar correctamente la cadena en objetos de token. Pero ahora, tendría que pasar por la molestia de analizar esas clases de personajes nuevamente. Espero que este esquema escrito de la adición sea suficiente ayuda.

PD: Por supuesto, mi implementación tampoco tiene en cuenta los metacaracteres que se escapan y podría ahogarse con * dentro de las clases de caracteres.

Answer 3

Determinar si una expresión regular coincide con un subconjunto de otra expresión regular utilizando greenery :

Primero, pip3 install https://github.com/ferno/greenery/archive/master.zip .

Entonces:

from greenery.lego import parse as p
a_z = p("[a-z]")
b_x = p("[b-x]")
assert a_z | b_x == a_z
m_n = p("m|n")
zero_nine = p("[0-9]")
assert not m_n | zero_nine == m_n

Answer 4

Estos patrones especiales son considerablemente menos potentes que las expresiones regulares completas, pero señalaré que es posible hacer lo que quiera incluso con expresiones regulares generales. Estas deben ser expresiones regulares "verdaderas", es decir, aquellas que usan solo la estrella Kleene, la alternancia (la operación) y la concatenación con cualquier alfabeto fijo más la cadena vacía y el conjunto vacío. Por supuesto, también puede usar cualquier azúcar sintáctica en estas operaciones: una o más (+), opcional (?). Los conjuntos de caracteres son solo un tipo especial de alternancia [ac] == a | b | c.

El algoritmo es simple en principio: Convierta cada expresión regular a un DFA usando las construcciones estándar: Thompson seguido de powerset. Luego use la construcción del producto cruzado para calcular la intersección DFA de los dos originales. Finalmente, verifique esta intersección de DFA para determinar si acepta al menos una cadena. Esto es solo un dfs desde el estado de inicio para ver si se puede alcanzar un estado de aceptación.

Si no está familiarizado con estos algoritmos, es fácil encontrar referencias de Internet.

Si al menos una cadena es aceptada por la intersección DFA, hay una coincidencia entre las expresiones regulares originales, y la ruta descubierta por el dfs da una cadena que satisface ambas. De lo contrario no hay partido.

Answer 5

¡Ahora presencie la potencia de fuego de esta estación de batalla totalmente ARMADA y OPERATIVA!

(He trabajado demasiado en esta respuesta y mi cerebro se ha roto; debería haber una insignia para eso).

Para determinar si dos patrones se entrecruzan, he creado un analizador de seguimiento recursivo: cuando se encuentran estrellas Kleene, se crea una nueva pila, de modo que si falla en el futuro, todo retrocede y la estrella consume el siguiente carácter.

Puede ver el historial de esta respuesta para determinar cómo llegó a todo esto y por qué fue necesario, pero básicamente no fue suficiente para determinar una intersección mirando hacia adelante solo una ficha, que era lo que estaba haciendo antes.

Este fue el caso que rompió la respuesta anterior [abcd]d => *d . El conjunto coincide con la d después de la estrella , por lo que el lado izquierdo aún tendría fichas restantes, mientras que el lado derecho estaría completo. Sin embargo, estos dos patrones se entrecruzan en ad , bd , cd y dd , por lo que es necesario corregirlos. Mi casi O (N) respuesta fue descartada.

Lexer

El proceso de lexing es trivial, excepto que se procesan los caracteres de escape y elimina las estrellas redundantes. Los tokens se dividen en conjuntos , estrellas , carácter salvaje (?) Y carácter . Esto es diferente a mis versiones anteriores donde un token era una cadena de caracteres en lugar de un solo carácter. A medida que surgen más casos, tener cadenas como tokens era más un obstáculo que una ventaja.

Analizador

La mayoría de las funciones del analizador son bastante triviales. Un interruptor dado el tipo del lado izquierdo, llama a una función que es un interruptor que determina la función apropiada para compararlo con el tipo del lado derecho. El resultado de la comparación mejora los dos interruptores al receptor original, normalmente el bucle principal del analizador.

Analizando estrellas

La simplicidad termina con la estrella . Cuando se encuentra eso se hace cargo de todo. Primero compara el siguiente token de su lado con el del otro lado, avanzando el otro lado hasta que encuentra una coincidencia.

Una vez que se encuentra la coincidencia, luego verifica si todo coincide hasta el final de ambos patrones. Si lo hace, entonces los patrones se cruzan. De lo contrario, avanza el siguiente token del otro lado del original con el que se comparó y repite el proceso.

Cuando se encuentran dos anys , entonces el despegue en sus propias ramas alternativas a partir del siguiente token de cada uno.

function intersects(left, right) {
    var lt, rt,
        result = new CompareResult(null, null, true);

    lt = (!left || left instanceof Token) ? left : tokenize(left);
    rt = (!right || right instanceof Token) ? right : tokenize(right);

    while (result.isGood && (lt || rt)) {
        result = tokensCompare(lt, rt);

        lt = result.leftNext;
        rt = result.rightNext;
    }

    return result;
}

function tokensCompare(lt, rt) {
    if (!lt && rt) return tokensCompare(rt, lt).swapTokens();

    switch (lt.type) {
        case TokenType.Char: return charCompare(lt, rt);
        case TokenType.Single: return singleCompare(lt, rt);
        case TokenType.Set: return setCompare(lt, rt);
        case TokenType.AnyString: return anyCompare(lt, rt);
    }
}

function anyCompare(tAny, tOther) {
    if (!tOther) return new CompareResult(tAny.next, null);

    var result = CompareResult.BadResult;

    while (tOther && !result.isGood) {
        while (tOther && !result.isGood) {
            switch (tOther.type) {
                case TokenType.Char: result = charCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Single: result = singleCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Set: result = setCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.AnyString:
                    // the anyCompare from the intersects will take over the processing.
                    result = intersects(tAny, tOther.next);
                    if (result.isGood) return result;
                    return intersects(tOther, tAny.next).swapTokens();
            }

            if (!result.isGood) tOther = tOther.next;
        }

        if (result.isGood) {
            // we''ve found a starting point, but now we want to make sure this will always work.
            result = intersects(result.leftNext, result.rightNext);
            if (!result.isGood) tOther = tOther.next;
        }
    }

    // If we never got a good result that means we''ve eaten everything.
    if (!result.isGood) result = new CompareResult(tAny.next, null, true);

    return result;
}

function charCompare(tChar, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return charCharCompare(tChar, tOther); 
        case TokenType.Single: return new CompareResult(tChar.next, tOther.next);
        case TokenType.Set: return setCharCompare(tOther, tChar).swapTokens(); 
        case TokenType.AnyString: return anyCompare(tOther, tChar).swapTokens();
    }
}

function singleCompare(tSingle, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Single: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Set: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.AnyString: return anyCompare(tOther, tSingle).swapTokens();
    }
}
function setCompare(tSet, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return setCharCompare(tSet, tOther);
        case TokenType.Single: return new CompareResult(tSet.next, tOther.next);
        case TokenType.Set: return setSetCompare(tSet, tOther);
        case TokenType.AnyString: return anyCompare(tOther, tSet).swapTokens();
    }
}

function anySingleCompare(tAny, tSingle) {
    var nextResult = (tAny.next) ? singleCompare(tSingle, tAny.next).swapTokens() :
        new CompareResult(tAny, tSingle.next);
    return (nextResult.isGood) ? nextResult: new CompareResult(tAny, tSingle.next);
}

function anyCharCompare(tAny, tChar) {
    var nextResult = (tAny.next) ? charCompare(tChar, tAny.next).swapTokens() :
        new CompareResult(tAny, tChar.next);

    return (nextResult.isGood) ? nextResult : new CompareResult(tAny, tChar.next);
}

function charCharCompare(litA, litB) {
    return (litA.val === litB.val) ?
        new CompareResult(litA.next, litB.next) : CompareResult.BadResult;
}

function setCharCompare(tSet, tChar) {
    return (tSet.val.indexOf(tChar.val) > -1) ?
        new CompareResult(tSet.next, tChar.next) : CompareResult.BadResult;
}

function setSetCompare(tSetA, tSetB) {
    var setA = tSetA.val,
        setB = tSetB.val;

    for (var i = 0, il = setA.length; i < il; i++) {
        if (setB.indexOf(setA.charAt(i)) > -1) return new CompareResult(tSetA.next, tSetB.next);
    }
    return CompareResult.BadResult;
}

jsFiddle

Complejidad del tiempo

Cualquier cosa con las palabras "retroceso recursivo" en ella es al menos O (N ² ).

Mantenibilidad y legibilidad

A propósito, rompí cualquier rama en funciones propias con un interruptor singular. También usé constantes con nombre cuando bastaría una cadena de un solo carácter. Hacer esto hizo que el código fuera más largo y más detallado, pero creo que lo hace más fácil de seguir.

Pruebas

Puedes ver todas las pruebas en el violín. Puede ver los comentarios en la salida de Fiddle para recoger sus propósitos. Cada tipo de token fue probado contra cada tipo de token, pero no he hecho uno que probara todas las comparaciones posibles en una sola prueba. También se me ocurrieron unos cuantos al azar como el de abajo.

abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*

jsFiddle una interfaz en el jsFiddle si alguien quiere probar esto por sí mismos. El registro se rompe una vez que agregué la recursión.

No creo haber probado suficientes pruebas negativas, especialmente con la última versión que creé.

Mejoramiento

Actualmente la solución es una fuerza bruta, pero es suficiente para manejar cualquier caso. Me gustaría volver a esto en algún momento para mejorar la complejidad del tiempo con algunas optimizaciones simples.

Las comprobaciones al inicio para reducir las comparaciones podrían aumentar el tiempo de procesamiento para ciertos escenarios comunes. Por ejemplo, si un patrón comienza con una estrella y otro termina con uno, ya sabemos que se intersectarán. También puedo verificar todos los caracteres desde el inicio y el final de los patrones y eliminarlos si coinciden en ambos patrones. De esta manera quedan excluidos de cualquier recursión futura.

Expresiones de gratitud

Usé las pruebas de @m.buettner inicialmente para probar mi código antes de que yo creara las mías . También recorrí su código para ayudarme a entender mejor el problema.