Casamento de Padrão Com Busca Exata e Aproximada

UNIVERSIDADE FEDERAL DO ESPRITO SANTO MESTRADO EM INFORMTICA

PROJETO DE ANLISE DE ALGORITMOS

Ana Christina de Oliveira Bringuente Rodrigo Fernandes Calhau

Casamento de Padro com Busca Exata e Aproximada

Vitria ES 2009

1

Sumrio 1 Introduo ......................................................................................................... 2 2 Casamento exato .............................................................................................. 3

2.1 Boyer-Moore-Horspool BMH ..........................................................................3 2.1.1 Descrio.............................................................................................. 3 2.1.2 Anlise .................................................................................................. 4

2.2 Boyer-Moore-Horspool-Sunday BMHS ..........................................................5 2.2.1 Descrio.............................................................................................. 5 2.2.2 Anlise .................................................................................................. 7

2.3 Shift-And Exato .................................................................................................7 2.3.1 Descrio.............................................................................................. 7 2.3.2 Anlise .................................................................................................. 9

3 Casamento Aproximado.................................................................................... 9 3.1 Shift-And Aproximado .......................................................................................9

3.1.1 Descrio.............................................................................................. 9 3.1.2 Anlise ................................................................................................ 11

3.2 Programao Dinmica...................................................................................12 3.2.1 Descrio............................................................................................ 12 3.2.2 Anlise ................................................................................................ 13

4 Experimentos .................................................................................................. 14 4.1 Execuo ........................................................................................................14 4.2 Resultado Experimentais ................................................................................15

4.2.1 Metodologia ........................................................................................ 15 4.2.2 Resultados.......................................................................................... 16

5 Sumrio........................................................................................................... 23

2

1 Introduo Este trabalho visa comparar os diversos algoritmos usados no processamento de cadeias de caracteres, escolhidos a partir de um conjunto chamado alfabeto. O objetivo do mesmo estudar a busca de palavras (padres) em um texto, atravs do casamento de caracteres. O casamento pode ser exato ou aproximado, como mostraremos no prximo captulo. Este trabalho est organizado da seguinte forma: Captulo 2: Casamento exato e os algoritmos usados para este tipo de casamento. Para cada algoritmo, apresentamos uma breve descrio e uma anlise genrica; Captulo 3: Casamento aproximado e os algoritmos usados para este tipo de casamento. Para cada algoritmo, apresentamos uma breve descrio e uma anlise genrica; Captulo 4: Demonstramos os experimentos realizados e confrontamos os resultados de cada um dos algoritmos.

3

2 Casamento exato O casamento exato acontece quando todos os caracteres do padro so encontrados exatamente na mesma ordem no texto. Neste trabalho apresentaremos os seguintes algoritmos para casamento exato: Boyer-Moore-Horspool, Boyer-Moore-Horspool-Sunday e Shift-And Exato.

2.1 Boyer-Moore-Horspool BMH

2.1.1 Descrio Este algoritmo executa uma busca sequencial no texto do padro a ser pesquisado atravs de comparaes realizadas da direita para a esquerda com relao ao padro, o que torna este algoritmo muito rpido.

O algoritmo BMH consiste em pesquisar o padro P em uma janela que desliza ao longo do texto T. Para cada posio desta janela, o algoritmo faz uma pesquisa por um sufixo da janela que casa com um sufixo de P, com comparaes realizadas no sentido da direita para a esquerda. Se no ocorrer uma desigualdade, ento uma ocorrncia de P em T foi encontrada. Seno, o algoritmo calcula um deslocamento em que o padro deve ser deslizado para a direita antes que uma nova tentativa de casamento se inicie (ZIVIANI, 2004). O algoritmo BOYER-MOORE-HORSPOOL funciona da seguinte forma (Algoritmo 1): para cada posio da janela de procura, comparamos o seu ltimo caractere com o ltimo caractere do padro. Se eles casarem, verificamos a janela de procura voltando para o penltimo caractere do padro assim at que seja encontrado o padro ou falhe no caractere do teste. Ento, independente se teve um casamento ou no, fazemos um deslocamento na janela de acordo com a prxima ocorrncia da letra no padro.

A seguir apresentamos a implementao do algoritmo BMH:

4

long bmh(char *linha, char *padrao, int numLinha, int erro, int* ocorrencias) { int n = strlen(linha); int m = strlen(padrao); long i, j, k; long d[MAX_CHAR]; long comp=0; *ocorrencias = 0;

// pre processamento for (j=0; j

5

deslocamentos so maiores, do tamanho do padro. O caso esperado tambm O(n/m), se c pequeno e m no muito grande (ZIVIANI, 2004).

2.2 Boyer-Moore-Horspool-Sunday BMHS

2.2.1 Descrio O BMHS uma variao do BMH. Ele enderea a tabela com o caractere no texto correspondente ao prximo caractere aps o ltimo caractere do padro, em vez de deslocar o padro usando o ltimo caractere como no algoritmo BMH.

Atravs de deslocamentos maiores, e o baixo nmero de referncias memria deste novo algoritmo, o faz executar mais rapidamente no geral.

Desta forma, para pr-computar o padro, o valor inicial de todas as entradas na tabela de deslocamentos feito igual a m+1. A seguir, os m primeiros caracteres do padro so usados para obter os outros valores da tabela.

A seguir apresentamos a implementao do algoritmo BMHS:

6

long bmhsLinha(char *linha, char *padrao, int numLinha, int erro, int* ocorrencias) { int tamLinha = strlen(linha); int tamPadrao = strlen(padrao);

*ocorrencias = 0;

long i, j, k;

long d[MAX_CHAR+1];

long comp=0;

// Pre-processamento for (i=0; i

7

2.2.2 Anlise Observando o cdigo, temos que o comportamento assinttico do BMHS idntico ao BMH tanto no pr-processamento quanto na pesquisa. Entretanto os deslocamentos so mais longos (podendo chegar a m+1), levando a saltos relativamente maiores para padres curtos e resultando em execues mais rpidas.

2.3 Shift-And Exato

2.3.1 Descrio Este algoritmo foi proposto por Baeza-Yates e Gonet em 1989. A idia por trs deste algoritmo bastante simples, e seu tempo de execuo bem melhor que diversos algoritmos de busca como por exemplo o proposto por KNUTH-MORRIS-PRATT.

Este consiste em manter um conjunto de todos os prefixos de P que casem com um sufixo do texto lido. Os algoritmos utilizam paralelismo de bits1 para atualizar este conjunto a cada novo caractere. Este conjunto representado por uma mscara D = dm...d1. Tirando proveito do paralelismo de bit, o nmero de operaes que um algoritmo realiza pode ser reduzido por um fator de at , onde o nmero de bits da palavra do computador. Considerando que nas arquiteturas atuais, 32 ou 64, temos um ganho relativamente grande.

Colocamos um 1 na j-sima posio de d(esta posio ento dita estar ativa) se e somente se p1...pj um sufixo de t1...ti. Se o tamanho de p menor que , ento este vetor poder ser armazenado em um registrador. Reportamos um casamento sempre que dm ficar ativo.

Ao ler o prximo caractere ti+1, temos que computar o novo conjunto D. Uma posio j+1 neste conjunto ser ativada se e somente se a posio j estava ativada

1 Uma tcnica que tira proveito do paralelismo intrnseco das operaes sobre bits dentro de uma

palavra de computador. Neste caso, possvel empacotar muitos valores em uma nica palavra e atualizar todos eles em uma nica operao

8

em D, isto , p1...pj era um sufixo de t1...ti e ti+1 casa com pj+1. Este novo conjunto fcil de computar em tempo constante usando operaes com paralelismo de bits.

O algoritmo primeiro monta uma tabela B, que armazena a mscara de bits bm...b1 para cada caractere. A mscara em B[c] tem o j-simo bit ligado se pj=c.

Inicialmente setamos D = 0m, e para cada novo caractere ti+1 atualizamos D usando a frmula

(I)

Intuitivamente, o ''

9

} comp++; } return comp; }

Algoritmo 3 - Shift-And Exato

2.3.2 Anlise A fase de pr-processamento, onde criada a tabela de mscara M ocorre nos dois primeiros loops do cdigo. A fase de pesquisa constituda por um loop em que i varia de 1 at n, onde cada caracter analisado. Desta forma temos que o custo deste algoritmo O(n). O custo de espao O(c).

3 Casamento Aproximado

3.1 Shift-And Aproximado

3.1.1 Descrio

Como o prprio nome indica, este algoritmo uma modificao do Algoritmo SHIFT-AND original que permite o casamento aproximado dos padres. Este algoritmo foi proposto por Wu e Manber em 1992.

A implementao deste algoritmo bastante parecida com a implementao do SHIFT-AND original. Ele tambm representa o autmato como uma seqncia de bits e, atravs de operaes lgicas bit a bit, realiza o caminhamento no autmato. Uma mscara tambm definida para cada um dos caracteres do alfabeto.

Este algoritmo empacota cada linha j(0

10

Na posio i do texto, os novos valores Rj, o 1) | 10m-1) & M[T[i]]

Rj= ((Rj >> 1) & M[T[i]]) | Rj-1 | (Rj-1 >> 1) | (Rj-1 >>1)

onde M a tabela do algoritmo SHIFT-AND conforme mostrado anteriormente. A princpio estas operaes em Rj parecem complicadas, mas explicando elas por partes, ficam bem mais fcil de entender:

((Rj >>1) & M[T[i]]): faz com que os estados ativos acumulados pelo registrados Rj continuem caminhando em direo ao estado final do autmato em conformidade com a mscara do caractere atual do texto;

Rj-1: simula a insero de um caractere no padro, ou que um caractere do texto foi ignorado;

(Rj-1 >>1): simula a substituio de um caractere do padro; (Rj-1 >>1): simula a remoo do prximo caractere do padro.

Quando o registrador Rj alcana o seu estado final, indica que ocorreu um casamento aproximado de padro.

Apesar de parecer um pouco complicado, este algoritmo pode ser implementado em poucas linhas, como mostra o cdigo a seguir. O funcionamento do mesmo similar ao mostrado no cdigo do Shift-And Exato.

long saaLinha(char *linha, char *padrao, int numLinha, int erro, int* ocorrencias) { int n = strlen(linha); int m = strlen(padrao); long Masc[MAX_CHAR]; long i, j, Ri, Rant, Rnovo; long R[NUM_ERROS + 1]; long comp = 0; *ocorrencias = 0;

// pre-processamento for (i=0; i

11

R[0] = 0; Ri = 1 > 1); Rant = R[j]; R[j] = Rnovo | Ri; comp++; } if ((Rnovo & 1) != 0) { imprimeResultado(linha, padrao, numLinha, i-(strlen(padrao))+2); (*ocorrencias)++; } } return comp; }

Algoritmo 4 - Shift-And Aproximado

3.1.2 Anlise A complexidade deste algoritmo de O(k[m/]n) no pior caso e no caso mdio onde o tamanho em bits de uma palavra, o que equivale a O(kn) para padres tpicos, isto m (ZIVIANI, 2004). J a complexidade de espao O(Km), onde K o nmero de erros, uma vez que so necessrio K autmatos com o tamanho do padro.

12

3.2 Programao Dinmica

3.2.1 Descrio

A soluo utilizando PROGRAMAO DINMICA considerada uma das mais antigas formas de resolver este problema. O algoritmo final atribudo a Sellers, em 1980, apesar de algoritmos deste tipo terem sido desenvolvidos vrias vezes desde 1960.

O algoritmo funciona da seguinte forma: uma matriz C0...m inicializada com valores Ci = i e ento o texto T processado caractere a caractere. A cada novo caractere tj, esta matriz atualizada para C0...m de acordo com a seguinte frmula:

(2)

e as posies do texto onde Cm k so reportadas como posies finais das ocorrncias.

Uma pequena modificao neste algoritmo reduz o seu tempo de processamento. A idia que, j que um determinado padro no ocorre normalmente em um texto, os valores de cada coluna lidos da do incio para o fim rapidamente alcana k+1 (i.e., no-casamento), e que se uma clula tem valor maior que k+1, o resultado da procura no depende de seu valor exato. Uma clula dita ativa se seu valor pelo menos k. O algoritmo mantm o contador da ltima clula ativa e evita trabalhar nas clulas subsequentes.

A seguir apresentamos a implementao do algoritmo de programao dinmica:

long pdLinha(char *linha, char *padrao, int numLinha, int erro, int* ocorrencias) { long comp = 0; int n = strlen(linha); int m = strlen(padrao); (*ocorrencias) = 0;

int C[1000]; int i, lact, pos, pC, nC;

13

// pre-processamento for (i=0; i

14

4 Experimentos .4#ALY\T A=4#]# 5^1 M _4_Y\T 5CKl"TIP_1_A,O#1_PQ1wm.1_6\T IP.m.4#J /Y\1_A,1_AN 4S'B(4#6=JRP_4_G[Y\1_A_-.F ,A= ALJKP.B_6=JRP_4_JK6\TIP_4_G} Y=4

Neste captulo iremos detalhar como foram feitos os experimentos. Inicialmente, apresentaremos como cada um desses algoritmos devem ser executados. E, na seo seguinte, apresentaremos os resultados experimentais obtidos e confrontaremos com a anlise feita anteriormente.

4.1 Execuo Para compilar todo o cdigo, digite:

> make

Para executar, obedea ao padro:

>./TP2

Caso o algoritmo selecionado seja para casamento exato, dispensvel o ltimo parmetro.

Para cada algoritmo disponvel, existe um cdigo associado. Abaixo listamos:

Algoritmo Cdigo

BMH 0

BMHS 1

Shift-And Exato 2

Shift-And Aproximado 3

Programao Dinmica 4

No arquivo que contm os padres, cada linha ser considerada como um padro a ser procurado.

15

4.2 Resultado Experimentais

4.2.1 Metodologia Aps implementarmos os algoritmos descritos, testamos todos eles com o intuito de compar-los e verificarmos se o resultado encontrado est de acordo com o esperado. Os experimentos foram realizados em uma mquina Intel Core 2 Quad 2.4Hz, 2Gb de memria ram. Apesar dos cdigos apresentados acima realizarem a busca em apenas uma linha, adaptamos os cdigos de todos os mtodos para que os mesmos realizem a busca em blocos de linhas. Dessa forma, diminumos sensivelmente a quantidade de chamada de funes, uma vez que os blocos tm 500 linhas cada. Nos testes consideramos os seguintes parmetros:

i. Tamanho do arquivo: foram utilizados quatro arquivos com tamanhos distintos (2,7 Mb, 9,8 Mb,19,9 Mb, 107 Mb);

ii. Padro: para facilitar a anlise dos resultados, nos testes utilizamos padres diferentes, porm com o mesmo tamanho (Em torno de quinze caracteres). Nas buscas, para cada algoritmo e para cada valor de k (erro), foram buscados 10 padres e calculada a mdia do nmero de comparaes e do tempo de execuo.

Como resultado dos testes, obtemos os seguintes dados: i. Tempo de execuo: o tempo de execuo foi medido dentro de cada funo,

evitando assim, que o tempo de leitura de arquivo influencie nas medies. O tempo de execuo foi calculado para cada bloco de texto. Cada um desses tempos parciais foram somados afim de se obter o tempo de execuo total. Na realizao de cada algoritmo, foram separados os comando relativos ao pr-processamento do padro. Estes foram realizados somente uma fez antes da realizao das buscas. Como o tempo de pr-processamento est em funo do tamanho do padro, e para os testes realizados o tamanho dos padres foram relativamente pequenos (15 caracteres) em se comparando com o tamanho dos textos. Para obter tais tempos, foi necessria a utilizao de uma funo com bastante preciso. No caso, a funo utilizada foi a gettimeofday(). Os tempos de pr-processamento calculados para os algoritmos, considerando inclusive os erros, se mostraram bastante aleatrios

16

para os mesmo parmetros de entrada da busca, ficando em mdia na ordem de 0,000000001.

ii. Quantidade de comparaes realizadas: foram consideradas apenas as comparaes entre um caracter do padro com um caracter do texto. No casamento aproximado, foram ainda computadas as comparaes realizadas para saber se o nmero de erros estava dentro do permitido;

4.2.2 Resultados

A seguir, apresentaremos os grficos com os resultados obtidos dos experimentos. Eles foram organizados de acordo com o nmero de erros alm de estarem sempre em funo do tamanho do texto a ser pesquisado (representado nos grficos pelo tamanho do arquivo em Megabits). Assim, para cada erro sero apresentados dois grficos:

Grfico com o tempo (segundos) de execuo dos algoritmos em funo do tamanho do arquivo (Grficos mpares apresentados a seguir);

Grfico com o nmero de comparaes dos algoritmos em funo do tamanho do arquivo (Grficos pares apresentados a seguir).

Vale salientar que, os algoritmos exatos aparecem apenas nos grficos cujo erro 0. Os grficos que comparam o tempo e o nmero de comparaes das so os grficos de 1 at 8, apresentados na prxima seo. Como mencionado anteriormente, os algoritmos possuem complexidade de tempo linear quando o tamanho da palavra constante. Isso foi comprovado atravs dos experimentos, apesar dos grficos darem a falsa impresso de que o crescimento no linear, pois o eixo x no est com os dados marcados proporcionalmente. Alm de se comparar o desempenho entre os algoritmos, foram gerados grficos para a comparao do desempenho de um algoritmo aproximado de acordo com o seu erro. Os Grficos 9 e 10 mostra essa comparao para o ShiftAnd Aprox. j os Grficos 11 e 12 so relativos ao de programao dinmica.

4.2.3 Grficos

17

Tempo X Tamanho do Arquivo

0

0,5

1

1,5

2

2,5

3

2,7 9,8 19,9 107tamanho do arquivo

tem

po (s)

BMH

BMHS

Shift-And Exato

Shift-And Aproximado

ProgramaoDinmica

Grfico 1 - tempo X tamanho do arquivo para erro = 0

Comparaes X Tamanho do Arquivo

0

50000000

100000000

150000000

200000000

250000000

2,7 9,8 19,9 107

tamanho do arquivo

n de

co

mpa

ra

es

BMH

BMHS

Shift-And Exato


ProgramaoDinmica

Grfico 2 - comparaes X tamanho do arquivo para erro = 0

18


0

0,5

1

1,5

2

2,5

3

3,5

4

4,5

5

1 2 3 4

tamanho do arquivo

tem

po (s) Shift-And Aproximado

ProgramaoDinmica


Comparaes X Tamanho de Arquivo

0

50000000

100000000

150000000

200000000

250000000

300000000

350000000

400000000


n de

co

mpa

ra

es


ProgramaoDinmica


19


0

1

2

3

4

5

6


n de

co

mpa

ra

es


ProgramaoDinmica


Comparao X Tamanho do Arquivo

0

50000000

100000000

150000000

200000000

250000000

300000000

350000000

400000000

450000000

500000000

2,7 9,8 19,9 107

tamanho do arquivo

n de

co

mpa

ra

es


ProgramaoDinmica


20


0

1

2

3

4

5

6

7

8

2,7 9,8 19,9 107

tamanho do arquivo

tem

po (s) ProgramaoDinmica



Comparaes X Tamanho do Arquivo

0

100000000

200000000

300000000

400000000

500000000

600000000

700000000


n de

co

mpa

ra

es

ProgramaoDinmicaShift-And Aproximado


21

Shift-And AproximadoTempo X Tamanho do Arquivo

0

1

2

3

4

5

6


tem

po

erro = 0erro = 1erro = 2erro = 3

Grfico 9 - tempo X tamanho ShiftAnd Aproximado

Shift-And AproximadoComparaes X Tamanho do arquivo

0

50000000

100000000

150000000

200000000

250000000

300000000

350000000

400000000

450000000

500000000


n de

co

mpa

ra

es


Grfico 10 N Comparaes X tamanho ShiftAnd Aproximado

22

Programao DinmicaTempo X Tamanho do Arquivo

0

1

2

3

4

5

6

7

8


tem

po (s)


Grfico 11 N Comparaes X tamanho Programao Dinamica

Programao DinmicaComparaes X Tamanho do Arquivo

0

100000000

200000000

300000000

400000000

500000000

600000000

700000000


n de

co

mpa

ra

es


Grfico 12 - tempo X tamanho Programao Dinamica

23

Conforme a anlise mostrada anteriormente dos algoritmos de busca aproximada, a complexidade deles est em funo do nmero de erros. Isso ficou comprovado com os experimentos, como os grficos mostram.

5 Sumrio ZIVIANI, Nivio. Projeto de Algoritmos: Com implementaes em Pascal e C. Pioneira Thomson Learning, 2 edio, 2004

Documents

Casamento de Padrão Com Busca Exata e Aproximada