Estudiante del DCC obtiene primer premio del Concurso CLEI

Image preview

Sebastián Kreft

Image preview

Gonzalo Navarro


Compartir

 

Sebastián Kreft resultó ganador del concurso Latinoamericano de Tesis de Maestría  organizado por CLEI, con una investigación que busca una nueva forma de indexar colecciones de texto muy repetitivas.

 

Sebastián Kreft, con “auto-_indice de texto basado en lz77”,  tesis de Magíster, realizada en el Departamento de Ciencias de la Computación, obtuvo el primer lugar en el concurso Latinoamericano de Tesis de Maestría (CLTM), evento anual dentro del Congreso, organizado por el Centro Latinoamericano de Estudios en Informática (CLEI), y cuyo premio involucra la presentación de la investigación en la XXXVII Conferencia Latinoamericana de Informática que se realizará en Quito, Ecuador, entre el 10 y el 14 de Octubre, además de la publicación en las actas de dicho evento.

 

El Concurso -donde pueden participar estudiantes que se hayan graduado en programas de Maestría de Universidades Iberoamericanas- tiene como objetivo difundir y transmitir el trabajo de estudiantes latinoamericanos que hayan terminado sus tesis de maestría en informática recientemente.

 

La investigación realizada por Sebastián Kreft trata de una forma de indexar colecciones de texto muy repetitivas (documentos versionados, bases de datos genómicas, repositorios de software, publicaciones periódicas), de manera de aprovechar la repetitividad para que el índice además comprima la colección. “Por ejemplo, conseguimos tasas de compresión de uno en mil para artículos versionados de Wikipedia, y de uno en cien para colecciones genéticas”, explicó el estudiante del DCC.
 

El trabajo presenta, en primer lugar, un nuevo método de compresión basado en LZ77 llamado LZ-End. “Este método tiene la particularidad que permite extraer eficientemente una porción del texto original a partir del texto comprimido sin necesidad de descomprimir todo el texto, logrando una compresión muy cercana a lo obtenido con LZ77”, expresó Sebastián Kreft.

 

La segunda parte del trabajo, consistió en crear un auto índice basado en LZ77/LZ-end, orientado a textos repetitivos. Según explica, un auto índice es una estructura de datos que almacena un texto de manera comprimida y a su vez permite buscar patrones en el texto. “Una metáfora que siempre uso es como un archivo zip, que tiene la capacidad de poder buscar palabras en los archivos sin necesidad de “abrirlo”. Ejemplo de estos textos son colecciones de secuencias de ADN, colecciones de códigos fuente o los cambios hechos a un artículo de Wikipedia. El principal resultado es que esta nueva estructura supera al mejor índice existente, el RLCSA, tanto en tiempo como en espacio”.

 

A su vez, este trabajo es la continuidad de una investigación realizada por el académico del DCC, Gonzalo Navarro, quien señaló que “había diseñado un par de años antes las estructuras de datos para conseguir aprovechar la repetitividad, basadas en la compresión Lempel-Ziv 1977 (LZ77). Sebastián es un alumno con mucha iniciativa, implementó y probó mis ideas, seleccionó las que funcionaban mejor, inventó otras cuando ninguna funcionaba e, incluso, resolvió algunos problemas que ni siquiera había planteado, como por ejemplo un compresor mejor que el LZ77 para este caso”, resaltó.
 

Para Sebastián, el académico Gonzalo Navarro cumplió un rol fundamental en la investigación: “Siempre estuvo dispuesto a resolver mis dudas y discutir nuevas soluciones. Además me motivó a presentar los resultados en distintas conferencias, lo que ha demostrado que la tesis es un trabajo de calidad. Sin duda el profesor fue un gran apoyo”, destacó.

 

En tanto Gonzalo Navarro comentó que el premio es una distinción muy importante para el DCC. “Competimos con universidades muy buenas de toda Latinoamérica, con programas de Magíster muy fuertes, con muchísimos alumnos. Las otras veces que nos habíamos ganado el primer puesto fueron 1996 y 2008. Desde entonces nos hemos ganado el segundo premio dos veces (2003 y 2006) y otros menores”. Agregó a su vez: “No todos los profesores del DCC conocen este premio y estoy seguro de que varios de sus alumnos podrían también obtenerlo”, enfatizó.

 

Finalizando el estudiante se refirió al premio como una gran sorpresa. “Por motivos laborales no tuve el tiempo que me hubiese gustado dedicarle al resumen e incluso pensé en no enviar mi tesis, pero el resultado obtenido me llena de alegría y orgullo. Para mi es importante saber que el trabajo de dos años sea relevante para la comunidad”, concluyó.

 

--

Comunicaciones DCC