Knuth Morris Pratt

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Knuth-Morris-Pratt
rbl@cin.ufpe.br
*
*
*
Problema
Deseja-se procurar dentro de um longo texto todas as ocorrências de um determinado padrão.
Exemplo:
Procurar "nano" em "banananobanaca".
Ocorrência encontrada:
bana[nano]banaca
*
*
*
Solução ingênua
Para encontrar ocorrências, poderíamos verificar se, para cada posição da string que contém o texto, podemos formar o padrão.
Pseudo-código:
- Para cada posicao i dentro da string TEXTO:
- - Seja matches variavel igual a 0
- - Para cada posicao j dentro da string PADRAO:
- - - Se ( posicao i+j é valida dentro de TEXTO )
- - - e   ( TEXTO[i+j] igual a PADRAO[j] ):
- - - - incremente matches
- - Se ( matches igual a tamanho de PADRAO ):
- - - // Ocorrência encontrada!
*
*
*
Solução ingênua
Qual é a complexidade dessa solução?
Seja N o tamanho da string TEXTO, e M o tamanho da string PADRAO, podemos ver que a complexidade será O(N*M).
Funciona bem para textos e padrões pequenos, mas tem como ser melhor?
Vamos observar a execução desse algoritmo ingênuo e ver se tem como melhorá-lo.
*
*
*
Solução ingênua
 i 0 1 2 3 4 5 6 7 8 9 (...)    b a n a n a n o b a n a c a
 1 n
 2   n
 3     n a n o
 4       n
 5         n a n o
 6           n
 7             n a n
 8               n
 9                 n
10                   n
11                     n a n
(...)
*
*
*
Solução ingênua
Algumas dessas comparações são inúteis!
Após a iteração 3, sabemos que em TEXTO[3] existe um 'a', então não há necessidade de comparar com PADRAO[0], cujo valor é 'n'.
Da mesma forma, na iteração 5, já sabemos que TEXTO[4] é 'n', não há necessidade de comparar com PADRAO[0].
*
*
*
Melhorando a solução
À medida que se explora TEXTO, ao fazer um match parcial de tamanho K, sabe-se exatamente o que há nas K últimas posições de TEXTO, que é parte da string PADRAO.
Como usar esse conhecimento para evitar comparações inúteis?
*
*
*
Melhorando a solução
Evitar comparações que não vão fazer match.
 3     n a n
 4       n a n o
Podemos ignorar posições até encontrar uma sem conflitos:
 3     n a n
 5         n a n o
Não há necessidade de comparar novamente esses 'n', pois já sabiamos da existência desse 'n' no nosso match parcial anterior.
*
*
*
Melhorando a solução
Ao falhar uma comparação, precisamos aproveitar o nosso match parcial anterior. Veja:
 3     n a n
 5         n a n o
A maior sobreposição (overlap) entre o match anterior e o padrão que procuramos é 'n'. Vamos definir overlap como:
overlap(x, y):
retorna maior sufixo de x que também é prefixo de y
        e que não seja o próprio x, nem y
*
*
*
Melhorando a solução
Exemplos de resultados do overlap:
overlap("nan", "nano") = "n"
overlap("ABCAB", "ABCABAB") = "AB"
overlap("AAAA","AAAA") = "AAA"
overlap("D","D") = ""
Com esse overlap, poderemos reajustar o posicionamento do match parcial anterior levando em consideração nossas observações para otimizar a solução ingênua.
*
*
*
KMP
Ao fazer um mismatch, precisamos aproveitar ao máximo o que já obtivemos com o antigo match parcial, e continuar a partir do próximo caractere.
O maior aproveitamento do nosso match antigo é exatamente o overlap entre ele e o padrão inteiro.
Ao encontrar ocorrência do padrão, tratar de forma similar ao mismatch, para poder continuar a busca.
*
*
*
KMP
Exemplo (padrão: "ABCABAB"):
  A  B  C  A  B  C  A  B  A  B  C  A  C  A  B
# A  B  C  A  B  A (reajustar match parcial)
                overlap("ABCAB","ABCABAB") = "AB"
#         [A  B] C  A  B  A  B (encontrou!)
                overlap("ABCABAB","ABCABAB") = "AB"
#                        [A  B] C  A  B
                overlap("ABCA","ABCABAB") = "A"
#                                 [A] B
                overlap("A","ABCABAB") = ""
#                                     A
       (não temos mais match parcial, vamos prosseguir)
#                                        A  B
Em azul, o que pudemos aproveitar do match parcial anterior. Em verde, as comparações que retornaram true,
e, em vermelho, as comparações que retornaram false.
*
*
*
KMP
Voltando ao exemplo original:
 i 0 1 2 3 4 5 6 7 8 9 (...)
   b a n a n a n o b a n a c a
 1 n
 2   n
 3     n a n o (falha, match agora em 'n')
 4         n a n o (compara a partir de 'a')
 5                 n
 6                   n
 7                     n a n (match em '')
 8                         n
 9                           n
*
*
*
KMP
Pseudo-código (overlap retorna o tamanho da string):
- Inicialize i e j com 0
- Enquanto i for menor que N (ou tamanho de TEXTO), faça:
- - Repita até fazer break, incremente i ao terminar:
- - - Se ( TEXTO[i] == PADRAO[j] ):
- - - - Incremente j
- - - - Se ( j == M (ou tamanho de PADRAO) ):
- - - - - // Ocorrência encontrada!
- - - - - Faça j = overlap( PADRAO[0 .. j-1], PADRAO[0 .. M-1] )
- - - - Faça break
- - - Senão, se ( j == 0 ):
- - - - Faça break
- - - Senão:
- - - - Faça j = overlap( PADRAO[0 .. j-1], PADRAO[0 .. M-1] )
*
*
*
KMP
Como calcular a função overlap (que retorna o tamanho da string da nossa função original)?
Como sempre vamos calcular o overlap entre um prefixo do padrão e o padrão inteiro, podemos omitir essa repetição. Assim:
F(n) - n é o tamanho do nosso match parcial
     - retorna o tamanho do maior aproveitamento
F(0) = 0
F(1) = overlap( PADRAO[0 .. 1-1], PADRAO ).size()
F(1) = overlap( PADRAO[0], PADRAO ).size()
F(1) = 0
F(2) = overlap( PADRAO[0 .. 2-1], PADRAO ).size()
F(2) = overlap( PADRAO[0 .. 1], PADRAO ).size()
F(3) = overlap( PADRAO[0 .. 2], PADRAO ).size()
*
*
*
KMP
Considere o padrão "ABABAC", vamos listar todos os seus prefixos:
0. ""
1. "A"
2. "AB"
3. "ABA"
4. "ABAB"
5. "ABABA"
6. "ABABAC"
*
*
*
KMP
Aplicando overlap entre cada prefixo e o padrão inteiro, temos:
0. ""
1. ""
2. ""
3. "A"
4. "AB"
5. "ABA"
6. ""
*
*
*
KMP
Podemos agora listar todos os valores da nossa função F definida anteriormente:
F(0) = 0
F(1) = 0
F(2) = 0
F(3) = 1
F(4) = 2
F(5) = 3
F(6) = 0
*
*
*
KMP
Essa função guarda não só informação sobre o próximo maior match parcial, mas todos os anteriores. Veja:
5. "ABABA"
próximo melhor match parcial = F(5) = 3
3. "ABA"
próximo melhor match parcial = F(3) = 1
1. "A"
Então, o segundo melhor match parcial de 5 é simplesmente F( F(5) ), e assim por diante.
*
*
*
KMP
Para cada caractere em PADRAO, tentar expandir o melhor match parcial encontrado anteriormente. Se não conseguir, tentar o segundo melhor, e assim por diante. Se não houver como expandir, então o valor de F para aquela posição será zero.
*
*
*
KMP
Pseudo-código:
- F(0) = 0, F(1) = 0
- for( i = 2; i <= M; ++i ):
- - j = F(i-1)
- - while(true):
- - - if ( PADRAO[j] == PADRAO[i-1] ):
- - - - F(i) = j + 1
- - - - break
- - - if ( j == 0 ):
- - - - F(i) = 0
- - - - break
- - - j = F(j)
*
*
*
KMP
O custo do preprocessamento é O(M). O custo de procurar as ocorrências é O(N). Logo, custo total do KMP é O(N+M).
A demonstração do porquê de cada custo foi omitida nessa apresentação, mas disponível nas referências.
*
*
*
Referências
http://www.ics.uci.edu/~eppstein/161/960227.html
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching