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

Os dados de download ainda não estão disponíveis.

Downloads

Publicado

2018-05-21

Como Citar

ANÁLISE E APLICAÇÃO DE ESTRUTURAS DE SUFIXOS NA RESOLUÇÃO DO STRING MATCHING. (2018). Colloquium Exactarum. ISSN: 2178-8332, 10(1), 01-17. https://revistas.unoeste.br/index.php/ce/article/view/2312

Artigos Semelhantes

1-10 de 415

Você também pode iniciar uma pesquisa avançada por similaridade para este artigo.

Artigos mais lidos pelo mesmo(s) autor(es)

1 2 3 4 > >>