miércoles, 24 de febrero de 2016

Rating: 5 out of 5

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.