Clique aqui e inclua na sua agenda
Dia 03/12, 11h, Sala 2016
Palestrante: Felipe Alves da Louza (UFU)
Título: BWT e FM-index: compressão e busca em dados textuais
Resumo:
Em 1994, Burrows e Wheeler apresentaram um algoritmo de compressão baseado em uma nova transformação reversível, mais tarde conhecida como Transformada de Burrows-Wheeler (BWT). A BWT é a base do compressor bzip2, amplamente utilizado. Alguns anos depois, Ferragina e Manzini mostraram que, ao combinar a BWT com estruturas de dados compactas, era possível criar um “índice comprimido” – uma estrutura de dados, posteriormente chamada de FM-index, que suporta buscas eficientes por subcadeias em um espaço assintoticamente igual ao dos melhores compressores (que não suportam consultas). Em 2022, a ACM concedeu a esses três autores o prêmio Paris Kanellaki¹ em reconhecimento por suas contribuições. Nesta palestra exploraremos a BWT e o FM-index, conceitos que transformaram a maneira como lidamos com compressão e busca em dados textuais.
