Doctorando chileno resuelve problema abierto en compresión de datos y recibe premio internacional

El reconocimiento destacó el desarrollo de un algoritmo que permite analizar grandes volúmenes de datos comprimidos sin necesidad de descompresión, resolviendo un problema abierto desde 2020 en el área de estructuras de datos.

Alejandro Pacheco, investigador del Centro de Biotecnología y Bioingeniería (CeBiB) y estudiante de doctorado del Departamento de Ciencias de la Computación de la Universidad de Chile, fue distinguido con el Best Student Paper Award en la prestigiosa conferencia CPM 2025 – 36th Annual Symposium on Combinatorial Pattern Matching, realizada entre el 17 y 19 de junio en Milán, Italia.

El premio fue otorgado por su trabajo titulado “Counting on General Run-Length Grammars”, desarrollado con la guía del académico e investigador principal del CeBiB, Gonzalo Navarro. El paper propone una innovadora estructura de datos que permite contar ocurrencias de patrones en textos comprimidos sin necesidad de descomprimirlos, lo que representa un avance importante para el procesamiento eficiente de grandes volúmenes de información, como secuencias de ADN o archivos de texto masivos.

Según lo señalado en una nota publicada por el Departamento de Ciencias de la Computación de la Universidad de Chile (ver aquí), Pacheco explica el desafío abordado:

“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”.

Esta es la primera solución a un problema abierto planteado por Christiansen et al. en 2020, en un artículo publicado en la revista especializada ACM Transactions on Algorithms (TALG). En esa publicación, los autores —expertos en estructuras de datos y compresión desde instituciones como la Universidad Técnica de Dinamarca— dejaron abierta la posibilidad de desarrollar un algoritmo eficiente para contar patrones en textos comprimidos mediante gramáticas de tipo Run-Length. El trabajo de Pacheco y Navarro no solo resuelve ese desafío teórico, sino que además presenta una aplicación práctica que demuestra su utilidad en escenarios reales de análisis de datos comprimidos.

“Este trabajo contribuye a la línea de investigación de Bioinformática en el 
CeBiB, que busca manejar grandes colecciones muy repetitivas, como colecciones de genomas, usando mucho menos espacio que su tamaño original, y adicionalmente poder realizar consultas y análisis sobre estos datos sin nunca descomprimirlos. Una RLCFG puede representar una colección genómica en 10 a 100 veces menos que su espacio original, permitiendo así manipularlas en computadores mucho más accesibles, transferirlas en mucho menos tiempo, y adicionalmente responder preguntas de interés bioinformático, explicó Gonzalo Navarro, investigador principal y de CeBiB. "Con nuestro trabajo, se pueden ahora hacer preguntas de análisis estadístico sobre esas colecciones, como por ejemplo la frecuencia (y por lo tanto la relevancia) que tienen ciertos motifs de interés en la colección, todo esto directamente sobre el formato altamente comprimido”, agregó.

En cuanto al impacto del reconocimiento, Navarro destaco: “Este premio es muy importante para la futura carrera de un estudiante, pues le da visibilidad internacional a él y a su trabajo. Por eso es una gran noticia para nosotros, para nuestro programa de doctorado, y para el CeBiB, que permite sustentar este tipo de investigación”.

La conferencia CPM es uno de los encuentros científicos más relevantes a nivel mundial en el ámbito del análisis de patrones y algoritmos sobre cadenas, reuniendo cada año a especialistas en computación teórica y aplicada. El reconocimiento a Pacheco subraya la calidad de la investigación chilena en este competitivo campo científico.

Este trabajo fue financiado por los Fondos Basales para Centros Científicos y Tecnológicos de Excelencia FB0001 de Mideplan (Chile) y el proyecto Fondecyt 1-230755. Además, Alejandro Pacheco recibió apoyo a través del programa Becas Chile de Doctorado de la Agencia Nacional de Investigación y Desarrollo (ANID).

Consulta el artículo completo en las actas de la conferencia:

LIPIcs, Volumen 331 – 36º Simposio Anual sobre Coincidencia de Patrones Combinatorios (CPM 2025);  Descargar aquí