FACULDADE DE TECNOLOGIA DE SÃO PAULO Guilherme de Almeida Moreira Algoritmos para Busca de Padrões: Uma Análise Comparativa Empírica São Paulo 2012 FACULDADE DE TECNOLOGIA DE SÃO PAULO Guilherme de Almeida Moreira Algoritmos para Busca de Padrões: Uma Análise Comparativa Empírica Trabalho submetido como exigência parcial para a obtenção do Grau de Tecnólogo em Processamento de Dados Orientador: Dr. Silvio do Lago Pereira São Paulo 2012 FACULDADE DE TECNOLOGIA DE SÃO PAULO Guilherme de Almeida Moreira Algoritmos para Busca de Padrões: Uma Análise Comparativa Empírica Trabalho submetido como exigência parcial para a obtenção do Grau de Tecnólogo em Processamento de Dados. Parecer do Professor Orientador: Orientador:Dr. Silvio do Lago Pereira São Paulo, de Junho de 2012 Resumo Devido ao grande volume de informações que é gerado hoje na internet, é essencial poder localizar informações dentro deste conteúdo. Porém com um volume de dados tão grande é importante estudar qual a melhor forma de realizar essas buscas. O objetivo deste trabalho é analisar cinco algoritmos diferentes de busca em texto dinâmico, aquele que não se tem informações prévias sobre ele. Os cinco algoritmos são: Força Bruta, Rabin-Karp, busca por Autômato, Knuth- Morris-Pratt e Boyer-Moore. Basicamente todos os algoritmos baseiam-se na comparação de uma janela do texto com o padrão. A janela é um conjunto de caracteres sequenciais do texto que tenha o mesmo tamanho do padrão. A diferença entre os algoritmos consiste em como eliminar algumas comparações e como movimentar a janela. O algoritmo de Força Bruta tem a implementação mais trivial de todas, a comparação é feita caracter a caracter, caso algum deles não corresponda a janela é movida uma posição. O algoritmo de Rabin-Karp tenta evitar a comparação de todos os caracteres através da comparação entre o hash da janela e do padrão, outro ponto chave deste algoritmo é a forma como é feito o deslocamento da janela. Através de alguns calculos que envolvem o descarte do primeiro caracter e a soma do próximo, não é necessário recalcular o hash inteiro da nova janela. A comparação dos caracteres das janelas é executada apenas quando os hash’s corresponderem, com isso a quantidade de comparações diminui. Na busca por Autômato o problema atacado é a comparação repetida de caracteres, que pode acontecer em Força Bruta e Rabin-Karp. Neste algoritmo cada caractere com- parado muda o estado de um autômato, este autômato serve para avaliar se o prefixo atual pode ser reaproveitado. Com Knuth-Morris-Pratt a base é a mesma do autômato, porém a analise de prefixos não é feita para cada possível transição de caracter, ela é feita apenas com o prefixo/sufixo do próprio padrão e a transição de estado é feita apenas quando o texto estiver sendo comparado com o padrão, na maioria das vezes melhorando o desempenho da busca. O último algoritmo estudado é o Boyer-Moore, diferente de todos os outros algoritmos, neste a janela é comparada da direita para a esquerda. O ganho com essa mudança é o conhecimento obtido na comparação dos caracteres finais. Esses caracteres são analisados com duas heurísticas diferentes, a do bom sufixo, que confere se o sufixo ou parte dele ocorre novamente no padrão e alinha a janela com essa correspondência e a heurística do caracter errado, ela procura o caracter que não foi correspondido na pesquisa e procura uma ocorrência anterior no padrão, alinhando a janela com este caracter. Dentre todos os algoritmos o que obteve melhor desempenho geral foi o Boyer-Moore, queinclusiveéaimplementaçãomaiscomumdealgoritmodebusca, emboraparacenários 1 onde o padrão e alfabetos são muito pequenos Força-Bruta e Autômato resolvem melhor o problema. 2 Abstract Due to the large amount of content generated in Internet today, it is mandatory be able to find pieces of information inside this content. However with this large amount of content it is important to study which is the best way to perform this searches. The aim of this paper is to analyze five different algorithms of search in dynamic text, the one that does not have prior information about it. The five algorithms are: Naive Search, Rabin-Karp, search by automata, Knuth- Morris-Pratt and Boyer-Moore. Basically all this algorithms are based on comparison between the text window and the pattern. The window is a set of sequence of characters of same size of the pattern. The difference between the algorithms consists in how eliminate some comparisons and how to move the window. The Naive algorithms is the most trivial implementation of them, the comparison is done character by character, whether some of them does not match, the window is moved by one position. The Rabin-Karp algorithm tries to avoid the comparison between all the characters by comparing the window’s hash and the pattern’s hash, another key of this algorithm is how the window is moved. Enabled by some computation, that involves the first character disposes and the sum of the next one, it is not mandatory to re-calculate the entire new window hash. The comparison between the characters it is done only when the hash’s are equivalent. therefore decreasing the comparisons done during the execution. Searching by automata the main goal is to avoid the duplicate comparison, that can occur in Naive and Rabin-Karp algorithms. With this algorithm each compared character changes the state of the automata. This automata is used to evaluate whether the current prefix can be reused. The Knuth-Morris-Pratt algorithm has the same foundation of the automata, however the prefix analysis is not done for all the possible transitions, it is done only in the prefix of the pattern and the computation of state transition is done just when the text and the pattern are being compared, in most of times improving the performance again the’ automata. The last studied algorithm it is Boer-Moore, not like all others algorithms, in this one the window is compared from right to left. This change can improve the overall performance because of the knowledge of the last characters. They are analyzed by two distinct heuristics, the good-suffix that checks if the suffix, or part of it, occur again in the pattern and align the window with this match. There is also the bad-character heuristic, that searches for the mismatch character align the window with this character. From all algorithms the one with better overall performance was Boyer-Moore, it is the most common search algorithm implementation, nevertheless in some contexts, where 3 the alphabet and the pattern are small Naive and automata solve better the problem. 4 Sumário 1 Introdução 7 1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Organização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Fundamentos e Terminologia 9 2.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Siglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Fundamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Algoritmos de Busca de Padrões 12 3.1 Força-Bruta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Rabin-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.2 Otimizações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.3 Usando o resto da divisão por um inteiro . . . . . . . . . . . . . . . 15 3.2.4 Utilização de Hash em Rabin-Karp . . . . . . . . . . . . . . . . . . 16 3.2.5 O algoritmo final . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Autômatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Construção do Autômato . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.3 O algoritmo de busca com Autômato . . . . . . . . . . . . . . . . . 21 3.4 Knuth-Morris-Pratt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1 Pré-processamento de KMP . . . . . . . . . . . . . . . . . . . . . . 23 3.4.2 Processamento de KMP . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Boyer-Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5.1 As Heurísticas de Boyer-Moore . . . . . . . . . . . . . . . . . . . . 26 3.5.2 A Heurística do Caracter Errado . . . . . . . . . . . . . . . . . . . 26 3.5.3 A heurística do Bom sufixo . . . . . . . . . . . . . . . . . . . . . . 27 3.5.4 Processamento em Boyer-Moore . . . . . . . . . . . . . . . . . . . . 32 4 Resultados Experimentais 34 5 Conclusão 53 6 Anexo I - Implementações dos algoritmos 54 7 Referências Bibliográficas 63 5 Lista de Figuras 1 Texto formado por uma cadeia de DNA . . . . . . . . . . . . . . . . . . . . 7 2 Padrão formado por uma cadeia de DNA . . . . . . . . . . . . . . . . . . . 7 3 Cadeia de DNA com uma ocorrência . . . . . . . . . . . . . . . . . . . . . 8 4 Exemplo de janela de comparação . . . . . . . . . . . . . . . . . . . . . . . 10 5 Janela na primeira posição . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6 Janela na segunda posição . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7 Janela na terceira posição . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 8 Primeiro passo na busca por Força-Bruta . . . . . . . . . . . . . . . . . . . 12 9 Segundo passo na busca por Força-Bruta . . . . . . . . . . . . . . . . . . . 12 10 Terceiro passo na busca por Força-Bruta . . . . . . . . . . . . . . . . . . . 13 11 Quarto passo na busca por Força-Bruta . . . . . . . . . . . . . . . . . . . . 13 12 Ocorrência encontrada com Força-Bruta . . . . . . . . . . . . . . . . . . . 13 13 Diferença de valor com Rabin-Karp . . . . . . . . . . . . . . . . . . . . . . 14 14 Janela e padrão com valores iguais . . . . . . . . . . . . . . . . . . . . . . 15 15 Janela e padrão com valores iguais, porém com textos diferentes . . . . . . 15 16 Sequência de estados da palavra ababaca . . . . . . . . . . . . . . . . . . . 19 17 Autômato no estado 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 18 Autômato no estado 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 19 Voltando um estado no autômato . . . . . . . . . . . . . . . . . . . . . . . 19 20 Erro na quinta posição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 21 Há uma substring correspondente ao prefixo . . . . . . . . . . . . . . . . . 22 22 Deslocamento de uma posição errado . . . . . . . . . . . . . . . . . . . . . 22 23 Deslocamento de duas posições com chance de ocorrência . . . . . . . . . . 22 24 Deslocamento de duas posições correto . . . . . . . . . . . . . . . . . . . . 23 25 O prefixo ’ab’ também ocorre na posição 2 . . . . . . . . . . . . . . . . . . 23 26 Falha ao comparar o caracter ’a’ com ’z’ . . . . . . . . . . . . . . . . . . . 26 27 Alinhamento no caracter ’a’ . . . . . . . . . . . . . . . . . . . . . . . . . . 26 28 Falha ao comparar o caracter ’a’ com ’z’ . . . . . . . . . . . . . . . . . . . 27 29 Deslocamento ultrapassando caracter ’b’ . . . . . . . . . . . . . . . . . . . 27 30 Formação do sufixo ’ab’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 31 Alinhamento ao sufixo ’ab’ . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 32 Formação do sufixo ’dab’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 33 Alinhamento ao sufixo/prefixo ’ab’ . . . . . . . . . . . . . . . . . . . . . . 29 34 Formação do sufixo ’ab’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 35 Deslocamento ultrapassa o sufixo ’ab’ . . . . . . . . . . . . . . . . . . . . . 29 36 Capitu em Dom Casmurro . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 37 Capitu em Dom Casmurro . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6 38 Parágrafo em Dom Casmurro . . . . . . . . . . . . . . . . . . . . . . . . . 37 39 Parágrafo em Dom Casmurro . . . . . . . . . . . . . . . . . . . . . . . . . 38 40 Linux Dictionary em Texto em Inglês . . . . . . . . . . . . . . . . . . . . . 39 41 Linux Dictionary em Texto em Inglês . . . . . . . . . . . . . . . . . . . . . 40 42 10 a e b em 1000 a e b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 43 10 a e b em 1000 a e b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 44 10 a e b em 10.000.000 a e b . . . . . . . . . . . . . . . . . . . . . . . . . . 43 45 10 a e b em 10.000.000 a e b . . . . . . . . . . . . . . . . . . . . . . . . . . 44 46 DNA tamanho 2 em DNA tamanho 10 . . . . . . . . . . . . . . . . . . . . 45 47 DNA tamanho 2 em DNA tamanho 10 . . . . . . . . . . . . . . . . . . . . 46 48 DNA tamanho 10 em DNA tamanho 3000 . . . . . . . . . . . . . . . . . . 47 49 DNA tamanho 10 em DNA tamanho 3000 . . . . . . . . . . . . . . . . . . 48 50 DNA tamanho 10.000 em DNA tamanho 200.000.000 . . . . . . . . . . . . 49 51 DNA tamanho 10.000 em DNA tamanho 200.000.000 . . . . . . . . . . . . 50 52 Padrão tamanho 100 em texto 2.000.000 com alfabeto de 65.000 . . . . . . 51 53 Padrão tamanho 100 em texto 2.000.000 com alfabeto de 65.000 . . . . . . 52 7