Comodines coincidentes

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]}

• No se definen caracteres de escape
• Comodines: ?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:

${\displaystyle {\begin{aligned}m_{00}&=(p_{0}=t_{0})\\m_{0j}&=(p_{j-1}={\text{'*'}})\land m_{0,j-1}\\m_{i0}&={\text{falso}}\\m_{ij}&={\begin{cases}m_{i-1,j-1}&{\text{para}}\;p_{i-1}=t_{j-1}\lor p_{i-1}={\text{'?'}}\\m_{i,j-1}\lor m_{i-1,j}&{\text{para}}\;p_{i-1}={\text{'*'}}\\{\text{falso}}&{\text{para}}\;p_{i-1}\neq t_{j-1}\end{casos}}&&\quad {\text{para}}\;1\leq i\leq |p|,1\leq j\leq |t|.\end{alineado}}}$

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:

• Coincidencia de patrones sin importar si hay espacios o no, una búsqueda de cadena no anclada con solo el equivalente de lo ?definido. ^{[11] [12]}
• Coincidencia de patrones con comodines, una búsqueda de cadena no anclada con el equivalente de ambos comodines definidos. Tiene un tiempo de ejecución exponencial a menos que se proporcione un límite de longitud en la variante de coincidencia de patrones con comodines flexibles. ^[13]

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.

• Algoritmo wildmat de Rich Salz (sintaxis tipo sh) ^[14]
• Algoritmo de Filip ^[15] y algoritmo de Vignesh Murugesan ^[16]
• Algoritmo de Martin Richter ^[9] (idéntico a Snippets y relacionado con el algoritmo 7-zip) ^[17]
• Implementaciones de la biblioteca C fnmatch[...] (admite conjuntos de caracteres multibyte):
  • BSD libc fnmatch de Guido van Rossum , ^[18] también parte de Apple libc ^[19]
  • Fnmatch de Glibc ^[20]

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:

• La señal ABORT contra la recursión excesiva (Lars Mathiesen 1991). Si bien es correcto realizar una recursión ingenua por todo el resto de las cadenas (patrón y texto) *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]
• Avance de Asterisk en recursión. Este ajuste de wildmatch es relativamente menor. Se aplica cuando la recursión quiere hacer coincidir "*X" con "abcX": cuando un asterisco va seguido de un literal como "X", es obvio que solo la última comparación con longitudes iguales tendría una posibilidad de producir una coincidencia. ^[21] Esto se vio anteriormente en uwildmat en 2000 ^[22] y de manera más implícita en fnmatch de van Rossum para 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:

• Algoritmo de coincidencia de comodines de Kirk J. Krauss , utilizado por IBM ^{[8] [23]}
• Colección de algoritmos de comparación de comodines de Alessandro Cantatore ^[10]
• Comparador iterativo de Dogan Kurt y comparador NFA más lento. ^[17]
• Algoritmo incorrecto de Siler (falla MATCH("da*da*da*", "daaadabadmanda")) ^[24]

Lo siguiente no es:

• Algoritmo incorrecto de Jack Handy ^[25] (falla 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 .

• Coincidencia de patrones
• Cálculo de patrones
• Glob (programación)
• Carácter comodín
• Lista de algoritmos