El estudiante del Doctorado en Computación de la Universidad de Chile, Alejandro Pacheco, fue galardonado con el Best Student Paper Award en la 36ª edición del Symposium on Combinatorial Pattern Matching (CPM 2025), realizado entre el 17 y 19 de junio en Milán, Italia. El premio reconoce los aportes científicos de su investigación titulada “Counting on General Run-Length Grammars", desarrollada en conjunto con el académico del Departamento de Ciencias de la Computación (DCC), Gonzalo Navarro, quien además es su profesor guía.

El trabajo resuelve un problema abierto desde 2020 en el área de compresión de datos, específicamente sobre un tipo particular de gramáticas utilizadas para representar textos comprimidos.

Para explicar el problema, Alejandro comenta: “Imagínate que tienes una biblioteca gigante con millones de libros, pero todos están comprimidos en cajas especiales para ahorrar espacio. Cuando quieres saber cuántas veces aparece una palabra específica en todos los libros, normalmente tendrías que descomprimir cada caja, buscar la palabra, y volver a comprimir todo - un proceso muy lento.  Nuestro trabajo resuelve este problema para un tipo particular de compresión llamada Gramáticas Libres de Contexto con Reglas de Tipo Run-Length (RLCFGs). Desarrollamos el primer algoritmo que puede contar cuántas veces aparece un patrón en textos comprimidos sin necesidad de descomprimirlos completamente. Es como poder contar palabras directamente en las cajas comprimidas”.

Este nuevo algoritmo permite calcular frecuencias de palabras y medidas de relevancia de manera eficiente, siendo especialmente útil para datos muy repetitivos como secuencias de ADN, logs de sistemas, o repositorios de código, donde la compresión es muy efectiva. “Nuestro resultado establece equivalencia teórica entre tipos de gramáticas para conteo, con implicaciones importantes para futuras herramientas de compresión”.

Uno de los principales desafíos fue la limitada aplicabilidad de los métodos existentes, que sólo funcionaban con gramáticas muy restringidas. “Tuvimos que crear una clasificación completamente nueva de reglas gramaticales y desarrollar diferentes estrategias para cada tipo, especialmente para manejar patrones con estructura periódica”. 

El artículo fue presentado en una de las conferencias más relevantes en el área de búsqueda de patrones y algoritmos sobre texto. Se enfoca en aspectos teóricos y prácticos de búsqueda eficiente de patrones en estructuras de datos como strings, árboles y grafos. “Es una conferencia de alto nivel y muy competitiva en ciencias de la computación. Su relevancia radica en las aplicaciones directas en bioinformática, minería de datos, recuperación de información y motores de búsqueda”, comenta. 

Sobre el reconocimiento recibido, añade: “Significa muchísimo porque válida el trabajo y da credibilidad internacional. Para un doctorando, este reconocimiento abre puertas y es también mérito del excelente trabajo del profesor Gonzalo Navarro”.

Finalmente, sobre su experiencia presentando el trabajo en el simposio, confiesa: “¡Fue increíble, pero también muy estresante! Presentar frente a investigadores de renombre, cuyos trabajos he estudiado y citado, fue un gran desafío. Pero hubo un ambiente muy acogedor que ayudó bastante. Lo más gratificante fue el reconocimiento inmediato al problema que resolvimos y las discusiones técnicas que surgieron con colegas de distintas partes del mundo”.

--
Comunicaciones DCC