Algoritmo de Knuth-Morris-Pratt - KMP

Algoritmo de Knuth-Morris-Pratt - KMP

1. Algoritmo KMP ( Knuth -Morris- Pratt ) Curso de Maratona de Programação ICT-Unifesp - SJC

2. KMP Para que serve? Saber se uma string é substring de outra. String searching algorithm . É legal? Sim, você escreve pouco (código pequeno) e é eficiente ! Vídeo-aula utilizando esses slides: https :// youtu.be/VxcrVqoi_k8 2

3. KMP Ideia do algoritmo: Procura uma palavra (padrão) P dentro de um texto T. Quando aparece uma diferença ( mismatch ), a palavra tem em si a informação necessária para determinar onde começar a próxima comparação, ou seja, um mistmach consiste em caracteres que já conhecemos porque eles estão na palavra/padrão (isso evita retroceder pelos caracteres já conhecidos). Pense: considerando um algoritmo de força bruta, quando ocorre uma diferença entre T[i] e P[j], não seria possível fazer um deslocamento maior de P para a direita evitando comparações redundantes? 3

4. KMP Ideia do algoritmo: A B A A B X A B A A B A i j T P o maior prefixo que é sufixo é o AB 4

5. KMP T[i] != P[j] A B A A B X A B A A B A i j T P pode-se recomeçar a partir daqui essas comparações não precisam ser refeitas 5

6. KMP Exemplo: texto = "eu gosto de c++" palavra: "gosto" A palavra "gosto" foi encontrada na posição 3 (indexando a partir do 0). 6

7. KMP Aplicação: Quando você utiliza um editor de sua preferência e quer buscar uma string em um arquivo, esses tipos de algoritmos são utilizados para exibir os resultados da busca. 7

8. KMP Complexidade: A complexidade no pior caso é O(n) onde “n” é o tamanho do texto em que a palavra será buscada. Um algoritmo ruim teria complexidade O(n * m) onde “n” seria o tamanho do texto e “m” o tamanho da palavra. Duas etapas: prefix function s tring matching 8

9. KMP Prefix function : KMP faz um pré-processamento da palavra (padrão) e constrói um array auxiliar (vou chamá-lo de “ aux ”) de tamanho “m” (mesmo tamanho da palavra). O pré-processamento analisa todos os prefixos do padrão procurando pelo maior sufixo destes prefixos que também seja prefixo. O pré-processamento evita que um caractere seja reexaminado! Exemplo: ABAB O maior sufixo que também é prefixo é o “AB” que termina na posição 1 (indexando a partir do 0) e também ocorre na posição 2. 9

10. KMP Prefix function : Ao final, teremos um array que conterá cada posição que gera um prefixo para cada posição do padrão. O pré-processamento é feito na palavra (padrão) para determinar se seus prefixos aparecem como subsequências deles mesmos. O array que iremos construir nessa fase chamaremos de “ aux ” de forma que: O tamanho do maior prefixo de aux [0..k] que é sufixo de aux [1..k]. Ou seja, é o tamanho do maior “começo” de aux [k] que também aparece no seu “fim” sem condiderar ele mesmo. 10

11. KMP Prefix function 11

12. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 A == B ? Não, coloca 0 na posição marcada por “i” e incrementa “i” 12

13. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 A == C ? Nãão , coloca 0 na posição marcada por “i” e incrementa “i” 13

14. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 A == D ? Nããão , coloca 0 na posição marcada por “i” e incrementa “i” 14

15. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 A == A ? Sim, incrementa “j”, guarda o valor de “j” na posição marcada por “i” e incrementa o “i” 15

16. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 1 B == B ? Simm , incrementa “j”, guarda o valor de “j” na posição marcada por “i” e incrementa o “i” 16

17. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 1 2 C == C ? Simmm , incrementa “j”, guarda o valor de “j” na posição marcada por “i” e incrementa o “i” 17

18. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 1 2 3 D == A ? Não, mas o j é diferente de 0, então podemos fazer: j = aux [j – 1], o u seja, j = 0, não incrementa o “i” e nem o “j’ 18

19. KMP Considere a palavra: ABCDABCA A B C D A B C A j i 1 2 3 4 5 6 7 1 2 3 Voltamos tudo de novo :(, calma, está terminando... A == A ? Sim, incrementa “j”, guarda o valor de “j” na posição marcada por “i” e incrementa o “i” 19

20. KMP Considere a palavra: ABCDABCA A B C D A B C A j 1 2 3 4 5 6 7 1 2 3 1 i = 8, ou seja, não é menor do que o tamanho da palavra ABCDABCA, portanto, chegamos ao fim da execução. 20

21. KMP Algoritmo da fase de pré-processamento ( prefix function ): substr = palavra = padrão 21

22. KMP String matching 22

23. KMP Vamos tentar identificar a palavra “CD” Primeiro fazemos o pré-processamento construindo o vetor “ aux ” para o padrão que se quer encontrar. idx_substr -> índice da substring /palavra/padrão idx_str -> índice da string /texto idx_substr = idx_str = 0 C D 1 23

24. KMP Vamos tentar identificar a palavra “CD” C D 1 Critério de parada: idx_str < tam_str 24

25. KMP Vamos tentar identificar a palavra “ C D” A B C D A B C A Lembrando que idx_substr = 0 e idx_str = 0 substr [ idx_substr ] == str [ idx_str ] ? C == A ? Não ( mismatch ) 25

26. KMP Vamos tentar identificar a palavra “ C D” A B C D A B C A Lembrando que idx_substr = 0 e idx_str = 0 idx_substr == tam_substr ? 0 == 2 ? Não, ou seja, a palavra ainda não foi encontrada no texto. 26

27. KMP Vamos tentar identificar a palavra “ C D” A B C D A B C A Lembrando que idx_substr = 0 e idx_str = 0 // mismatches após idx_substr matches idx_str < tam_str E substr [ idx_substr ] != str [ idx_str ] ? Ou seja, 0 < 8 E C != A ? Sim, então verificamos: idx_substr != 0 ? Não, então idx_str = idx_str + 1 = 1 27

28. KMP Vamos tentar identificar a palavra “ C D” A B C D A B C A idx_substr = 0 e idx_str = 1 substr [ idx_substr ] == str [ idx_str ] ? C == B ? Não. idx_substr == tam_substr ? 0 == 2 ? Não. idx_str < tam_str E substr [ idx_substr ] != str [ idx_str ] ? 1 < 8 E C != B ? Sim. idx_substr != 0 ? Não, então idx_str = idx_str + 1 = 2 28

29. KMP Vamos tentar identificar a palavra “ C D” A B C D A B C A idx_substr = 0 e idx_str = 2 substr [ idx_substr ] == str [ idx_str ], C == C ? Sim, então incrementa idx_substr e idx_str em 1 Agora idx_substr = 1 e idx_str = 3 idx_substr == tam_substr ? 1 == 2 ? Não, ainda não encontramos o padrão. idx_str < tam_str E substr [ idx_substr ] != str [ idx_str ] ? Não, porque D == D! 29

30. KMP Vamos tentar identificar a palavra “C D ” A B C D A B C A idx_substr = 1 e idx_str = 3 substr [ idx_substr ] == str [ idx_str ], D == D ? Sim, então incrementa idx_substr e idx_str em 1 Agora idx_substr = 2 e idx_str = 4 idx_substr == tam_substr ? 2 == 2 ? Sim, então imprime que o padrão foi encontrado. 30

31. KMP Vamos tentar identificar a palavra “C D ” A B C D A B C A idx_substr = 2 e idx_str = 4 Após a impressão do padrão encontrado, é feito: idx_substr = aux [ idx_substr – 1] Aqui utilizamos o array que construímos no pré-processamento. idx_substr = aux [2 – 1] = aux [1] -> idx_substr = 0 Aqui não fez muita diferença, pois nosso padrão é apenas “CD”, o importante é que nessa parte tenta evitar comparações descenessárias fazendo uso do array “ aux ”. C D 1 31

32. KMP Vamos tentar identificar a palavra “CD” A B C D A B C A E assim sucessivamente, o algoritmo encontra todas as posições do padrão buscado no texto e de forma rápida: O(n)! 32

33. KMP Algoritmo da etapa string matching : 33

34. KMP Algoritmo: https:// goo.gl/ybXQqN ou https :// gist.github.com/marcoscastro/618bcfc9ec58e3b27661 Implementação em C++: https:// goo.gl/g0mrcL ou https:// gist.github.com/marcoscastro/55cc08aef269d6d006d2 Vídeo-aula: https:// youtu.be/VxcrVqoi_k8 34

35. Considerações sobre strings Se eu tenho só duas strings e quero achar uma dentro da outra, o que eu posso usar para otimizar? Resposta: KMP. Se eu tenho várias strings e quero encontrar a ocorrência delas em uma única string , o que eu posso usar para otimizar? Resposta: Suffix Tree ou Suffix Array . Otimização: algoritmo de Ukkonen para construir a suffix tree . E a Trie (árvore de prefixo)? Uma alternativa ao map. 35

36. Contato [email protected] www.geeksbr.com www.twitter.com/mcastrosouza 36