AEDs III 30/03/2011

BOYER-MOORE
// Não entendi bem, se na aula anterior ele estava explicando o Boyer Moore Horspool, e nessa aula ele decidiu explicar o BOYER-MOORE sem o Horspool, ou se ele ta re-explicando esse cara, mas anyway, nao entendi qual dos 2 mas parece que o BM é força bruta.

// Estudar Boyer-Moore Puro para ver quais as diferenças do BMH.

Shift-And // Re-explicado, ao menos essa explicação me poupou de pesquisar sozinho na internet

- Paralelismo de Bit
- Automato não-determinista

       t     e     s     t     e
--> 0 --> 1 --> 2 --> 3 --> 4 --> (5)  // sendo 5 estado final

     | 1 2 3 4 5 //numero do bit.
M[t] | 1 0 0 1 0
M[e] | 0 1 0 0 1
M[s] | 0 0 1 0 0

o 1 na tabela indica que leva ao estado do numero da coluna.
ou seja se estava no estado X, na proxima rodada do loop ele verifica se
consegue chegar no estado X+1, se o bit daquela posição para aquela letra for 1,
entao consegue, isso é anotado e se chega ao proximo estado.

então teremos um inteiro que representara o estado atual.

o inteiro é sempre atualizado assim:

R = (2^(m-1) | R>>1) & M[T[i]];

Pode parecer estranho a principio eu usar os bits de R para definir o estado,
mas lembre-se de que estamos imitando um automato não deterministico, significando que eu posso estar em mais de um estado por vez certo?

Bem cada bit de R indica que eu estou, ou não em um estado, e é por isso que eu dou um shift

// Essa explicação ficou mais como revisão, achei bem escrita =], mas se quiser mais detalhes sobre o shift-and
// a aula do dia "03 28" explica melhor.

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

Ja vimos então o casamento exato de padrão =].

Veremos agora o Casamento Aproximado
que é quando a palavra não se encaixa direitinho, falta uma letra ou tem uma letra a mais.

Os que existem são:
- Spell Checker
- Filtro de SPAM
- Diff ( revisão de arquivo )

// um conceito essencial ao casamento aproximado é o de distancia de uma palavra para outra
// que é o numero de diferenças entre as duas,
// o que permite que as pesquisas no google por exemplo funcionem mesmo se voce errar um pouco a palavra.
// abaixo o professor colocou de maneira mais sucinta do que seria adequado, os valores que diferenciam as palavras.
// e deu um exemplo de como usar esses valores.

CONCEITO:
Distância de edição é o numero de diferenças entre duas palavras.
Entao tipo se tem uma letra a mais, a menos ou trocada tenho que incrementar o contador de diferenças.

//O professor colocou então uns "preços" de diferença para cada operação,
// mas não sei pra que isso se todos tem o mesmo preço.

- Deleta custa 1
- inserção custa 1
- Substituição custa 1

// Bem dito a ideia da distancia de edição, o professor exemplificou com o Shift-And Aproximado.

Primeiramente mostraremos o shift-and para a operação de inserção que é quando a palavra lida tem uma letra a mais.
É adicionada então uma tolerancia a erros, da mesma forma que funciona o automato do shift-and, aqui nós criamos mais N automatos
que só são ativados se o primeiro automato receber uma letra errada.

// O numero N de novos automatos é o numero de erros que serão tolerados

entao se eu li a letra T do padrão "Teste", mas em seguida li um A, eu pulo para o estado T' (do 2° automato) que indica que tolerei um erro, se acontecer de novo pulo pro estado T''(3° automato), se agora aparecer um E pulo para o estado E''(ainda no 3° automato), indicando que cheguei a letra E tolerando 2 erros.

// A implementação deve ser interessante
// Bem o professor comecou a explica-la agora:

bem é o seguinte o calculo para R ainda é o mesmo identicamente:
R = (R>>1 | 2^(m-1)) & M[T[i]]; // igualzinho.

// mas o calculo pro R':
R'= (R'>>1 & 2^(m-1) | R | M[T[i]]); // é diferente

// Agora um automato que deleta!

Um shift-and que aceita deleções ou seja uma letra que está em falta vai ter tambem tantos automatos quanto numero de erros que eu desejo tolerar e caso ocorra um erro no estado T (Padrao="Teste") eu tenho de pular é para o estado E'(2° automato),
indicando que cheguei a letra E tolerando um erro, e fazendo isso eu meio que pulei a letra T e estou buscando a palavra "este".

// agora o calculo que é importante né.

R = mesmo calculo dos demais =];
R'= (R'>>1 | 2^(m-1)) | R >> 1;

Programa Dinâmico
distância de levenshtein.
// seguinte peguei mal o inicio dessa explicação posso ter q estudar sozinho.