Defesa de Doutorado de Felipe Alves da Louza

Data: 
27/07/2017 - 13:00
Local: 
Sala 85 IC 2

Título: Engineering Augmented Suffix Sorting Algorithms

 

Banca Examinadora
Titulares (Professores Doutores) Unidade / Instituição
Guilherme Pimentel Telles IC/UNICAMP
Eduardo Sany Laber DI/PUC-Rio
Said Sadique Adi FACOM/UFMS
Mauricio Ayala Rincón CIC/UnB
Lehilton Lelis Chaves Pedrosa IC/UNICAMP
Suplentes (Professores Doutores) Unidade / Instituição
Zanoni Dias IC/UNICAMP
Eduardo Cândido Xavier IC/UNICAMP
Nalvo Franco de Almeida Junior FACOM/UFMS

 

Resumo

Nesta tese estudamos problemas relacionados à ordenação de sufixos e a construção de estruturas de dados que desempenham um papel fundamental em indexação de textos e compressão de dados. Esta tese contribui com novos algoritmos para a construção do vetor de sufixos, da transformada de Burrows-Wheeler (BWT) e do vetor de prefixo comum mais longo (LCP). Esta tese é organizada como uma coletânea de artigos publicados em periódicos peer-reviewed. Nossa primeira contribuição é um algoritmo in-place que calcula a BWT e o vetor LCP simultaneamente em tempo quadrático utilizando espaço adicional constante. Nossa segunda contribuição é um algoritmo de ordenação de sufixos que constrói o vetor de sufixos junto com o vetor LCP em tempo e espaço ótimos para cadeias de caracteres de alfabetos de tamanho constante. Nossa terceira contribuição é um conjunto de algoritmos que constrói o vetor de sufixos aumentado com o vetor LCP e com o vetor de documentos para coleções de cadeias. Em particular, apresentamos um algoritmo ótimo para cadeias de alfabetos de tamanho constante. As soluções apresentadas nesta tese contribuem com melhorias teóricas e avanços práticos na construção de importantes estruturas de dados para processamento de cadeias.