Búsqueda Parametrizada para la Detección de Código Duplicado

Publicado: el 31 marzo, 2017 por AdminKonrad / Konrad Lorenz

Para nadie es un secreto que un software al que no se le hace mantenimiento se vuelve obsoleto con el tiempo. Por eso, el mantenimiento del software es un área muy importante de la ingeniería de software, pero el código duplicado es un flagelo que dificulta dicho mantenimiento.

Muchas veces, el código duplicado se introduce cuando un programador va a arreglar un bug o a agregar una nueva funcionalidad parecida a otra existente. En lugar de hacer un análisis profundo para hacer uso de patrones y buenas prácticas de programación, como el uso de funciones para la reutilización de código, los desarrolladores prefieren hacer nuevas copias de código que funciona para evitar la introducción de nuevos bugs en el sistema y dañar otros módulos que ya estaban funcionando bien [1].  Esto lo hacen, en especial, cuando lo que están editando lo hizo otro programador.

Para tal edición, copian el código que ya funciona en un editor de texto, cambian los nombres de algunas variables y lo pegan en otra sección del programa. Con el tiempo, la cantidad de código duplicado aumenta y el código se vuelve más extenso y más difícil de mantener. Por ejemplo, cuando se arregla un error en una sección del código, esta reparación no se replica automáticamente en las copias de dicha sección. Es más, dichas copias pueden ser difíciles de identificar en especial en los sistemas grandes de software en el que trabajan muchos desarrolladores.

Estudios en un software de más de un millón de líneas muestran que más del 22% del código es repetido [1]. Esta cantidad de código se podría reducir usando técnicas de programación más adecuadas como el uso de funciones, procedimientos y patrones de diseño. Una reducción así haría que el código fuera más simple y más fácil de mantener.

Con el fin de facilitar el hallazgo del código duplicado, Brenda Baker definió la búsqueda parametrizada [2]. En dicha búsqueda, el código es visto como una secuencia de tokens que corresponden a variables, operadores, palabras reservadas, etc. En particular, ella diferencia los tokens en dos grupos: los constantes y los parámetros. Los primeros corresponden a los tokens que permanecen iguales en dos copias de código: palabras reservadas, operadores y literales. Los parámetros corresponden a elementos que pueden ser identificados con nombres distintos: los nombres de las variables y de las constantes.

Basada en estas nociones, Baker definió las cadenas parametrizadas como cadenas de texto formadas por el alfabeto constante y el alfabeto de parámetros. Dos cadenas del mismo tamaño hacen coincidencia parametrizada si existe una biyección que mapee los símbolos de una cadena en los símbolos de la otra de manera que los símbolos del alfabeto constante tengan un mapeo identidad. Por ejemplo, si el alfabeto constante está formado por {a,b} y el alfabeto de parámetros es {X,Y,Z}, las cadenas XZabaYXYbZ y ZYabaXZXbY hacen una coincidencia parametrizada bajo el mapeo (a,b,X,Y,Z)→(a,b,Z,X,Y).

Visto desde el punto de vista de código, una coincidencia parametrizada se ilustra en los siguientes fragmentos.

Nótese que estos fragmentos de código son idénticos, excepto por un intercambio sistemático de los parámetros. En este caso, los parámetros son las variables x e y, las cuales son mapeadas a las variables a y b, respectivamente.

Entonces, la idea de la búsqueda parametrizada, dado un patrón y un texto, es encontrar las subcadenas del texto que hagan coincidencia parametrizada con el patrón, de esta manera se pueden encontrar todas las copias en el código del sistema de software del fragmento representado por el patrón.

Así, la búsqueda parametrizada adquiere gran importancia en la reducción de código duplicado y en el mantenimiento de software. Por esta razón, se han buscado soluciones eficientes para el problema, como las presentadas en [3,4]. También, el problema se ha extendido a la búsqueda de patrones múltiples [5], búsqueda aproximada [6,7,8] y búsqueda en dos dimensiones [9]. Los trabajos más recientes se enfocan a la búsqueda parametrizada aplicada a la solución del isomorfismo de grafos [10] y a la búsqueda en textos comprimidos [11].

Una gran cantidad de trabajo se ha desarrollado en torno al tema debido a su importancia en el mantenimiento de software, procesamiento de imágenes y bioinformática. Una guía más detallada de las contribuciones en esta área es presentada en [12]. A pesar de que el problema se propuso hace más de dos décadas, la búsqueda parametrizada continúa siendo ampliamente estudiada.

Por Juan Mendivelso, PhD

Bibliografía

1. Baker, B. S. (1993). A program for identifying duplicated code. Computing Science and Statistics, 49-49.
2. Baker, B. S. (1993, June). A theory of parameterized pattern matching: algorithms and applications. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (pp. 71-80).
3. Amir, A., Farach, M., & Muthukrishnan, S. (1994). Alphabet dependence in parameterized matching. Information Processing Letters, 49(3), 111-115.
4. Baker, B. S. (1995, January). Parameterized Pattern Matching by Boyer-Moore-Type Algorithms. In SODA (Vol. 95, pp. 541-550).
5. Idury, R. M., & Schäffer, A. A. (1994, June). Multiple matching of parameterized patterns. In Annual Symposium on Combinatorial Pattern Matching (pp. 226-239). Springer Berlin Heidelberg.
6. Lee, I., Mendivelso, J., & Pinzón, Y. J. (2008, November). δγ–parameterized matching. In International Symposium on String Processing and Information Retrieval (pp. 236-248). Springer Berlin Heidelberg.
7. Hazay, C., Lewenstein, M., & Sokol, D. (2007). Approximate parameterized matching. ACM Transactions on Algorithms (TALG), 3(3), 29.
8. Apostolico, A., Erdős, P. L., & Lewenstein, M. (2007). Parameterized matching with mismatches. Journal of Discrete Algorithms, 5(1), 135-140.
9. Hazay, C., Lewenstein, M., & Tsur, D. (2005, June). Two dimensional parameterized matching. In Annual Symposium on Combinatorial Pattern Matching (pp. 266-279). Springer Berlin Heidelberg.
10. Mendivelso, J., Kim, S., Elnikety, S., He, Y., Hwang, S. W., & Pinzón, Y. (2013, October). Solving graph isomorphism using parameterized matching. In International Symposium on String Processing and Information Retrieval (pp. 230-242). Springer International Publishing.
11. Beal, R., & Adjeroh, D. (2016). Compressed parameterized pattern matching. Theoretical Computer Science, 609, 129-142.
12. Mendivelso, J., & Pinzón, Y. J. (2015, August). Parameterized Matching: Solutions and Extensions. In Stringology (pp. 118-131).