En mérito de su propuesta innovadora para abordar el problema de comprimir colecciones de texto altamente repetitivas, el artículo científico (paper) “On Stricter Reachable Repetitiveness Measures”, desarrollado por el estudiante de Doctorado en Computación, Cristián Urbina, y el profesor del DCC, Gonzalo Navarro, obtuvo el reconocimiento “Best Student Paper Award” en la 28th edition of the annual Symposium on String Processing and Information Retrieval – SPIRE 2021. Esta conferencia, aborda temas de procesamiento de cadenas, recuperación de información y bioinformática, entre otros, y se realizó del 4 al 6 de octubre pasado.

Para contextualizar el problema abordado, Cristián Urbina explica que otros autores han demostrado que los mecanismos que se utilizan en la actualidad para comprimir colecciones de textos altamente repetitivas, tienen limitaciones importantes que, en ciertos casos, no permiten comprimir tanto como se quisiera. Señala que en la investigación desarrollada con el profesor Navarro, proponen “capturar la idea de repetitividad en textos a un nivel más estructural, en vez de solo medir las copias explícitas que hay en el texto”.

El estudiante de Doctorado agrega que los aportes que realizan con este trabajo tienen que ver con proponer explotar la repetitividad estructural de las cadenas a la hora de comprimir, en vez de solo copias explícitas, y proponer nuevos mecanismos basados en estas ideas. “Probamos que estos funcionan bien en casos relevantes, donde los mecanismos del estado del arte no comprimen tan bien (en términos de espacio). Nuestros nuevos mecanismos incluso rompen las mejores cotas inferiores que teníamos actualmente para los esquemas basados en copias explícitas”, afirma.

En este sentido, destaca que el principal mérito de este trabajo y que lo llevó a ser reconocido con el “Best Student Paper Award” es que introduce un nuevo concepto que se puede explotar y estudiar a la hora de comprimir, y afirma: “Esto abre un montón de posibilidades para futuras investigaciones, que van desde desarrollar la teoría de los métodos que propusimos, plantear otros nuevos, implementaciones prácticas, etc. Lo principal es que los métodos basados en copias explícitas no pueden alcanzar las cotas inferiores teóricas que se tienen en la actualidad, así que para estudiar los límites de la compresibilidad, se hacía necesario explorar nuevas ideas. El concepto de repetitividad estructural que introdujimos permite volver a intentar aproximarse a estas cotas, o buscar otras que sean mejores”.

Revisa la presentación de “On Stricter Reachable Repetitiveness Measures en SPIRE 2021 en: https://pod.univ-lille.fr/video/21830-on-stricter-reachable-repetitivene...

--
Comunicaciones DCC