Con una investigación guiada por el profesor Gonzalo Navarro, académico del Departamento de Ciencias de la Computación (DCC), el investigador Cristian Urbina obtuvo el grado de Doctor en Computación por la Universidad de Chile, el más alto otorgado por nuestra casa de estudios.

Su tesis, titulada “A Study on Repetitiveness Measures for Strings”, se centra en el estudio de medidas de repetitividad en textos, tanto aquellas basadas en compresores como otras definidas desde una perspectiva combinatoria. Estas medidas permiten explorar límites teóricos y ofrecer garantías asintóticas sobre la compresibilidad de datos. “La cantidad de datos en el mundo ha crecido enormemente y almacenar estos datos explícitamente muchas veces no es una opción.  La compresión de texto trata de representar enormes colecciones de texto usando menos espacio. Luego tenemos las estructuras de datos compactas, que buscan ofrecernos funcionalidad (consultas) sin tener que descomprimir el texto, lo cual es otro lujo que muchas veces no nos podemos permitir”, señala Urbina.

Uno de los contextos donde estos desafíos se hacen evidentes es la bioinformática, donde las colecciones de texto son altamente repetitivas. Frente a esta realidad, los compresores tradicionales, que se basan en las frecuencias de los símbolos, resultan insuficientes. De ahí surge la necesidad de compresores especializados para datos repetitivos, y con ello, nuevas formas de medir cuán “compresible” es un texto bajo este paradigma.

La tesis de Urbina realiza contribuciones en tres líneas principales:

1) Explora diversas propiedades algorítmicas y combinatoriales de distintas medidas de repetitividad usadas en la práctica. “En específico, estudiamos la vulnerabilidad de medidas de repetitividad y compresores a pequeñas modificaciones en los textos. Idealmente, buscamos que las medidas de repetitividad no cambien mucho si se hacen pequeñas modificaciones, pues en el mundo real las colecciones de datos pueden cambiar en el tiempo”, comenta.

2) Se buscan formas novedosas de explotar la repetitividad como fuente de compresibilidad, diseñando nuevas representaciones comprimidas (y medidas de repetitividad asociadas) con buen desempeño teórico. Expresa que “la principal motivación de esto es romper con las limitaciones de métodos actuales y encontrar formas de diseñar compresores más poderosos para colecciones altamente repetitivas”.

3) Se generalizan medidas de repetitividad y algunas representaciones comprimidas usadas para textos corrientes, para funcionar en colecciones de datos “multidimensionales”. “Encontramos que algunas medidas que son útiles para textos corrientes dejan de serlo para datos multidimensionales, y, por otro lado, que nuestras representaciones de datos multidimensionales mejoran substancialmente algunas técnicas usadas en la práctica”, señala.

El viaje doctoral de Cristian Urbina

El camino al doctorado no estuvo exento de dificultades, desde el inicio cuando en medio de la pandemia por COVID-19 comenzó sus estudios de doctorado. “Más allá de las exigencias del programa como exámenes, artículos publicados, deadlines, etc., lo que realmente ha sido complicado para mí es comenzar a relacionarme más con otros investigadores: tratar de dejar de sentirme un estudiante, y más un colega”, confiesa.  También fue clave aprender a darse tiempos libres y “tratar de mantener un nivel de estrés sano, ser exigente conmigo mismo, pero a la vez no tan duro, si es que eso hace sentido”.

Durante su doctorado, presentó trabajos en conferencias internacionales como SPIRE 2021, SPIRE 2022, CPM 2023, LATIN 2024 y SPIRE 2024. En 2021 recibió el Best Student Paper Award por su artículo “On stricter reachable repetitiveness measures”. En total, ha publicado 8 artículos en conferencias y 3 en revistas científicas.

Además, realizó dos estadías de investigación en la Universidad de Palermo, Italia, donde fue supervisado por los profesores Marinella Sciortino y Gabriele Fici. Su trabajo fue financiado por ANID Doctorado Nacional 2021, CeBiB, NIC Chile, el DCC y la propia Universidad de Palermo.

Ya como Doctor, Cristian Urbina espera continuar su carrera en la investigación académica: “Mi prioridad es realizar un postdoctorado donde pueda seguir trabajando en algoritmos, estructuras de datos, combinatoria sobre cadenas de texto, o incluso bioinformática”. En el corto plazo, asistirá en agosto a MFCS 2025, donde presentará un nuevo artículo aceptado, y espera participar en SPIRE 2025, en septiembre, donde tiene otro trabajo en proceso de revisión.

--
Comunicaciones DCC