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, el shell Bourne [2] o la línea de comandos de Microsoft Windows [3] o el editor de texto o 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]
El problema
Un comparador de comodines prueba un patrón de comodín p con una cadena de entrada s . Realiza una coincidencia anclada , 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 soportada por el tiempo de ejecución nativo de C: [7] [8]
- No se definen caracteres de escape
- Comodines:
?
coincide exactamente con una aparición de cualquier carácter.*
coincide con muchas (incluidas cero) apariciones arbitrarias de cualquier carácter.
Este artículo analiza principalmente la formulación de Windows del problema, a menos que se indique lo contrario.
Definición
Expresado en índices de base cero, el problema de coincidencia de comodines se puede definir de forma recursiva 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 encuentran en la colección de Cantatore. [9] [10] Esta descripción es similar a la distancia de Levenshtein .
Problemas relacionados
Los problemas directamente relacionados en ciencias de la computación incluyen:
- Coincidencia de patrones con no importa o huecos, una búsqueda de cadena no anclada con solo el equivalente de
?
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 coincidencia de patrones con la variante de comodines flexibles. [13]
Historia
Los primeros algoritmos para hacer coincidir comodines a menudo se basaban en la recursividad , pero la técnica fue criticada por consideraciones de rendimiento [10] y confiabilidad [8] . Los algoritmos no recursivos para hacer coincidir 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 coincidencia 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 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.
Algoritmos recursivos
La recursividad generalmente ocurre al hacer coincidir *
cuando hay más sufijos con los que hacer coincidir. Esta es una forma de retroceso , también realizada por algunos comparadores de expresiones regulares.
- Rich Salz ' wildmat algoritmo (sh-como sintaxis) [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 fnmatch de la biblioteca C (soportes
[...]
y juegos de caracteres multibyte):- BSD libc fnmatch de Guido van Rossum , [18] también forma parte de Apple libc [19]
- Fnmatch Glibc [20]
La forma general de estos algoritmos es la misma. En la recursividad, el algoritmo divide la entrada en subcadenas y considera que ha ocurrido una coincidencia cuando UNA de las subcadenas devuelve una coincidencia positiva. Para dowild("*X", "abcX")
, sería llamar con avidez dowild("X", "abcX")
, dowild("X", "bcX")
, dowild("X", "cX")
y dowild("X", "X")
. Por lo general, se diferencian por aspectos menos importantes, como la compatibilidad con funciones, y por factores más importantes, como optimizaciones menores pero altamente efectivas. Algunos de ellos incluyen:
- La señal ABORT contra la recursividad excesiva (Lars Mathiesen 1991). Si bien es correcto recurrir ingenuamente al 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, coincidencia, no coincidencia y ABORT (no hay coincidencia posible para la recursividad de asterisco). El valor ABORT se devuelve cuando el texto se consume demasiado pronto o cuando falla otra coincidencia de asterisco, lo que garantiza rendimiento lineal con respecto al número de asteriscos. (La complejidad general es adicionalmente cuadrática al número de caracteres que quedan por igualar). [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 asterisco en recursividad. Este ajuste de wildmatch es relativamente menor. Se aplica cuando la recursividad quiere hacer coincidir "* X" en "abcX": cuando un asterisco va seguido de un literal como "X", es obvio que solo la última comparación con longitudes iguales tendría la posibilidad de producir una coincidencia . [21] Esto se ve anteriormente en uwildmat en 2000 [22] y más implícitamente en fnmatch for de van Rossum
FNM_PATHNAME
.
El algoritmo de Martin Richter es una excepción a este patrón, aunque el funcionamiento general es equivalente. En * recurre al aumento de cualquiera de los índices, siguiendo la formulación de programación dinámica del problema. La técnica "ABORT" también se le aplica. [9] En patrones típicos (según lo probado por Cantatore) es más lento que las implementaciones de llamadas codiciosas. [10]
En general, los algoritmos recursivos son más fáciles de razonar y, con la modificación ABORT, funcionan de manera aceptable en términos de complejidad en el peor de los casos. En cadenas sin *, necesitan un tiempo de lineal a tamaño de cadena para coincidir, ya que hay una relación fija de uno a uno.
Algoritmos no recursivos
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 coincidencia de comodines de Alessandro Cantatore [10]
- El emparejador iterativo de Dogan Kurt y el emparejador más lento de la NFA. [17]
- El algoritmo incorrecto de Siler (falla
MATCH("da*da*da*", "daaadabadmanda")
) [24]
Lo siguiente no es:
- El algoritmo incorrecto de Jack Handy [25] (falla
MATCH("*?", "xx")
)
Las funciones iterativas anteriores implementan el retroceso al guardar un conjunto antiguo de punteros de patrón / texto y volver a él si falla una coincidencia. Según Kurt, dado que solo se requiere una coincidencia exitosa, solo se debe guardar uno de esos conjuntos. [17]
Además, el problema de la coincidencia de comodines se puede convertir en una coincidencia de expresiones regulares utilizando un enfoque de reemplazo de texto ingenuo . Aunque los comparadores de expresiones regulares no recursivas, como la construcción de Thompson, se utilizan menos en la práctica debido a la falta de compatibilidad con 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 puede modificarse trivialmente para tal. [26] El algoritmo nrgrep basado en BDM de Gustavo Navarro proporciona una implementación más simplificada con énfasis en sufijos eficientes. [27] Véanse también las implementaciones de § expresiones regulares .
Ver también
- La coincidencia de patrones
- Cálculo de patrones
- Glob (programación)
- Carácter comodín
- Lista de algoritmos
Referencias
- ^ "Caracteres comodín" . ScienceDirect . 2018.
- ^ Quigley, Ellie (2005). Inicio rápido de programación de shell de UNIX . InformIT.com.
- ^ "Caracteres comodín de MS-DOS y Windows" . Biblioteca de Microsoft Developer Network .
- ^ "Apache Lucene - Sintaxis del analizador de consultas" . Documentación de Apache Lucene 2.9.4. 2006.
- ^ "Comodines SQL" . W3Schools . 2018.
- ^ Goyvaerts, enero (2018). "Bienvenido a Regular-Expressions.info" . RegularExpressions.info.
- ^ "Expansión de comodines" . docs.microsoft.com .
- ^ a b c Krauss, Kirk (2008). "Coincidencia de comodines: un algoritmo" . Diario del Dr. Dobb .
- ^ a b c Deadlock (2015). "Algoritmo recursivo de coincidencia de comodines C ++" . Desbordamiento de pila .
- ^ a b c d Cantatore, Alessandro (2003). "Algoritmos de coincidencia de comodines" .
- ^ Iliopoulos, Costas S .; Rahman, M. Sohel (2007). "Algoritmos de coincidencia de patrones con Don't Cares" (PDF) . SOFSEM 2007: Teoría y Práctica de la Informática, 33ª Conferencia sobre Tendencias Actuales en Teoría y Práctica de la Informática . Harrachov, República Checa. Archivado desde el original (PDF) el 17 de diciembre de 2019.
- ^ Clifford, Peter; Clifford, Raphaël (enero de 2007). "Coincidencia de comodines determinista simple". Cartas de procesamiento de información . 101 (2): 53–54. doi : 10.1016 / j.ipl.2006.08.002 .
- ^ Wu, Xindong; Qiang, Ji-Peng; Xie, Fei (12 de septiembre de 2014). "Coincidencia de patrones con comodines flexibles". Revista de Ciencias y Tecnología de la Computación . 29 (5): 740–750. doi : 10.1007 / s11390-014-1464-3 .
- ^ a b Salz, Rich (1991). "wildmat.c" . GitHub .
- ^ Filip (2014). "Comparar cadenas con comodines" . Desbordamiento de pila .
- ^ Murugesan, Vignesh (2014). "Algoritmo WildCard Matching" .
- ^ a b c Kurt, Dogan. "Métodos de coincidencia de comodines" .
- ^ van Rossum, Guido (20 de noviembre de 2019). "freebsd / lib / libc / gen / fnmatch.c" . Consultado el 21 de noviembre de 2019 .
- ^ "fnmatch.c" . opensource.apple.com. 1999.
- ^ "fnmatch_internal.c" . Espejos de Beren Minor. 21 de noviembre de 2019.
- ^ a b "git / git: wildmatch.c" . GitHub . 2020-01-20.
- ^ a b "uwildmat.c en el tronco / lib - INN" . inn.eyrie.org . Consultado el 27 de noviembre de 2019 .
- ^ Krauss, Kirk (2018). "Coincidencia de comodines: un algoritmo mejorado para Big Data" . Desarrollar para el rendimiento.
- ^ Siler (2013). "Soluciones recursivas para la coincidencia de patrones glob" . Desbordamiento de pila .
- ^ Handy, Jack (2005). "Comparación de cadenas comodín (globbing}" . Proyecto de código .
- ^ Cox, Ross. "La coincidencia de expresiones regulares puede ser simple y rápida" .
- ^ Navarro, Gonzalo (10 de noviembre de 2001). "NR ‐ grep: una herramienta de coincidencia de patrones rápida y flexible" (PDF) . Software: práctica y experiencia . 31 (13): 1265-1312. doi : 10.1002 / spe.411 .