Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/325682
Type: TESE DIGITAL
Title: Engineering augmented suffix sorting algorithms = Algoritmos para ordenação de sufixos aumentada
Title Alternative: Algoritmos para ordenação de sufixos aumentada
Author: Louza, Felipe Alves da, 1988-
Advisor: Telles, Guilherme Pimentel, 1972-
Abstract: Resumo: Nesta tese estudamos problemas relacionados com a 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. Nossa segunda contribuição é um algoritmo de ordenação de sufixos que constrói o vetor de sufixos e o vetor LCP em tempo e espaço ótimos para cadeias 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. 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

Abstract: In this thesis we study problems related to suffix sorting and to the construction of data structures that play a fundamental role in text indexing and data compression. This thesis contributes with new algorithms for the suffix array, the Burrows-Wheeler transform (BWT) and the longest common prefix (LCP) array construction. This thesis is organized as a collection of articles published in peer-reviewed journals. Our first contribution is an in-place algorithm that computes the BWT and the LCP array simultaneously in quadratic time. Our second contribution is a suffix sorting algorithm that constructs the suffix array together with the LCP array in optimal time and space for strings from constant size alphabets. Our third contribution is a set of algorithms to build the suffix array augmented with the LCP array and with the document array for string collections. The solutions presented in this thesis contribute with theoretical improvements and practical advances in building important data structures for string processing
Subject: Processamento de textos (Computação)
Ordenação (Computadores)
Algoritmos
Language: Inglês
Editor: [s.n.]
Date Issue: 2017
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Louza_FelipeAlvesDa_D.pdf1.41 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.