%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{float}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}

%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{algorithmic}

\usepackage{babel}
\makeatother
\begin{document}

\title{Projeto e Análise de Algoritmos}


\title{3º Trabalho Prático}


\author{Tiago Alves Macambira < tmacam@dcc.ufmg.br >}


\date{16 de Julho de 2003}

\maketitle

\section{Os algoritmos}

A seguir, explicaremos sucintamente o funcionamento dos 3 algoritmos
implementados.


\subsection{Boyer-Moore-Horspool}

Como o Cormen et al\cite{cormenalg} dizem, o algoritmo de Boyer-Moore
é muito semelhante ao de força bruta em sua estrutura. Contudo, uma
diferença inicial marcante é o fato de que o algoritmo de BM verifica
casamentos com a cadeia de trás para frente no padrão, ao contrário
do de força bruta, que verifica casamentos entre o texto e a cadeia
de frente para trás. Todavia, isso somente não é o responsável pela
difenrença de complexidade entre os dois algoritmos. BH faz uso de
heurísticas que permitem que muito do trabalho do algoritmo de força
bruta seja evitado.

O algoritmo de Boyer-Moore-Horspoll, a mais importante simplificação
de Boyer-More, consegue melhorar o desempelnho do algoritmo original
evitando o tempo de escolha entre que heurística tomar. Seu grande
trunfo está na função de avanço $\lambda$, definida como:

\[
\lambda[x]=\min\{ j|(j=m)\wedge((1\leq j<m)\vee(P[m-j]=x))\}\]


Sempre que no laço $while$interno não for encontrado um casamento,
o algoritmo de BMH verifica qual é, naquele momento, o $i$-ésimemo
caractere no texto, correspondente ao último caractere do padrão.
Dado esse caractere, verifica-se qual será sua imagem na função $\lambda$.
Essa informação diz quanto o padrão deveria andar para casar esse
$i$-ésimo caractere no texto com um póssível caractere igual a este
no padrão. Se este $i$-ésimo caractere nem sequer estiver presente
no padrão, o algotitmo andará $m$caracteres.Vê-se facilmente então
porquê o melhor caso desse algoritmo é $O(n/m)$. Esse também é o
caso médio desse algoritmo, o que explica porque ele é tão atraente.

%
\begin{algorithm}

\caption{BuscaForcaBruta(T,P)}

\begin{algorithmic}

\STATE $n \leftarrow tamanho(T)$

\STATE $m \leftarrow tamanho(P)$

\FOR{$x \leftarrow 0..n-m$}

\IF{$P[1..m]=T[s+1..s+m]$}

\STATE imprima "Casamento em",$s$

\ENDIF

\ENDFOR

\end{algorithmic}
\end{algorithm}


%
\begin{algorithm}

\caption{AlgoritmoBMH}

\begin{algorithmic}

\STATE $n \leftarrow tamanho(T)$

\STATE $m \leftarrow tamanho(P)$

\STATE $\lambda \leftarrow $Função de avanço

\STATE $i \leftarrow m$

\WHILE{$i \leq n$}

\STATE $k \leftarrow i$

\STATE $j \leftarrow m$

\WHILE{$((j \geq 0)^(T[k])=P[j])$}

\STATE $k \leftarrow k-1$

\STATE $j \leftarrow k-1$

\ENDWHILE

\IF{$j<0$}

\STATE imprima "Casamento em",$k+1$

\ENDIF

\STATE $i = i + \lambda[T[i]]$

\ENDWHILE

\end{algorithmic}
\end{algorithm}



\subsection{Shift-And}

A idéia é simples: com um autômata finito determinítico ( DFA ) consegue-se
em tempo $\Theta(n)$\cite{cormenalg} verificar se existe ou não
um casamento para o padrão $P$no texto $T$. A construção de tal
autômato, no entanto, pode ser bastante dispendiosa se o alfabeto
$\Sigma$ usado por $T$ e $P$ for grande.

Knuth, Morris e Pratt foram os primeiros a vir com um algoritmo eficiente
para o problema de \emph{string matching} e o fizeram utilizando idéias
baseadas em autômatos. Nesse caso, em um 2DPDA ( 2-way Deterministic
Pushdown Automata ). Esse algoritmo, no entanto não é tão eficiente
quanto o BMH e o que interessa aqui é falar do Shift-And. Cortemos
o leriado e vamos falar logo dele.

O algoritmo Shift-And simula de forma bem interessante um NDFA (Non-Deterministic
DFA) limitado para fazer o casamento de padrões em texto. Seu grande
atrativo é que com pouquíssimas alterações é possível, com ele, fazer
buscas aproximadas.

Ele utiliza o paralelismo de bits das palavras de um computador, de
forma muito engenhosa. tanto para representar as transições possíveis
entre estados como para representar o próprio estado do autômata (estados
ativos). De maneira análoga ao BMH, existe um pré-processamento que
deve ser feito com o padrão de busca $P$, a um custo $O(m)$. Este
pré-processamento consiste em criar uma tabéla contendo a \emph{máscara
de bits} de cada caractere no padrão. Para um caractere $i$ no padrão,
a sua máscara $\lambda(i)$ é definida como:

\[
\lambda(i)=b_{m}^{i}b_{m-1}^{i}...b_{1}^{i},\]
onde

\[
b_{p}^{j}=\left\{ \begin{array}{ccc}
1, & se & P[p]=i\\
0 & se & P[p]\neq i\end{array}\right.\]


Uma fez feito isso, e tendo que $m\ll n$, o custo do algoritmo se
resume a alimentar o \emph{autômato com o texto},$O(n)$. A notação
usada no algoritmo segue a definida pelo professor: exponenciação
significa repetição de um dado numero, por exemplo: $0^{3}1^{2}0^{3}=00011000$.

%
\begin{algorithm}

\caption{Shift-And Exato}

\begin{algorithmic}

\STATE $\lambda \leftarrow $Função de máscara de bits

\STATE $R \leftarrow 0^{m}$

\FOR{$i \leftarrow 0..n-m$}

\STATE $R \leftarrow ((R\ll 1)\wedge10^{m-1})\vee \lambda[T[i]]$

\IF{$R\vee 0^{m-1}1\neq 0^{m}$}

\STATE imprima "Casamento em",$i-m+1$

\ENDIF

\ENDFOR

\end{algorithmic}
\end{algorithm}



\subsection{Shift-And Aproximado}

Como dito na sub-seção anterior, o algoritmo shift-and pode ser modificado
para incluir busca aproximada. Tal é feito acrescentando mais registradores
($R_{i}$, no algoritmo). O material fornecido pelo professor\cite{ziviani}
explica essa parte em grande detalhe, de forma que julgo desnecessáio
repetí-la aqui.


\section{Análise de Desempenho}

Os dados seguintes foram gerados através da script \noun{gera\_estatisticas.sh}.
Seu código foi gentilmente cedido por Erikson Freitas de Morais, e
modificado por mim para assumir a forma atual. Os dados foram pré-processados
pela script \noun{parse\_estatisticas.pl} de forma a poder gerar
um conjunto de dados mais tratável.

Todos os testes foram executados na máquina \noun{turmalina.} A
medição do tempo foi feita usando-se o programa \noun{time} e levando-se
em conta apenas o tempo de usuário de cada processo lançado, de forma
que os dados estão isentos de flutuações devidas a lentidões ocasiodados
por problemas de I/O e etc.


\subsection{Casamento Exato}

Segue abaixo uma tabela contendo o tempo total que cada algoritmo
levou para realizar a busca pelas palavras chaves em cada um dos arquivos
de testes fornecidos.

\medskip{}
\begin{center}\begin{tabular}{|c|c|c|c|}
\hline 
tamanho do arquivo em kB&
agrep exato&
BMH&
Shift-And Exato\tabularnewline
\hline
\hline 
2768&
0,921&
10,121&
20,841\tabularnewline
\hline 
9912&
2,781&
34,721&
73,291\tabularnewline
\hline 
19832&
5,231&
69,711&
147,231\tabularnewline
\hline 
106952&
26,241&
375,551&
794,071\tabularnewline
\hline
\end{tabular}\end{center}
\medskip{}

Um primeiro dado que chama a atenção é quão lento é a minha implementação,
mesmo do BMH, é do agrep. Isso deve ser causado pelo fato de que minha
implementação lê e processa uma linha por vez, colocando um certo
\emph{overhead} a mais, já que a cada chamada da função um certo processo
de inicialização é feita. Tem-se também o fato de que limita-se a
procura a, em média, 80 caracteres por vez, ao invés de blocos de
tamanho maiores.

Analisando apenas a minha implementação, já que não tem como comparar
os dados do agrep com ela, vemos que o BMH mesmo estando limitado
às mesmas condições do Shift-And, apresenta uma performance pelo menos
2 vezes melhor, aproximadamente.

\medskip{}
\begin{center}\begin{tabular}{|c|c|c|}
\hline 
Número de Caracteres&
Padrão&
Tempo\tabularnewline
\hline
\hline 
3&
DCC&
23,031\tabularnewline
\hline 
3&
dia&
23,991\tabularnewline
\hline 
3&
New&
23,561\tabularnewline
\hline 
4&
UFMG&
19,581\tabularnewline
\hline 
4&
York&
20,541\tabularnewline
\hline 
5&
index&
18,691\tabularnewline
\hline 
5&
price&
19,101\tabularnewline
\hline 
5&
stock&
18,451\tabularnewline
\hline 
6&
branco&
17,401\tabularnewline
\hline 
6&
Canada&
17,601\tabularnewline
\hline 
6&
coffee&
17,381\tabularnewline
\hline 
6&
dollar&
17,311\tabularnewline
\hline 
7&
Gregory&
16,341\tabularnewline
\hline 
7&
Michael&
16,741\tabularnewline
\hline 
7&
Uberaba&
16,481\tabularnewline
\hline 
8&
Exchange&
15,511\tabularnewline
\hline 
8&
Treasury&
15,461\tabularnewline
\hline 
9&
Brazilian&
15,071\tabularnewline
\hline 
9&
Macunaima&
15,041\tabularnewline
\hline 
10&
Manacupuru&
14,321\tabularnewline
\hline
\hline 
14&
administration&
13,941\tabularnewline
\hline
\end{tabular}\end{center}
\medskip{}

Outro detalhe interessante é ver como o tamanho e a estrutura da chave
de busca alteram os tempos de execução do BMH. Quanto maior a palavra,
mais rápido fica o algoritmo. Isso é devido a possibilidade de dar
saltos maiores no texto quanto maior for a palavra. 

O Shift-And, ao contrário, nao apresenta comportamento semelhante
(Shift-And exato, arquivo de 106M):

\medskip{}
\begin{center}\begin{tabular}{|c|c|c|}
\hline 
Número de Caracteres&
Padrão de busca&
Tempo\tabularnewline
\hline
\hline 
3&
DCC&
37,921\tabularnewline
\hline 
4&
UFMG&
38,601\tabularnewline
\hline 
14&
administration&
37,461\tabularnewline
\hline
\end{tabular}\end{center}
\medskip{}


\subsection{Casamento Aproximado}

Vejamos agora uma tabela contendo o tempo médio que cada algoritmo
utilizou para realizar, para cada valore de k possível, uma busca
aproximada. Note que descartamos absurdos como busca aproximada com
3 erros para palavra de 3 caracteres (mutatis mutandis) porque isso
casa com qualquer coisa e não é o nosso interesse ver esse caso. O
caso médio será mostrado na tabela a seguir ao invés do somatório
devido ao fato de que nem todas as instâncias de testes possíveis
para esse caso foram rodadas, devido ao alto tempo que esses testes
levavam.

\medskip{}
\begin{center}\begin{tabular}{|c|c|c|}
\hline 
K (número de erros)&
Agre Aprox.&
Shift-And aprox\tabularnewline
\hline
\hline 
1&
1,871&
14,194\tabularnewline
\hline 
2&
5,107&
24,078\tabularnewline
\hline 
3&
10,187&
28,989\tabularnewline
\hline 
4&
12,917&
31,453\tabularnewline
\hline 
5&
13,221&
33,430\tabularnewline
\hline 
6&
12,545&
31,894\tabularnewline
\hline
\end{tabular}\end{center}
\medskip{}

Algumas observações antes de comentarmos esses dados:

\begin{itemize}
\item O agrep não faz busca aproximada com mais de 8 caracteres
\item Valores para os testes com $k\geq7$não foram mostrados devido ao
pequeno número de palavras com mais de 8 caracteres, para os quais
faria sentido realizar procura com $k\geq7$
\item Como dito, não rodamos todas as possíveis instâncias de testes, em
especial as que tomavam muito tempo.
\end{itemize}
Dessa forma, reduzimos a tabela para uma faixa mais conservadora dos
dados.

O que podemos novamente observar é que minha implementação realmente
ficou muito ruim. Tirando isso, podemos observer que a medida que
$k$cresce, a diferença entre os tempos de execução para dois valores
de $k$consecutivos decresce, claro sinal que quanto maior o $k,$maior
é a probabilidade de casar o podrão mais facilmente, chegando a um
ponto que a diferença volta a crescer denovo (valor absoluto): k fica
tão grande que a facilidade de casar com qualquer coisa aumenta. Isso
pode ser melhor observado olhandose para as linhas em que $4\leq linha\leq6$.


\section{Versão eletrônica}

A versão eletrônica desse relatório encontra-se em \emph{http://www.dcc.ufmg.br/\textasciitilde{}tmacam/PAA/},
na pasta PAA3, bem com os relatórios dos trabalhos passados.


\section{Referências}

\begin{thebibliography}{1}
\bibitem{cormenalg}\char`\"{}Introduction to Altorithms\char`\"{}, Cormen et al, 1st
Edition
\bibitem{ziviani}''Projeto de Algoritmos com implementações em Pascal e C''. Ziviani,
Nívio. 5a./6a. edição\end{thebibliography}

\end{document}