miércoles, 24 de febrero de 2016

Algoritmo para búsquedas con comodines (wildcards)

Recientemente andaba yo enredado en un proyecto personal de poca trascendencia pero que me obligó a hacer una implementación completa de un sistema de archivos FAT a bajo nivel.

La FAT es un sistema de archivos muy simple para los estándares de hoy y la implementación fue muy fácil y rápida.

Sin embargo, en el proyecto además se necesitaba agregar algunas funciones típicas de sistemas operativos de sabor Microsoft, entre ellas la habitual búsqueda por comodines o wildcard. Pues esto, que parece una tontería, me tuvo filosofando para su implementación más tiempo que casi el resto de la implementación.

Se me ocurrieron diferentes acercamientos al problema de interpretar una cadena cualquiera que usase el comodín asterisco (*) para sustituir una subcadena cualquiera y el interrogante (?) para sustituir cualquier carácter coincidente en esa posición. Pensé en aplicar mis oxidados conocimientos de autómatas y lenguajes, o también una simple rutina al estilo amateur a base de recorrer las cadenas con un bucle e ir contando caracteres e intentando cuadrarlo todo usando código spaghetti.

Pero finalmente opté por la implementación más sencilla y elegante, si bien no la más eficiente: convertir los viejos comodines de tipo DOS a expresiones regulares de las que hoy en día se usan para todo. Cualquier lenguaje de programación moderno permite el uso de regex cuyo parseo es transparente para el programador.



Para ello basta con buscar las equivalencias necesarias entre comodines DOS y expresiones regulares o regex:


FunciónWildcardRegex
Sustituye un carácter en la posición indicada?.
Sustituye una secuencia cualquiera de caracteres*.*
Separador de extensión.\.

Además, si se trata de una regex en un entorno POSIX, es probable que para que la coincidencia de la cadena buscada sea haga desde las posiciones indicadas de cada comodín comenzando por el primer carácter de la cadena (y no en cualquier lugar de la misma), haya que agregar el metacarácter ^ al comienzo de la expresión.

De esta forma, la conversión entre wildcards y regex puede verse ilustrada en los siguientes ejemplos:


DescripciónWildcardsRegex
Cualquier archivo con cualquier extensión*.*^.*\..*
Todos los archivos que comiencen por AA*.*^A.*\..*
Todos los archivos con extensión jpg que comiencen por pic y dos caracteres máspic??.jpg^pic..\.jpg

El código 

Para transformar los comodines en expresiones regulares hemos visto que basta cualquier tipo de sustitución simple, incluso la que hace un editor de texto con sus macros correspondientes. El lenguaje Perl tiene, como parte de su propia sintaxis, el manejo de expresiones regulares. También existen en Java, Javascript, c#, PHP y casi cualquiera que se precie.

No obstante, en mi ejemplo yo usaré lenguaje C ansi por ser un estándar y porque además era el lenguaje usado en mi proyecto.


#include <string.h>
#include <regex.h>

/*
*Esta función recorre el patrón basado en comodines y los sustituye por sus equivalencias regex
*/
char *wildcard_to_regex(char *pattern) {

    if (pattern) {
        int len = strlen(pattern);

        char *regstr = malloc(200);

        int r = 0;
        regstr[r++] = '^';

        for (int i = 0; i < len; i++) {

            switch (*(pattern + i)) {
                case '*':
                    regstr[r++] = '.';
                    regstr[r++] = '*';
                    break;
                case '?':
                    regstr[r++] = '.';
                    break;
                case '.':
                    regstr[r++] = '\\';
                    regstr[r++] = '.';
                    regstr[r++] = '*'; //ignoramos si hay más de un . seguido
                    break;
                default:
                    regstr[r++] = *(pattern + i);

            }
        }
        regstr[r] = '\0';

        return regstr;

    } else {

        return NULL;
    }

}
/*
*En esta función se comprueba si el nombre de archivo o cadena coincide con la expresión regex dada
*/
bool pattern_matches(char *filename, char *mask) {

    regex_t regex;
    regcomp(&regex, wildcard_to_regex(mask), REG_ICASE);

    if (!regexec(&regex, filename, 0, NULL, 0)) {
        return true;
    } else {
        return false;
    }
}

Ambas funciones se utilizarían para construir la expresión regular a partir de un patrón de búsqueda por comodines y para comprobar si una cadena dada (por ejemplo, un nombre de archivo) concuerda con dicha expresión regular:
void main (int argc, char *argv[])
{
    if (pattern_matches(argv[1], wilcard_to_regex("test*.*") )
    {
        // el archivo especificado en la línea de comandos
        // concuerda con la máscara "test*.*"

    } else {

        // el archivo no concuerda

    }

}