I) Apresentação:
O objetivo deste trabalho prático
é avaliar diferentes algoritmos de casamento de padrões, tanto sob um ponto de
vista teórico, pela análise de complexidade de algoritmos, quanto de um ponto
de vista prático, pela avaliação e comparação empírica dos algoritmos e entre
si, com o AGREP [AGREP], e os programas da família GREP [GREP], programas tradicionais, disponíveis para uso em
diversos ambientes.
II) Algoritmos e Estruturas de Dados:
II.1) Algoritmo
Boyer-Moore-Horspool – BMH:
Algoritmos de casamento de padrões
buscam, num texto de tamanho n, as diferentes ocorrências de um padrão
de tamanho m. O algoritmo mais simples para o casamento de padrões usa o
processo de força bruta: a idéia básica é comparar cada substring de
tamanho m com o padrão. Um algoritmo deste tipo seria como o que se
segue:
(1) void ForcaBruta
(texto, n, padrao, m) {
(2) int i, j,
k;
(3) char *texto, *padrao;
(6) for (i=0; i<n-m+1; i++) {
(7) for (j=0, k=i; (j<m) &&
texto[k]==padrao[j]; j++) k++;
(8) if (j>m) printf(“Padrao achado em %d\n”,i);
(9) }
(10)}
A idéia básica do algoritmo BMH é otimizar as linhas (6) e (7), observando que, ao caminhar na comparação do texto com o padrão, o algoritmo obtém informação sobre o texto que está sendo pesquisado. O algoritmo pode tirar partido desta informação para que, uma vez que ocorra uma falha numa comparação em (7), a linha (6) possa passar para um ponto mais à frente no texto, em lugar de avançar de um em um (i++).
A estrutura geral do algoritmo BMH é a seguinte:
(1) void BMH
(texto, n, padrao, m) {
(2) int i, j,
k;
(3) char *texto, *padrao;
(4) for( k=0;
k<ALPHABET_SIZE; k++ ) skip[k]= m;
(5) for( k=0;
k<m-1; k++ ) skip[pat[k]]= m-k-1;
(6) for(
i=m-1; i<n; i+=skip[texto[i]]) {
(7) for(j=m-1, k=i; j>=0 &&
texto[i]==padrao[j]; j--) k--;
(8) if (j==(-1)) printf(“Padrao achado em
%d\n”,i);
(9) }
(10)}
Neste algoritmo, ALPHABET_SIZE
indica o número de caracteres no alfabeto, texto é o texto
no qual o padrão padrao é pesquisado, n é o
tamanho do texto, e m
o tamanho do padrão. O vetor skip é usado
para controlar os saltos adiante no texto, quando ocorre uma falha na
comparação do padrão. As linhas (4) e (5) fazem a inicialização de skip.
O núcleo do algoritmo BMH, nas
linhas (6) a (9) é muito similar ao algoritmo
ForcaBruta, mas contém as otimizações que o tornam mais eficiente. A
linha (6) de BMH varre o texto. Note que, ao contrário da linha (6) de
ForcaBruta, o caminhamento no texto se inicia na posição m-1, porque
BMH faz as comparações da direita para a esquerda, e m-1 aponta
para o final do padrão. Além disto skip é usado
para avançar i mais rapidamente que na ForcaBruta.
A linha (7) de BMH é similar à
linha (7) de ForcaBruta . A principal diferença é que, em BMH, o caminhamento
se faz da direita para a esquerda. Portanto, os limites do for
se iniciam à direita do padrão, e caminham em direção à esquerda. Por
fim, o teste de padrão encontrado, na linha (8), passa a verificar se a
variável de controle transbordou para a esquerda, e não para a direita,
já que ela assume, em BMH, valores decrescentes.
O grande segredo reside, então no
cálculo e preenchimento prévios do vetor skip, que
controla os saltos adiante no texto. Este cálculo é baseado na heurística de ocorrência,
segundo a qual, na ocorrência de uma falha, deve-se alinhar o caractere do
texto que causou a falha com o primeiro caractere do padrão que combine com o
mesmo. No caso deste caractere não estar presente no padrão, pode-se alinhar o
padrão imediatamente após o caractere que causou a falha. Formalmente:
skip[x]
= { min ( s | s=m+1 ou (1 <= s <=
m e padrao[m+1-s] = x) }
A linha (4) preenche skip com o
valor inicial m+1. Em seguida, a linha (5) varre skip da
esquerda para a direita, preenchendo-o com valores cada vez menores (m-k-1,
k crescente) para cada caractere do padrão.
II.2) Algoritmo Wu-Manber:
O algoritmo Wu-Manber [WU92] deriva do algoritmo ShiftOr, proposto por Baeza-Yates
e Gonnet em [GBY89]. A idéia fundamental é representar o padrão a
pesquisar como um autômato finito. Neste autômato, as transições ocorrem quando
se aceita um caractere do texto que case com um caractere do padrão, e os
estados indicam quais caracteres já foram recebidos até o momento. Quando se
atinge um estado final, o padrão foi encontrado.
A eficiência do algoritmo se deve
à implementação projetada por seus autores: os estados, e os estados
alcançáveis são representados por máscaras de bits, toda a manipulação de
estados se fazendo por meio de operações lógicas e aritméticas. Então, se
usarmos padrões pequenos, poderemos representar as máscaras e estados
alcançáveis como palavras da arquitetura alvo onde o algoritmo for
implementado.
Certamente esta abordagem
restringe a dimensão dos padrões que podem ser pesquisados. Os autores do
algoritmo argumentam que, no caso de manipulação de textos, esta limitação não
reduz a utilidade do algoritmo, porque, freqüentemente, os padrões buscados são
pequenos.
Este algoritmo também é capaz de
lidar com busca aproximada, que permite erros. A implementação da busca
aproximada, aceitando erros é relativamente simples. Basta estender o autômato
para incluir transições espontâneas. Cada transição espontânea indicará um
erro: troca ou supressão de caractere. A figura abaixo, extraída das notas de
aula, mostra uma visão esquemática de um autômato para o padrão ABCA aceitando
até dois erros:
A estrutura geral do algoritmo é a seguinte:
( 1) void
WM_Exec(p, m, t, n, k) {
( 2) int i,
j,
( 3) R0[MAX_NUMBER_OF_ERRORS],
( 4)
R1[MAX_NUMBER_OF_ERRORS],
( 5) S
[ALPHABET_SIZE],
( 6)
Start[MAX_NUMBER_OF_ERRORS]
( 8) for (i =
0; i <= k; i++) {
( 9)
Start[i] = 0;
(10) for (j
= 0; j <= i; j++)
(11)
Start[i] |= 1 << (m - j);
(12) }
(13) for (i =
0; i < ALPHABET_SIZE; i++)
(14) S[i] =
0;
(16) for (i =
0; i < m; i++) { {
(17)
S[p[i]] |= 1 << (m - 1 - i);
(19) }
(20) for (i =
0; i <= k; i++) {
(21) R1[i]
= Start[i];
(22) R0[i]
= Start[i];
(23) }
(24) for (i = 0; i < n; i++) {
(25) R1[0] =((R0[0] >> 1)& S[t[i]])
| (Start[0] & (R0[0]);
(26) for (j
= 1; j <= k; j++) {
(27) R1[j] = ((R0[j] >> 1) &
S[t[i]]) |
(28) ((R0[j-1] |
((R1[j-1]|R0[j-1])>>1)) ) |
(29)
(Start[0] & R0[j]);
(30) }
(31) for (j
= 0; j <= k; j++)
(32) R0[j] = R1[j];
(33) if (R1[j]&1) printf(“Padrao achado em %d\n”,i);
(34) }
(35) }
(36) }
Neste algoritmo, as linhas de (8) a (23) efetuam inicializações, e as linhas de (24) a (35) efetuam a busca, ALPHABET_SIZE indica o número de caracteres do alfabeto, p é o padrão, e m seu tamanho, t é o texto, e n seu tamanho, k é o número de erros a aceitar. R0 indica o estado anterior, e R1 o atual. Start contém o valor inicial deste estado, calculado na inicialização. Todos os três são vetores, com uma posição para cada número de erros a aceitar (0=sem erros, 1=1 erro, k=k erros). S é um vetor de máscaras, uma para cada caractere do alfabeto, e que indica onde cada caractere ocorre no padrão.
As linhas (8) a (12) calculam o
valor de Start, que será
usado para inicializar R0 e R1 nas
linhas (20) a (23). Estas linhas calculam, para cada número de erros a aceitar,
o valor inicial do estado do algoritmo, da seguinte forma:
·
Para busca exata (sem erros, k=0), o m-ésimo bit em 1. Ex:
para m=3, teremos Start[0] = 8 (1000 em binário);
·
Para busca com erros, os k-ésimos bits à Start[i] em 1, a
partir do m-ésimo, para cada 1<= i <=k. Ex: para m=3, Start[1]= 12 (1100
em binário), Start[2]= 14 (1110 em binário).
As linhas (13) a (19) calculam S, vetor de
máscaras que indicam, para cada caractere do alfabeto, em que posição do padrão
o caractere se encontra.
Nas linhas (24) a (36) está o
núcleo do algoritmo. R0 (estado anterior), e R1
(estado atual) são registradores contém um bit para cada estado do
autômato correspondente ao padrão. Cada bit em 1 indica quais estados podem ser
alcançados a partir do estado atual. Um novo estado é calculado a partir do
estado anterior, dado por R0, do estado atual, dado por R1
e das posições em que o caractere em exame ocorre no padrão, dadas por S:
·
Na linha (25) calcula-se o novo estado do registrador para
casamento sem erros, Este valor é obtido verificando-se se o próximo estado
poderá ser ativado pelo caractere corrente;
·
Nas linhas (26) a (30) faz-se o cálculo dos novos estados
dos registradores para cada número de erros. Para tanto, verifica-se se o
próximo estado poderá ser ativado pelo caractere corrente (27), por transição
expontânea a partir do estado anterior com remoção, adição ou substituição de
um caractere.
III) Análise de Complexidade:
III.1) Algoritmo
Boyer-Moore-Horspool – BMH:
Sejam n o tamanho do texto, m o tamanho do padrão e c a dimensão do alfabeto. A complexidade de inicialização leva em conta as linhas (4) e (5) do algoritmo. A linha (4) tem sua complexidade dependente da dimensão do alfabeto, e o custo de execução da linha (5) depende diretamente do tamanho do padrão. O custo total de inicialização será, então, O(c) + O(m) = O(m + c).
Em termos de espaço, temos o custo para armazenar o vetor de deslocamentos skip: O(c).
O custo de execução depende da probabilidade de se encontrar o padrão pesquisado, de sua localização, da freqüência com que ocorre. Também depende da própria estrutura do padrão, e também da estrutura do texto, que afetam a possibilidade de se efetuarem os saltos responsáveis pelo bom desempenho do algoritmo.
Se considerarmos um caso em que o padrão tenha todos os caracteres iguais, e que o texto somente contenha apenas este mesmo caractere:
· Não ocorrerão saltos, e a linha (6) será executada n-m+1 vezes.
· A linha (7) será executada m vezes.
· Serão executadas nm-m2+m comparações. Considerando que m é muito menor que n, temos o pior caso apresentado em [FBY], que é O(n*m).
A análise do custo esperado exige a elaboração de um modelo probabilístico, como o que é apresentado em [BM] e em [BGM], e que permitem chegar a um custo médio, para m muito menor que n, de O(n/m).
III.2) Algoritmo Wu-Manber:
Sendo k o número de erros aceito, e c a dimensão do alfabeto, a complexidade em espaço, conforme as linhas (3) a (6) é 3k+2c.
Sendo m o tamanho do padrão, a complexidade de inicialização é:
· Linhas (8) a (12): (k+1) + (k+1)(k+2)/2 = (k+1) +(k2 + 3k + 2)/2 = k2/2+ 5k/2 + 2
· Linhas (13) a (14): c
· Linhas (16) a (19): m
· Linhas (20) a (23): 2k+2
· Complexidade de inicialização: k2/2+ 9k/2 + 4 + c + m
Sendo n o tamanho do texto, w o tamanho da palavra do computador alvo, e sendo m < w, a complexidade de execução é:
· Linha (24): n
· Linha (25): O(1)
· Linhas (26) a (34): 2*O(k) = O(k)
· Complexidade de execução: O(n*k)
IV) Avaliação Empírica:
Algoritmos
e programas avaliados: Em nossa avaliação, efetuamos diversos experimentos e medições, a fim
de montar um panorama consistente e amplo das características e desempenho dos
algoritmos implementados (Wu-Manber e Boyer-Moore-Horspool), e de seu
comportamento quando comparado a dois programas disponíveis para uso geral, o AGREP
[AGREP] e os programas da família GREP [GREP].
Ambiente
de testes: Os
experimentos foram feitos num notebook Toshiba Satellite S201, com cpu
Pentium de 1,6GHz e 256MB de
memória, executando Windows XP Professional. O ambiente de software usado
foi usado o ambiente Cygwin [CYGWIN].
Massa
de dados para testes: A massa de dados empregada foi a indicada na proposição do trabalho
prático [[TP3]], e disponível na rede do DCC. Esta massa de dados
inclui arquivos de 2, 10, 20 e 100 MB.
Modalidade
de medição de tempo adotada: As medições de tempo consideraram o tempo decorrido.
Embora este tipo de medição implique em certa imprecisão na medida, ele permite
considerar os tempos de execução dos algoritmos, e também os tempos de entrada
e saída que, no caso de pesquisa em arquivos, são componentes muito
significativos do tempo total de execução[1].
Foram
efetuados experimentos com relação aos tempos de entrada e saída, tanto para a
leitura de arquivos, quanto para a emissão de resultados. Com isto, pudemos
avaliar a influência destes tempos nos resultados encontrados.
IV.1) Medições de Entrada e Saída:
O gráfico Tempo de Leitura de
Arquivos mostra as medições efetuadas com a leitura dos mesmos arquivos
empregados nos testes de desempenho dos algoritmos. Foram efetuados testes com
dois tipos de leitura:
·
Leitura blocada, com registros de tamanho fixo, e chamadas open,
read, close;
·
Leitura com stream, com chamadas fopen, fgets,
fclose, que trata registros de tamanho variável, delimitados por “\n” (Os
arquivos da massa de testes são estruturados desta forma).
Os tempos obtidos mostram um fato
notável: a leitura blocada se mostrou ligeiramente mais lenta que a leitura
stream. Acreditamos que estes resultados estejam muito ligados a
peculiaridades de sistema operacional e compilador (como é típico das
implementações de mecanismos de entrada e saída). Portanto, ao portar o software
para outras plataformas, torna-se muito importante repetir estas medições, a
fim de usar o mecanismo mais adequado à plataforma alvo.
Por fim, podemos considerar os
tempos de leitura por stream como um limite inferior para o tempo de
execução de todos os algoritmos testados. Em particular, podemos considerar o
tempo de cerca de 6s como um limite inferior para algoritmos de busca no
caso do arquivo wsj88, de cerca de 100 MB
IV.2)
O programa desenvolvido - RGREP:
Para
a efetivação dos testes, foi desenvolvido o programa RGREP. O programa usa
algoritmos disponíveis em [[TP3]] e [GBY]. Este programa seleciona o algoritmo de pesquisa
conforme o tipo de pesquisa solicitada (com ou sem erros). Foram incluídas
diversas facilidades no programa que o tornam muito similar a um programa útil
e competitivo na vida real. Foram tomados diversos cuidados na implementação
para evitar falhas e comportamentos que dificultariam o uso efetivo do
programa.
Dentre
os pontos levados em conta na implementação, e que tornam o programa
competitivo, citamos:
·
Interface
compacta, de linha de comando, padrão em aplicativos e ferramentas Unix,
incluindo opções de ativação similares às dos aplicativos GREP e AGREP, capaz
de tratar arquivos na entrada padrão, e que inclui uma opção de ajuda (que
explica de forma sucinta o funcionamento do programa).
·
Cuidados
para evitar erros de buffer overflow, especialmente na alocação e
manipulação de registros e argumentos, causa freqüente de falhas inesperadas e
falhas de segurança nos mais variados sistemas.
·
Estruturação
e documentação cuidadosas do código, como forma de aumentar legibilidade de
manutenibilidade.
Embora
acreditemos que o programa possa ser usado efetivamente, certos pontos da
implementação não foram abordados em profundidade, e devem ser revistos:
·
Como
se verá adiante, a implementação de AGREP para busca com erros é muitíssimo
mais eficiente. Isto mostra que a implementação que usamos para a pesquisa com
erros (Wu-Manber em [TP3]) deve ser revista.
·
A
pesquisa de múltiplos padrões (opção –f) foi implementada de forma
ineficiente, que requer o re-processamento de padrões cada vez que se lê uma
linha do arquivo alvo. Esta implementação pode ser facilmente modificada para
evitar este re-processamento. Também é importante avaliar versões de algoritmos
especialmente adaptadas para a busca de múltiplos padrões. Variações de
algoritmos para casamento de múltiplos padrões podem ser vistos em [WU94] e em [CW].
·
O
processo de leitura de arquivos não faz uso de nenhuma otimização nem de
leitura antecipada de dados. A grande diferença de tempo que observamos entre
nosso programa, quando efetuando busca com erros, e AGREP, sugere que este
aspecto deva ser investigado.
·
O
programa AGREP limita a busca com erros a um máximo de 8 erros. Isto sugere que
exista alguma otimização, ou melhoria de desempenho significativa, para
operações em 1 byte, o que deve ser verificado.
·
Uma
extensão importante é permitir a especificação de padrões como expressões
regulares.
·
Seria
interessante avaliar o variação do algoritmo BMH proposta em [SUNDAY], que mais compacta, e apresenta algumas otimizações
em relação à versão usada por RGREP.
Desempenho: Os
gráficos RGREP-Wu-Manber e RGREP-
BMH x Wu-Manber exato mostram o desempenho global do programa para diversas
situações. Foram efetuadas buscas com strings de 3, 8 e 23 bytes,
e com 1, 4, 8 e 28 erros. Os gráficos mostram que, como esperado, os tempos de
execução crescem linearmente com relação ao tamanho do padrão, com relação ao
número e erros, e com relação ao tamanho do arquivo.
No caso de Wu-Manber, se
considerarmos linear a relação entre número de erros e tempo de execução, teremos:
- Para 1 erro: T(x)= 0,0001x + 0,2162
- Para 28 erros: T(x)= 0,0018x + 0,1723
Então, a pesquisa com 28 erros
pode ficar inviável para arquivos de 1 GB (cerca de 1800 segundos), mas viável
para 1 erro (cerca de 100 segundos).
No caso de Boyer-Moore-Horspool, o
tempo é menor para padrões maiores:
- Para padrões de 3 bytes: T(x) =
0,00007x + 0,0655
- Para padrões de 23 bytes: T(x) =
0,00006x + 0,2185
A
pesquisa sem erros é, então, viável mesmo para arquivos da ordem de 1GB (cerca
de 70 segundos para padrões de 3 bytes)
IV.3) Comparação com GREP:
Foram efetuadas buscas com padrões
de 3, 8 e 23 bytes. Os gráficos a seguir apresentam os resultados obtidos.
Estes gráficos mostram que o tempo de execução de RGREP para pesquisa exata, com o algoritmo Boyer-Moore-Horspool, depende linearmente do tamanho do arquivo. Se desprezarmos os experimentos com padrões de 8 bytes, teremos uma confirmação de que o tempo é inversamente proporcional ao tamanho do padrão. Em síntese, confirma-se que o caso médio é O(mn), onde m é o tamanho do padrão, n o tamanho do arquivo, e n muito maior que m.
A busca exata com Wu-Manber também cresce linearmente com respeito ao tamanho do arquivo, e é muito eficiente. Os experimentos não permitem uma conclusão segura sobre a relação entre tamanho do padrão e o tempo de execução.
Por fim, pode-se concluir que as implementações de busca exata de RGREP são muito competitivas e freqüentemente mais rápidas que a versão de GREP avaliada.
IV.4) Comparação com AGREP:
Foram efetuadas buscas com 1, 4 e
8 erros (o limite de AGREP para buscas aproximadas é de 8 erros), e buscas
exatas com padrões de 3, 8 e 23 bytes. O gráfico a seguir apresenta os
resultados obtidos na busca com erros. Os três gráficos anteriores, em IV.3,
incluem os resultados para busca exata.
Programa
AGREP: As
comparações demonstram as qualidades do AGREP. Seus resultados são muito
competitivos tanto para a busca com erros, quanto para a busca exata. No caso
da busca com erros, os resultados mostram claramente que seu tempo de execução
depende linearmente do tamanho do arquivo.
O
resultados também mostram que existe alguma dependência entre o número de erros
e o tempo de execução, mas os experimentos são insuficientes para caracterizar
perfeitamente qual a dependência. Aparentemente, o tempo de execução é
diretamente proporcional ao número de erros, o que confirma os resultados
teóricos em [WU92] (O(nk)).
O
resultado de AGREP é ainda mais surpreendente se compararmos seu tempo de
execução com o tempo para leitura de arquivos com stream, mostrado em IV.1.
Seu tempo de execução está muito próximo ao ali calculado. Este fato, aliado ao
fato de que o limite de erros de AGREP para busca aproximada é 8, sugere que
ele use algum tipo de otimização baseada em operadores de byte.
Programa RGREP para busca
aproximada: Os gráficos mostram que o crescimento do tempo de execução é
diretamente proporcional ao tamanho do arquivo e ao número de erros.
A busca aproximada é a situação em
que o programa RGREP, usando o algoritmo Wu-Manber, exibe seu pior
desempenho, muito inferior ao de AGREP.
De fato os tempos de execução tornam o programa inadequado para arquivos muito
grandes (conforme mostrado em IV.2, o tempo previsto para uma busca com
28 erros num arquivo de 1 GB é de cerca de 1800 segundos).
Programa RGREP para busca exata: Os
gráficos mostram que o crescimento do tempo de execução de RGREP com algoritmo
Boyer-Moore-Horspool para busca exata, é diretamente proporcional ao tamanho do
arquivo e ao número de erros. Também mostram que o tempo é inversamente
proporcional ao tamanho do padrão, o que é esperado (O(n/m), conforme
notas de aula).
A busca exata em RGREP com Wu-Manber também tem tempo de execução diretamente proporcional ao tamanho do arquivo. Não foi possível determinar qualquer relação entre tempo de execução e tamanho do padrão.
Por fim, a busca exata com RGREP é
competitiva, quando comparada com AGREP.
IV.6) Sabores de GREP: O
utilitário GREP, tradicional em sistemas Unix e Linux, e disponível para download
em [GREP], pode ser invocado de três maneiras distintas:
·
GREP: A versão tradicional, capaz de casamento de padrões
com expressões regulares;
·
EGREP: Uma versão estendida, capaz de aceitar, em sua linha
de comando, múltiplas expressões regulares;
·
FGREP: Uma versão reduzida, capaz de tratar padrões fixos,
sem expressões regulares, similar a RGREP.
O sabor escolhido para as
comparações foi GREP. Mostramos, abaixo, um gráfico com tempos de execução dos
três sabores que mostra que, embora GREP nem sempre seja o sabor
mais eficiente, todos são muito similares entre si:
IV.7) Tabelas de dados: A seguir,
temos as tabelas de dados usadas para gerar os gráficos acima.
|
Tempo de
leitura de arquivos |
|
|
||
|
Arquivo |
KBytes |
Linhas |
Stream |
Blocado |
|
wsj89 |
2.756 |
43.494 |
0,25 |
0,4 |
|
wsj88_10 |
9.901 |
140.539 |
0,73 |
0,6 |
|
wsj88_20 |
19.804 |
278.933 |
1,16 |
1,21 |
|
wsj88 |
106.885 |
1.523.893 |
5,77 |
7,4 |
|
Comparação entre RGREP e AGREP, aceitando erros |
|||||||||
|
Arquivo |
KBytes |
Linhas |
RGREP 1 erro |
AGREP 1 erro |
RGREP 4 erros |
AGREP 4 erros |
RGREP 8 erros |
AGREP 8 erros |
RGREP 28 erros |
|
wsj89 |
2.756 |
43.494 |
0,57 |
0,34 |
0,89 |
0,25 |
1,52 |
0,74 |
5,29 |
|
wsj88_10 |
9.901 |
140.539 |
1,08 |
0,64 |
3,01 |
0,61 |
5,24 |
1,2 |
17,85 |
|
wsj88_20 |
19.804 |
278.933 |
2,19 |
1,15 |
5,92 |
1,2 |
10,42 |
2,19 |
35,52 |
|
wsj88 |
106.885 |
1.523.893 |
10,74 |
6,05 |
31,7 |
5,94 |
56,95 |
11,27 |
191,74 |
|
Comparação
entre RGREP e AGREP, padrão de 3 bytes |
||||||||
|
Arquivo |
KBytes |
Linhas |
RGREP |
AGREP |
GREP |
FGREP |
EGREP |
RGREP-WM |
|
wsj89 |
2.756 |
43.494 |
0,4 |
0,44 |
0,35 |
0,42 |
0,46 |
0,19 |
|
wsj88_10 |
9.901 |
140.539 |
0,55 |
0,53 |
0,63 |
0,53 |
0,53 |
0,63 |
|
wsj88_20 |
19.804 |
278.933 |
1,43 |
1,17 |
1,21 |
1,46 |
1,37 |
1,21 |
|
wsj88 |
106.885 |
1.523.893 |
7,29 |
6,76 |
7,09 |
7,19 |
6,8 |
6,51 |
|
Comparação
entre RGREP e AGREP, padrão de 8 bytes |
||||||||
|
Arquivo |
KBytes |
Linhas |
RGREP |
AGREP |
GREP |
FGREP |
EGREP |
RGREP-WM |
|
wsj89 |
2.756 |
43.494 |
0,22 |
0,4 |
0,38 |
0,19 |
0,22 |
0,29 |
|
wsj88_10 |
9.901 |
140.539 |
0,68 |
0,54 |
0,59 |
0,67 |
0,54 |
0,56 |
|
wsj88_20 |
19.804 |
278.933 |
1,17 |
1,2 |
1,26 |
1,19 |
1,27 |
1,29 |
|
wsj88 |
106.885 |
1.523.893 |
6,71 |
6,31 |
6,71 |
6,45 |
6,4 |
6,36 |
|
Comparação
entre RGREP e AGREP, padrão de 23 bytes |
||||||||
|
Arquivo |
KBytes |
Linhas |
RGREP |
AGREP |
GREP |
FGREP |
EGREP |
RGREP-WM |
|
wsj89 |
2.756 |
43.494 |
0,32 |
0,33 |
0,38 |
0,23 |
0,19 |
0,22 |
|
wsj88_10 |
9.901 |
140.539 |
0,62 |
0,54 |
0,59 |
0,57 |
0,58 |
0,57 |
|
wsj88_20 |
19.804 |
278.933 |
1,64 |
1,41 |
1,26 |
1,13 |
1,15 |
1,12 |
|
wsj88 |
106.885 |
1.523.893 |
6,42 |
5,77 |
6,71 |
5,93 |
5,91 |
6,37 |
|
RGREP - Geral |
|||||||
|
BMH |
Arquivo |
KBytes |
Linhas |
3 bytes |
8 bytes |
23 bytes |
|
|
|
wsj89 |
2.756 |
43.494 |
0,4 |
0,22 |
0,32 |
|
|
|
wsj88_10 |
9.901 |
140.539 |
0,55 |
0,68 |
0,62 |
|
|
|
wsj88_20 |
19.804 |
278.933 |
1,43 |
1,17 |
1,64 |
|
|
|
wsj88 |
106.885 |
1.523.893 |
7,29 |
6,71 |
6,42 |
|
|
|
|
|
|
|
|
|
|
|
WU |
Arquivo |
KBytes |
Linhas |
1 erro |
4 erros |
8 erros |
28 erros |
|
|
wsj89 |
2.756 |
43.494 |
0,57 |
0,89 |
1,52 |
5,29 |
|
|
wsj88_10 |
9.901 |
140.539 |
1,08 |
3,01 |
5,24 |
17,85 |
|
|
wsj88_20 |
19.804 |
278.933 |
2,19 |
5,92 |
10,42 |
35,52 |
|
|
wsj88 |
106.885 |
1.523.893 |
10,74 |
31,7 |
56,95 |
191,74 |
|
|
|
|
|
|
|
|
|
|
WU-EXATO |
Arquivo |
KBytes |
Linhas |
3 bytes-WM |
8 bytes-WM |
23 bytes-WM |
|
|
|
wsj89 |
2.756 |
43.494 |
0,19 |
0,29 |
0,22 |
|
|
|
wsj88_10 |
9.901 |
140.539 |
0,63 |
0,56 |
0,57 |
|
|
|
wsj88_20 |
19.804 |
278.933 |
1,21 |
1,29 |
1,12 |
|
|
|
wsj88 |
106.885 |
1.523.893 |
6,51 |
6,36 |
6,37 |
|
BIBLIOGRAFIA:
[AGREP] http://www.tgries.de/agrep/
[BGM] Baeza-Yates,
R.A., Gonnet, G.H., Régniert, M., Analysis of Boyer-Moore-Type String
Searching Algorithms, Proceedings of the first annual ACM-SIAM symposium on
Discrete algorithms, Januarry 1990.
[BM] Boyer,
R. S., Moore, J. S., A Fast String Searching Algorithm, CACM, V20(10),
762-772, 1977.
[CW] Commentz-Walter, B., A string matching algorithm
fast on the average. In ICALP,
Lecture Notes in Computer Science, vol. 6. Springer-Verlag, 1979, pp. 118-132.
[FBY] Frakes, W. B. e Baeza-Yates (Eds) Information Retrieval Data Structures
and Algorithms. Prentice Hall, 1992
[GBY] http://www.dcc.uchile.cl/~rbaeza/handbook/
algs/7/713b.srch.c.html
[GBY89] G. H.
Gonnet e R. Baeza-Yates, A New Approach to Text Searching, ACM SIGIR Forum, Proceedings of the twelfth annual
international ACMSIGIR conference on Research and development in information
retrieval May 1989.
[GBY91] G. H.
Gonnet e R. Baeza-Yates, Handbook of Algorithms and Data Structures,
Addison-Wesley, 1991, 2ª edição.
[CYGWIN] http://www.cygwin.com
[GREP] http://www.gnu.org/software/grep/grep.html
[SUNDAY] D. M.
Sunday, A Very Fast Substring Search Algorithm, CACM, 33(8), 132-42,
1990
[TP3] http://www.dcc.ufmg.br/~nivio/cursos/pa02/tp3/pa02tp3.html
[WU92] S.
Wu, U. Manber, Fast Text Searching Allowing Errors, CACM, October 1992,
Vol35 No 10
[WU94] S.
Wu, U. Manber, A Fast Algorithm for Multi-Pattern Search, Technical Report TR-94-17,
Department of Computer Science, University of Arizona, 1994