String matching with a dynamic pattern
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Casamento de padrões dinâmicos
Primeiro orientador
Membros da banca
Victor Campos
Felipe Alves da Louza
Felipe Alves da Louza
Resumo
In this work, we study variations of the String Matching Problem: given two strings, a pattern P and a text T, we want to find how many times the pattern occurs in the text. We focus our contributions on the case of a dynamic pattern, that is, we want to support character additions and deletions to the pattern, and after each operation compute how many times it occurs in the text. We show a simple algorithm using Suffix Arrays that achieves O(log |T|) update time, after O(|T|) preprocess time. We show how to extend our solution to support substring deletion, transposition (moving a substring to another position of the pattern), and copy (copying a substring and pasting it in a specific position), in the same time complexities. Our solution can also be extended to support an online text (adding characters to one end of the text), maintaining the same amortized bounds. We also do a running time analysis of the proposed algorithm versus a naive solution, to illustrate its feasibility. A generalization of the suffix array for several strings is also discussed.
Abstract
Neste trabalho, nós estudamos variações do problema Casamento de Padrões: dadas duas strings, um padrão P e um texto T, queremos computar quantas vezes o padrão ocorre no texto. Nossa contribuição é focada no caso de um padrão dinâmico, ou seja, queremos suportar adição e remoção de caracteres no padrão, e após cada operação computar quantas vezes ele ocorre no texto. Nós mostramos um algoritmo simples usando Suffix Arrays que usa tempo O(log |T|), depois de tempo O(|T|) de pré-processamento. Nós mostramos como estender nossa solução para suportar remoção, transposição (mover a substring para outra posição) e cópia (copiar a substring e colar em uma posição específica) de substrings, na mesma complexidade de tempo. Nossa solução ainda pode ser estendida para suportar um texto online (adicionar caracteres em uma ponta do texto), mantendo as mesmas complexidades amortizadas de tempo. Também fazemos uma análise do tempo de execução do algoritmo proposto contra um algoritmo ingênuo, para demonstrar sua viabilidade. Também é discutida uma generalização do suffix array para várias strings.
Assunto
Computação – Teses, Algoritmos de computador – Teses, Complexidade computacional – Teses, Processamento de vetor (Computação) – Teses, Reconhecimento de padrões – Teses
Palavras-chave
strings, Algorithms, suffix array, string matching