Comodines coincidentes

En informática , un algoritmo para la coincidencia de 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, el shell Bourne ^{[ 2 ]} o la línea de comandos de Microsoft Windows ^{[ 3 ]} o editores de texto o administradores de archivos, así como las interfaces de 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 de comodín p contra una cadena de entrada s . Realiza una coincidencia 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 han definido caracteres de escape.
• Comodines: ?coincide exactamente con una aparición de cualquier carácter. *coincide con un número arbitrario de apariciones (incluidas cero) de cualquier carácter.

Este artículo trata principalmente sobre la formulación del problema en el contexto de Windows, a menos que se indique lo contrario.

Los primeros algoritmos para la coincidencia de comodines a menudo recurrían a la recursión , pero esta técnica fue criticada por su rendimiento ^{[ 10 ]} y fiabilidad ^{[ 8 ]} . Los algoritmos no recursivos para la coincidencia de comodines han ganado popularidad a raíz de estas consideraciones.

Tanto en los algoritmos recursivos como en los no recursivos, las estrategias para realizar la búsqueda de patrones varían considerablemente, como se evidencia en los diversos ejemplos de algoritmos que se mencionan a continuación. Se ha demostrado que las técnicas de desarrollo de casos de prueba y optimización del rendimiento se aplican a ciertos algoritmos, en particular a los desarrollados por los críticos de los algoritmos recursivos.

La recursión generalmente ocurre al realizar coincidencias *cuando hay más sufijos con los que comparar. Esta es una forma de retroceso , que también utilizan algunos comparadores de expresiones regulares.

• Algoritmo wildmat de Rich Salz (sintaxis tipo sh) ^{[ 14 ]}
• Algoritmo de Filip ^{[ 15 ]} y algoritmo de Vignesh Murugesan ^{[ 16 ]}
• El 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):
  • fnmatch de la libc de BSD de Guido van Rossum , ^{[ 18 ]} también forma parte de la libc de Apple ^{[ 19 ]}
  • Glibc fnmatch ^{[ 20 ]}

La forma general de estos algoritmos es la misma. En la recursión, el algoritmo divide la entrada en subcadenas y considera que hay coincidencia cuando UNA de las subcadenas devuelve una coincidencia positiva. Para dowild("*X", "abcX"), llamaría de forma voraz a , dowild("X", "abcX")y . Suelen diferir en aspectos menos importantes, como la compatibilidad con características, y en factores más importantes, como optimizaciones menores pero muy efectivas. Algunas de ellas incluyen:dowild("X", "bcX")dowild("X", "cX")dowild("X", "X")

• The ABORT signal against over-recursion (Lars Mathiesen 1991). While it is correct to naively recurse by the entire rest of the strings (pattern and text) on * and making sure that ONE of the substrings return a positive match, the running time becomes exponential for rejecting a match with many * in the text. Lars Mathiesen changes the return to three classes, match, no-match, and ABORT (no match possible at all for asterisk recursion.) The ABORT value is returned when the text is consumed too early or when another asterisk match has failed, guaranteeing a linear performance with respect to the number of asterisks. (The overall complexity is additionally quadratic to the number of characters left to match.)^[14] Git/Rsync's wildmatch ABORT also covers invalid inputs.^[21] The new INN uwildmat does the same.^[22]
• Asterisk advancement in recursion. This wildmatch tweak is relatively more minor. It applies to when the recursion wants to match "*X" on "abcX": when an asterisk is followed by a literal like "X", it is obvious that only the last comparison with equal lengths would have a chance of producing a match.^[21] This is seen earlier in uwildmat in 2000^[22] and more implicitly in van Rossum's fnmatch for FNM_PATHNAME.

Martin Richter's algorithm is an exception to this pattern, although the overall operation is equivalent. On * it recurses into increasing either of the indexes, following the dynamic programming formulation of the problem. The "ABORT" technique is applicable to it as well.^[9] On typical patterns (as tested by Cantatore) it is slower than the greedy-call implementations.^[10]

The recursive algorithms are in general easier to reason about, and with the ABORT modification they perform acceptably in terms of worst-case complexity. On strings without * they take linear-to-string-size time to match since there is a fixed one-to-one relation.

The following are developed by critics of the recursive algorithms:

• Kirk J. Krauss's wildcard-matching algorithm, used by IBM^[8][23]
• Alessandro Cantatore's collection of wildcard matching algorithms^[10]
• Dogan Kurt's iterative matcher and slower NFA matcher.^[17]
• Siler's incorrect algorithm (fails MATCH("da*da*da*", "daaadabadmanda"))^[24]

The following is not:

• El algoritmo incorrecto de Jack Handy ^{[ 25 ]} (falla MATCH("*?", "xx"))

Las funciones iterativas anteriores implementan el retroceso guardando un conjunto anterior de punteros de patrón/texto y volviendo a él si no hay coincidencia. Según Kurt, dado que solo se requiere una coincidencia exitosa, solo es necesario guardar un conjunto de este tipo. ^{[ 17 ]}

Además, el problema de la coincidencia de comodines se puede convertir en una 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 retroreferencia, 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 del NFA de Thompson se puede modificar trivialmente para tal. ^{[ 26 ]} El algoritmo nrgrep basado en BDM de Gustavo Navarro proporciona una implementación más optimizada con énfasis en sufijos eficientes. ^{[ 27 ]} Véase también expresiones regulares §  Implementaciones .

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