Trabalho de Conclusão de Curso
Algoritmos em sequências
Aluno: Yan Soares Couto
Orientadora: Cristina G. Fernandes
Uma string \(T[1\,.\,.\,n]\) de tamanho \(|T| := n\) é um vetor de \(n\) elementos, onde todos elementos são de um alfabeto \(\Sigma\) finito. Algoritmos em strings são usados para buscar ocorrências (como por exemplo buscar por uma palavra específica em um documento de texto grande), encontrar a similaridade (como o diff) e muitas outras aplicações relacionadas a texto. Também são usados em biologia computacional, pois DNA pode ser modelado como uma sequência de caracteres A, T, C e G. Proteínas também podem ser modeladas como uma sequência de aminoácidos.
Algoritmos em strings são às vezes abordados em matérias obrigatórias da graduação (MAC122 ou MAC323), porém, apenas os algoritmos mais simples, como KMP ou Boyer-Moore, são vistos. Neste TCC, tenho por objetivo estudar algoritmos relacionados à busca de ocorrências, explicando, implementando e provando que estes funcionam. O objetivo é tanto ampliar meu conhecimento nessa área quanto preparar um texto em português que possa ser usado como referência nestes assuntos por pessoas com conhecimento básico de algoritmos em strings.
Os algoritmos abordados são sofisticados; porém, o objetivo é escrever um texto que leve facilmente à criação de código que funcione, com atenção a detalhes de implementação necessários, sem deixar instruções complicadas "a cargo do leitor".
Os tópicos abordados são:
- Palíndromos. É discutido um algoritmo que permite, dada uma string \(S\), determinar, para toda posição \(i\), o maior palíndromo de comprimento ímpar centrado nesta posição. Além disso, como usar esse algoritmo também para palíndromos de comprimento par. O algoritmo consome tempo \(\mathcal{O}(|S|)\) e permite, por exemplo, determinar a maior substring palíndroma de \(S\).
- Tries. Uma trie é uma árvore enraizada na qual cada aresta está associada a um caractere, e de um mesmo nó não saem duas arestas associadas ao mesmo caractere. Uma trie é usada para guardar um conjunto \(\mathcal{S} = \{S_1, \ldots, S_k\}\) de strings, e cada caminho a partir de sua raiz indica um prefixo de uma ou mais dessas strings. Dessa forma é possível encontrar o maior prefixo comum de uma dada string \(P\) com alguma string \(S \in \mathcal{S}\) sem depender do tamanho de todas as strings de \(\mathcal{S}\).
- Aho-Corasick. Dado um conjunto de strings \(\mathcal{S}\), e uma string \(P\), o algoritmo de Aho-Corasick permite encontrar todas as ocorrências de cada string \(S \in \mathcal{S}\) em tempo \(\mathcal{O}(\sum\limits_{S \in \mathcal{S}}{|S|}.|\Sigma| + |P| + x)\), onde \(x\) é o número de ocorrências de strings de \(\mathcal{S}\) em \(P\). O preprocessamento do Aho-Corasick pode ser interpretado como uma extensão de KMP para múltiplas strings.
- Árvores de Sufixos. Uma árvore de sufixos é uma trie para todos os sufixos de uma string \(P\). Um caminho da raiz até um nó da trie representa uma substring de \(P\), logo é possível descobrir se uma dada string \(S\) ocorre em \(P\) independentemente do tamanho de \(P\). É possível criar a árvore de sufixos de \(P\) em tempo e espaço \(\mathcal{O}(|P|.|\Sigma|)\).
- Autômato de Sufixos. Para toda substring \(P\) de \(S\), defina \(D(P)\) como o conjunto de ocorrências à direita de \(P\) em \(S\), ou seja, o conjunto de índices \(i\) tais que \(P\) é sufixo de \(S[1\,.\,.\,i]\). É possível construir um digrafo acíclico no qual os vértices são os conjuntos de ocorrências à direita de todas as substrings de \(S\), as arestas são associadas a caracteres, e cada caminho a partir da raiz representa uma substring de \(S\) e termina no vértice que representa o conjunto de ocorrências dessa substring. É discutido um algoritmo que contrói esse digrafo em tempo e espaço \(\mathcal{O}(|S|.|\Sigma|)\).