La U. de Chile anunció que la CPM reconoció a Alejandro Pacheco —investigador del Centro de Biotecnología y Bioingeniería (CeBiB) y estudiante de doctorado en Ciencias de la Computación en la misma universidad— por resolver un problema abierto desde 2020 en el área de compresión de datos y estructuras de datos.
Su trabajo permite realizar análisis directamente sobre datos comprimidos, sin necesidad de descomprimirlos, lo que representa un avance relevante para áreas como la bioinformática y el procesamiento de información a gran escala.
El reconocimiento se entregó durante la conferencia internacional Combinatorial Pattern Matching (CPM 2025), uno de los encuentros más importantes en el área de análisis de patrones y estructuras de datos, realizada en junio en Milán, Italia.
El paper premiado se titula “Counting on General Run-Length Grammars”, propone un algoritmo capaz de contar patrones en textos comprimidos sin necesidad de descomprimirlos.
¿Por qué fue premiado su avance en compresión de datos en CPM 2025?
El premio reconoció una solución concreta a un problema que seguía abierto desde hace 5 años. El trabajo presenta el primer algoritmo que permite buscar y contar patrones directamente en textos comprimidos, sin necesidad de descomprimirlos.
Esta capacidad representa un cambio importante para el análisis de información a gran escala. Permite trabajar con colecciones genómicas o archivos de texto extensos de forma mucho más eficiente, reduciendo tiempos de procesamiento y uso de recursos computacionales, así lo detalló Gonzalo Navarro, uno de los autores del paper:
“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”.
Gonzalo Navarro, investigador principal del CeBiB
Alejandro Pacheco desarrolló el paper junto a Gonzalo Navarro, donde proponen una solución a un problema teórico planteado hace cinco años. Hasta ahora, no existía un método eficiente para contar patrones sobre este tipo específico de compresión basada en gramáticas.
“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”.
Alejandro Pacheco, investigador del CeBiB y estudiante de doctorado en la Universidad de Chile
El algoritmo identifica patrones directamente en estructuras comprimidas, lo que representa una de sus principales ventajas. Para ilustrar cómo funciona, la siguiente imagen muestra un árbol gramatical junto a una grilla de búsqueda que permite localizar un patrón sin descomprimir el texto original.
Además del aporte científico, el reconocimiento también destaca la proyección internacional del investigador y el impacto de este tipo de estudios para Chile. En esa línea, Gonzalo Navarro valoró el premio recibido en CPM 2025:
“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”.
Gonzalo Navarro, investigador principal del CeBiB.
Los Fondos Basales para Centros Científicos y Tecnológicos de Excelencia FB0001 de Mideplan, el proyecto Fondecyt 1-230755 y el programa Becas Chile de Doctorado de ANID financiaron este trabajo.
