AEDs III 28/03/2011

TP0

kemey-young
-malloc(), free() tambem terá Makefile

-Resenha

Vai sair hoje!
Data de entrega 08/04/2011


Makefile

regra: dependencia
  comando
executavel, executavel.cpp
    gcc executavel.cpp -o executavel

Ja foi definido que havera uma resenha para esta aula.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Revisão da ultima aula:
// Basicamente ele falou do KMP, e colocou a o significado da sigla, que anotei ai embaixo
KMP = Kmuth-Moris-Prett

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

// O professor começou a falar desse novo algoritimo de casamento de padrão
// Uma nota é que a explicação dele foi bem confusa hoje, eu tive que pesquisar tudo na internet depois.

BOYER-MOORE-HORSPOOL - Boyer-Moore-Horspool

- O(n/m), pior caso O(nm), melhor caso O(n/m)

- As comparações são feitas da direita p/ esquerda.
- Deslocamento é feito da esquerda para direita.
- É criada uma tabela de deslocamentos, analoga à tabela <pi> do KMP.
- É um algoritimo mais simples o que o diferencia do KMP e um pouco mais eficiente.

Como Funciona?

// começando com uns conceitos que eu vou usar para explicar:
  Vamos chamar de "janela" o trecho do texto T que está atualmente sendo comparado com P.

// Só revendo um detalhe estrutural do algoritimo
  Como dito nas notas acima, o deslocamento da janela ocorre no sentido de leitura,
  enquanto as comparações ocorrem no sentido contrario.
// Eu pensei um pouco sobre a necessidade dessas comparações no sentido contrario, e realmente não vi muita necessidade =/
// pra mim eu poderia fazer as comparações no sentido normal e ia funcionar identicamente.
// mas sei lá neh, vai ver o algoritimo que eu achei na internet num ta 100% fiel.

// Agora sim a explicação:

  O grande "chan" do algoritimo é uma tabela um pouco analoga à tabela <pi> do KMP, é uma tabela que indica o numero de
  deslocamentos que são seguros de se fazer após o fim de comparações, sabendo que "tal caractere" está em tal posição.

  No caso especifico desse algoritimo, o "tal caractere" é sempre o último da janela de comparação.
  A partir dele, se ele não for igual, a nem um dos caracteres do padrão P de comprimento m,
  eu posso assumir que é seguro eu deslocar m casas para frente.
  Porque concerteza aquele caractere não pertence a palavra, então vou tentar algo pra frente dele.

  Caso ele pertença a palavra, então eu tenho que deslocar um tanto de modo que
  a posição do caractere na janela e a posição do caractere no padrão sejam a mesma, depois tento comparar de novo.
  Obviamente isso da errado a maioria das vezes, mas funciona até melhor que a tabela <pi> do KMP.

// Bom é esse ai o BMH, o chan dele é uma tabela melhor que a tabela <pi> e melhor também que o sistema
// de O(n) do automato, já que no melhor caso e também no caso medio esse algoritimo é O(n/m), bom né?

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Shift-And

- Paralelismo de bit

- Simulação de um autômato não determinista.


Seguinte a ideia é simular um automato não determinista de modo que voce pode estar em multiplos estados ao mesmo tempo.
Isso é feito da seguinte maneira,
uma vez que o estado inicial representa uma palavra vazia e cada estado subsequente do automato representa uma letra da palavra uma vez que o ultimo estado é atingido é encontrado um padrão.

Para a parte não determinista, ao invez de se guardar quais estados estão funcionando em um inteiro cada estado,
o que exigiria varios inteiros e varias operações para atualizar cada estado,
guarda-se os estados ativos em um arranjo de bits chamado "R" onde o indice do bit indica qual é o estado
e o bit estar 1 indica que ele está ativo, permitindo que todas as operações de atualização dos estados ativos sejam feitos
em uma unica operação de processador. Bem engenhoso né?

Percebam então que isso funciona para palavras menores que a word do sistema sobre qual elas rodam. Hoje em dia isso significa
palavras de 32 ou 64 caracteres.

O sistema em sí funcoina da seguinte forma: A principio o estado "palavra vazia" está sempre ativo sendo então sempre igual a 1.
o que faz com que inicialmente R seja igual a "100000" para uma palavra de 5 letras e um automato consequente de 6 estados.
Antes de ler uma nova letra, arrasta-se o arranjo para a direita R>>1 de um bit, e o estado lambida é igualado a 1 novamente.
Deixando R = "110000". Isso faz do estado vazio e estado 1 ativos.
Agora vamos usar um arranjo M que possui um arranjo de bits para cada letra do alfabeto. Cada arranjo confirma a quais estados é possivel se chegar lendo-se aquela letra.

Portando se a palavra é "teste", M[ 't' ] = "010010". Indicando que é valido chegar-se ao estado 1 ou 4 lendo-se t.

Agora fazemos a magica, vamos supor que lemos a letra 't', já que R = "110000", e M['t'] = "010010" nós precisamos confirmar se realmente o estado 1 deve continuar ativo. Se a letra não for t ele não continuar ativo, se for ele deve continuar.
Fazemos isso comparando o R="110000" & M['t']="010010" resultando no novo R = "110000", e reiniciando o processo.

O que acontece então é que nos vamos caminhando com os estados sempre ativos a partir do estado "vazio" e desativamos aqueles que não forem possíveis usando a operação de &. Se o estado caminhar ativo ate a ultima posição necessariamente as letras t,e,s,t,e foram lidas ocasionando um casamento de padrão. Extremamente interessante não?

Bem simplificando todo este texto que escrevi, e ja tendo em mente como M e R devem ser preenchidos inicialmente
a equação que atualiza o valor de R é:

R' = ((R>>1) | 2^(m-1)) & M[t[i]]; // (só lembrando m minusculo é o comprimento do padrão, no caso de teste é 5)

R>>1 faz o caminhamento dos estados
| 2^(m-1) recoloca o 1 no bit do estado vazio.

então o & M[t[i]] (sendo t[i] o caractere do texto lido atualmente) faz o check up de quais estados podem continuar ativos.