Defesa de Doutorado de Felipe Alves da Louza

Título do Trabalho
Engineering Augmented Suffix Sorting Algorithms
Candidato(a)
Felipe Alves da Louza
Nível
Doutorado
Data
Add to Calender 2017-07-27 00:00:00 2017-07-27 00:00:00 Defesa de Doutorado de Felipe Alves da Louza Engineering Augmented Suffix Sorting Algorithms Auditório do IC 2 - Sala 85 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
13:00
Local
Auditório do IC 2 - Sala 85
Orientador(a)
Guilherme Pimentel Telles
Banca Examinadora

Titulares:
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:
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.