En informática , un algoritmo para hacer coincidir comodines (también conocido como globbing ) es útil para comparar cadenas de texto que pueden contener sintaxis de comodines . [1] Los usos comunes de estos algoritmos incluyen interfaces de línea de comandos , por ejemplo, Bourne shell [2] o la línea de comandos de Microsoft Windows [3] o el editor de texto o el administrador de archivos, así como las interfaces para algunos motores de búsqueda [4] y bases de datos. [5] La coincidencia de comodines es un subconjunto del problema de la coincidencia de expresiones regulares y la coincidencia de cadenas en general. [6]
Un comparador de comodines prueba un patrón comodín p con una cadena de entrada s . Realiza una comparación anclada y devuelve verdadero solo cuando p coincide con la totalidad de s .
El patrón puede basarse en cualquier sintaxis común (ver globbing ), pero en Windows los programadores tienden a discutir solo una sintaxis simplificada compatible con el entorno de ejecución nativo de C: [7] [8]
?coincide exactamente con una ocurrencia de cualquier carácter. *coincide con un número arbitrario de ocurrencias (incluso cero) de cualquier carácter.Este artículo analiza principalmente la formulación de Windows del problema, a menos que se indique lo contrario.
Enunciado en índices basados en cero, el problema de coincidencia de comodines se puede definir recursivamente como:
donde m ij es el resultado de hacer coincidir el patrón p con el texto t truncado en i y j caracteres respectivamente. Esta es la formulación utilizada por el algoritmo de Richter y el algoritmo Snippets que se encuentra en la colección de Cantatore. [9] [10] Esta descripción es similar a la distancia de Levenshtein .
Los problemas directamente relacionados con la informática incluyen:
?definido. [11] [12]Los primeros algoritmos para la búsqueda de comodines a menudo dependían de la recursión , pero la técnica fue criticada por razones de rendimiento [10] y confiabilidad [8] . Los algoritmos no recursivos para la búsqueda de comodines han ganado popularidad a la luz de estas consideraciones.
Entre los algoritmos recursivos y no recursivos, las estrategias para realizar la operación de comparación de patrones varían ampliamente, como se evidencia entre la variedad de algoritmos de ejemplo a los que se hace referencia a continuación. Se ha demostrado que el desarrollo de casos de prueba y las técnicas de optimización del rendimiento se aplican a ciertos algoritmos, en particular los desarrollados por críticos de los algoritmos recursivos.
La recursión generalmente ocurre *cuando hay más sufijos con los que comparar. Esta es una forma de retroceso , que también realizan algunos comparadores de expresiones regulares.
[...] (admite conjuntos de caracteres multibyte):La forma general de estos algoritmos es la misma. En la recursión, el algoritmo divide la entrada en subcadenas y considera que se ha producido una coincidencia cuando UNA de las subcadenas devuelve una coincidencia positiva. En el caso de dowild("*X", "abcX"), llamaría con avidez a dowild("X", "abcX"), dowild("X", "bcX"), dowild("X", "cX")y dowild("X", "X"). Por lo general, se diferencian por cuestiones menos importantes, como la compatibilidad con funciones, y por factores más importantes, como optimizaciones menores pero muy eficaces. Algunas de ellas son:
*y asegurarse de que UNA de las subcadenas devuelva una coincidencia positiva, el tiempo de ejecución se vuelve exponencial para rechazar una coincidencia con muchas *en el texto. Lars Mathiesen cambia el retorno a tres clases, match, no-match y ABORT (ninguna coincidencia posible en absoluto para la recursión de asteriscos). El valor ABORT se devuelve cuando el texto se consume demasiado pronto o cuando otra coincidencia de asteriscos ha fallado, lo que garantiza un rendimiento lineal con respecto al número de asteriscos. (La complejidad general es adicionalmente cuadrática con el número de caracteres que quedan por coincidir). [14] El wildmatch ABORT de Git/Rsync también cubre las entradas no válidas. [21] El nuevo INN uwildmat hace lo mismo. [22]FNM_PATHNAME.El algoritmo de Martin Richter es una excepción a este patrón, aunque el funcionamiento general es equivalente. En * recurre para aumentar cualquiera de los índices, siguiendo la formulación de programación dinámica del problema. La técnica "ABORT" también es aplicable. [9] En patrones típicos (como los probados por Cantatore) es más lento que las implementaciones de llamadas greedy. [10]
En general, es más fácil razonar sobre los algoritmos recursivos y, con la modificación ABORT, funcionan de manera aceptable en términos de complejidad en el peor de los casos. En cadenas sin *, tardan un tiempo lineal en coincidir con el tamaño de la cadena, ya que existe una relación fija de uno a uno.
Los siguientes son desarrollados por críticos de los algoritmos recursivos:
MATCH("da*da*da*", "daaadabadmanda")) [24]Lo siguiente no es:
MATCH("*?", "xx"))Las funciones iterativas anteriores implementan el retroceso guardando un conjunto antiguo de punteros de patrón/texto y volviendo a él si falla una coincidencia. Según Kurt, dado que solo se requiere una coincidencia exitosa, solo es necesario guardar un conjunto de estos. [17]
Además, el problema de la coincidencia de comodines se puede convertir en coincidencia de expresiones regulares utilizando un enfoque ingenuo de reemplazo de texto . Aunque los comparadores de expresiones regulares no recursivos como la construcción de Thompson se utilizan menos en la práctica debido a la falta de soporte de referencias inversas, la coincidencia de comodines en general no viene con un conjunto de características igualmente rico. (De hecho, muchos de los algoritmos anteriores solo tienen soporte para ?y *). La implementación de Russ Cox de Thompson NFA se puede modificar trivialmente para esto. [26] El algoritmo nrgrep basado en BDM de Gustavo Navarro proporciona una implementación más simplificada con énfasis en sufijos eficientes. [27] Véase también expresiones regulares § Implementaciones .