31jul2026
15:00 Defesa de Mestrado Sala 85 do IC2
Tema
Compressão gramatical em memória externa baseada em ordenação induzida de sufixos
Aluno
Victor Racso Galvan Oyola
Orientador / Docente
Guilherme Pimentel Telles - Coorientador: Daniel Saad Nogueira Nunes
Breve resumo
A rápida expansão de conjuntos de dados em áreas como bioinformática e treinamento de grandes modelos de linguagem tem levado a entradas que frequentemente excedem a capacidade da memória principal, motivando o desenvolvimento de algoritmos de compressão no modelo de memória externa. Entre os paradigmas de compressão disponíveis, a compressão baseada em gramáticas é particularmente atrativa porque representa um texto como uma gramática livre de contexto que o gera como sua única derivação, permitindo armazenamento compacto enquanto suporta operações como descompressão e extração de substrings diretamente a partir da representação comprimida. Essas propriedades também tornam algoritmos de compressão baseada em gramáticas úteis como blocos fundamentais para índices de texto comprimidos e estruturas auto-indexáveis.
Entre os algoritmos de compressão baseada em gramáticas, o Grammar Compression by Induced Sorting (GCIS) constrói gramáticas recursivamente utilizando técnicas de ordenação induzida de sufixos. No entanto, o GCIS assume um cenário de memória interna e não escala para cargas de trabalho em memória externa de grande porte. Apresentamos o eGCIS, a primeira adaptação em memória externa do GCIS. Baseado no algoritmo de construção de arrays de sufixos em memória externa fSAIS, o eGCIS reutiliza estruturas intermediárias já produzidas durante a ordenação induzida, incluindo substrings recursivamente ordenadas e textos reduzidos, para gerar regras de gramática ao longo da recursão. O pipeline de construção resultante depende exclusivamente de primitivas de memória externa, como varreduras sequenciais e ordenação externa, evitando acesso aleatório ao texto de entrada. Também desenvolvemos um decodificador em memória externa capaz de reconstruir o texto original sob restrições de RAM.
Resultados experimentais mostram que o eGCIS pode comprimir e descomprimir entradas de até 4 GiB utilizando apenas 32 MiB de RAM, demonstrando que a compressão baseada em gramáticas via ordenação induzida pode ser efetivamente realizada no modelo de memória externa.
Banca examinadora
Titulares:
| Guilherme Pimentel Telles | IC/UNICAMP |
| Diego Gastón Arroyuelo Billiardi | PUC/Chile |
| Nalvo Franco de Almeida Junior | UFMS |
Suplentes:
| Santiago Valdés Ravelo | IC/UNICAMP |
| Maria Emília Machado Telles Walter | UnB |