ANÁLISE E APLICAÇÃO DE ESTRUTURAS DE SUFIXOS NA RESOLUÇÃO DO STRING MATCHING

Autores

  • Guilherme Henrique Santos Miranda UNOESTE
  • Leandro Luiz de Almeida
  • Danillo Roberto Pereira
  • Mario Augusto Pazoti
  • Francisco Assis da Silva

Palavras-chave:

string matching, árvore de sufixos, autômato de sufixos, estrutura de dados, pesquisa em textos

Resumo

String Matching é o problema que busca responder a seguinte pergunta: “É possível encontrar determinado padrão dentro de um texto?”. É um problema amplamente estudado na Ciência da Computação e também na Biologia Computacional, devido à existência de suas diferentes modificações em ferramentas de pesquisa e também no processamento de cadeias de DNA. Já existem algoritmos que alcançaram a solução ótima para responder a pergunta do problema, entretanto tais soluções não possuem a mesma eficiência nas extensões e variações do problema. Dessa forma, diversas pesquisas tem estudado estruturas de dados relativas aos sufixos do texto para alcançar soluções que sejam capazes de resolver variações complexas do string matching. O presente trabalho realiza um estudo e análise aprofundada sobre a eficiência de dessas estruturas: a árvore de sufixos e o autômato de sufixos. Algoritmos clássicos também são abordados e comparados às estruturas enquanto o trabalho é discorrido. As análises seguem critérios estatísticos, tempos de execução e complexidade de algoritmos para obter maior grau de confiança nos resultados.

Downloads

Não há dados estatísticos.

Publicado

2018-05-21

Como Citar

Henrique Santos Miranda, G., Luiz de Almeida, L., Roberto Pereira, D., Augusto Pazoti, M., & Assis da Silva, F. (2018). ANÁLISE E APLICAÇÃO DE ESTRUTURAS DE SUFIXOS NA RESOLUÇÃO DO STRING MATCHING. Colloquium Exactarum. ISSN: 2178-8332, 10(1), 01-17. Recuperado de http://revistas.unoeste.br/index.php/ce/article/view/2312

##plugins.generic.recommendByAuthor.heading##

1 2 3 > >>