Árvores de Ukkonen: caracterização combinatória e aplicações (2011)
- Authors:
- Autor USP: SACOMOTO, GUSTAVO AKIO TOMINAGA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: ALGORITMOS E ESTRUTURAS DE DADOS
- Agências de fomento:
- Language: Português
- Abstract: A árvore de sufixos, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre as quais a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como mcasos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra.
- Imprenta:
- Data da defesa: 08.02.2011
-
ABNT
SACOMOTO, Gustavo Akio Tominaga. Árvores de Ukkonen: caracterização combinatória e aplicações. 2011. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21042011-092209/. Acesso em: 28 abr. 2024. -
APA
Sacomoto, G. A. T. (2011). Árvores de Ukkonen: caracterização combinatória e aplicações (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21042011-092209/ -
NLM
Sacomoto GAT. Árvores de Ukkonen: caracterização combinatória e aplicações [Internet]. 2011 ;[citado 2024 abr. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21042011-092209/ -
Vancouver
Sacomoto GAT. Árvores de Ukkonen: caracterização combinatória e aplicações [Internet]. 2011 ;[citado 2024 abr. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21042011-092209/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
