AEDs III 23/03/2011

// Nessa aula parece que vamos falar sobre processamento de strings
// O professor tambem disse que as proximas 3 aulas serão sobre este assunto, deve valer a pena a atenção.

Processamento de Cadeias de Caracteres

Bibliografia para essa materia:
NivioZ - cap8
Introduction to algorithms (cormen) - Cap 32
Algorithms in C (Robert SedgeWick) - cap 19  --> este é o favorito do professor.

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

Casamento de Cadeias (ou seja pesquisa por palavra)

 Metodos Exatos:
  - Lista Invertida ©
  - Força Bruta ©
  - Autômato ©
  - KMP ©
  - BOYER-MOORE x
  - Shift-And x

 Metodos Aproximados:
// Nenhum foi listado, não sei porque


// Abaixo o professor deu nomes a umas "variaveis" que imagino ele vá usar nesta aula.
 Texto arranjo T[1..n] -> contendo o texto de n caracteres a ser pesquisado
 Padrão arranjo P[1..m] -> contendo a palavra de m caracteres a ser encontrada no texto
 Alfabeto finito <sum> (haviam exemplos de alfabetos finitos, mas num vi porque escrever isso aqui)

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

// Seguem algumas observações que parecem se referir cada uma a um algoritimo especifico
// Aparentemente cada uma das observações se refere a um grupo de algoritimos que existem para pesquisa.
Tipo 1:

P e T: não são processados.
P e T: não são conhecidos a priori.

Tempo da busca O(m*n)

// Exemplos de algoritimos que se enquadram nesse tipo.
Ex: Algoritmo sequencial, on-line, tempo real.

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

Tipo 2:

P: pré-processado
  o padrão é conhecido anteriormente.
T não é preprocessado.

Tempo da busca O(n)

Ex: Edições de texto

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

Tipo 3:

P e T pre-processado
 - Algoritmo constroi um índice

Tempo da busca O(log(n))

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

Primeiro exemplo

lista invertida, tipo 3.
O texto é preprocessado entao voce tem a liberdade de fazer o seguinte:

Uma lista ordenada de palavras, contendo todas as palavras do texto mas sem repetição das mesmas.
Cada palavra da lista aponta para uma pilha de indices de modo que cada indice destes aponta para uma ocorrencia da palavra no texto.
Dessa forma para se encontrar a palavra na lista é feita uma pesquisa binaria O(log(n)), e então é retornada a lista de ocorrencias.

Fazendo isso ser um algoritmo O(log(n))

Outro método é criar uma arvore digital (o nome dela parece que é Trie), nessa arvore cada letra representa uma transição para um nó superior, e cada nó representa uma sub-palavra. Os nós finais possuem as palavras completas que foram formadas pelas letras das transições que levam até elas, juntamente com os indices das posições onde essas palavras se encontram no texto.

Parece que um macete para essa arvore é que não é preciso existir tantas transições quanto letras, digamos assim, se tenho apenas duas palavras, uma delas é batata e a outra é feijão, só precisarei do nó inicial e de uma transição para a letra b e de uma transição para a letra f. Se acontecer de surgir mais palavras que poderiam gerar ambiguidade com tão pouca distinção ai deveria ser adicionados outros nós e outras transições.

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

Segundo exemplo

 Força Bruta:

// nem é preciso exemplificar né? é bem facil.
A complexidade desse algoritimo é de O(n*m)

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

Terceiro exemplo

 Autômatos:

Tupla(Q,I,F,<sum>,T)
Q - Conjunto finito de estados
I - estado inicial I <pertencente> Q
F - estados finais
<sum> - alfabeto
T - conjunto de trancisões.

A ideia é construir um automato que leia o padrão, mas com um detalhe interessante, quando a letra de transição recebida for levar a um estado de erro, ao invez disso pode-se ir a um estado cuja a sub-palavra que ele representa (assim como na arvore Trie) de fato tenha acontecido recentemente. Opa, opa, o que voce está falando, voce não disse que acabou de acontecer um estado de erro? como poderia haver uma subpalavra correta? Mas pense bem, na palavra ababca, mesmo que eu receba um 'a' como quinta letra (ao inves do c) eu ainda posso aproveitar uma subpalavra lida que seria "aba".

Desse jeito voce pode ter um esmero maior com as transições de modo a ficar com uma unica comparação por letra do texto.
É um pouco dificil de explicar, mas isso evita que seja lido varias vezes a mesma letra do texto,

Exemplo (é meio repetitivo com o que eu ja disse em cima, mas ajuda a pegar a ideia):
digamos que o padrao é "ababc",

no texto eu leio a, depois b, depois a, depois b, e depois, opa leio a! Bem o padrão quebro, a letra que eu esperava era c certo?
                "a"      "ab"      "aba"    "abab"                "ababa"

mas olha, eu posso colocar que nesse nó do automato a transição para a letra b é mandar para o nó 3 (nó da sub-palavra "aba"),
(e não para o nó 0 como seria usando o metodo de força bruta).
Porque mesmo que o padrão "ababc" não exista, o "aba" ao menos ainda existe,
e pode vir a formar um "ababc" se eu continuar a partir daí.

A complexidade do preprocessamento é O(m|<sum>|) lembrando que <sum> é o alfabeto.
A complexidade da pesquisa é         O(n)

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

Terceiro exemplo

KMP:

// Esse metodo é meio complicado de entender

O KMP é mais ou menos analogo ao sistema do automato, porem ao inves de criar transições de estados para indicar quanto trabalho foi perdido, ele calcula previamente quanto trabalho (ou seja, letras do prefixo da palavra) seria perdido se ocorre uma comparação negativa na letra i do padrão P.
E então quando um erro de fato acontecer o programa rebobina o cabeçote que le P nesse número de letras.
Depois de calcular todos esses valores, ele anota estes valores em um arranjo de m posições que é o arranjo <pi>.

Então a tabela de transição <pi> tem um comprimento de m inteiros e guarda o numero de letras que eu tenho de rebobinar no cabeçote de leitura do padrão, para poder continuar as comparações de maneira eficiente, sem recomparar o que eu ja sabia.

Desse jeito eu nunca preciso de voltar atrás o cabeçote de leitura do texto T e ganho alguma eficiencia.

// Acabei de explicar de um jeito facil =], abaixo vem o jeito complicado,
// mas pode ser que o de baixo seja mais útil para quem queira realmente programar esse metodo.

A ideia é o seguinte,

a cada nova letra lida e comparada com P com resultado positivo, tem-se uma nova subpalavra de P com as letras iniciais dele.
tipo "ab" é o inicio de "abbba"
Ou seja um Prefixo novo é encontrado a cada letra lida.

vamos chamar esse prefixo Px

Vamos então montar a tabela <pi>
para isso vamos fingir uma leitura, e a cada novo Px vamos calcular o quanto seria perdido ao se receber uma letra errada neste ponto.

Agora para calcular a perda de trabalho temos de pensar, sera que um sulfixo qualquer de Px pode ser igual a um prefixo do padrão P?

Por que pense bem, se for igual significa que eu posso aproveitar parte do que foi lido, e continuar daí, como se o Px fosse esse sulfixo.

Para descobrir se tem algum sulfixo de Px que é aproveitavel o jeito é testar um a um mesmo.


Por fim,
uma vez encontrado um desses sufixos, o calculo para saber quantas letras tenho de voltar é: |Px|-|sufixo|
sendo |cadeia de carateres| a notação que indica o comprimento da cadeia de caracteres.

O numero de letras que eu devo rebobinar no cabeçote de leitura de P fica então anotado na posição i do arranjo <pi>.
sendo i o numero de letras de |Px| usado no calculo.

E durante a leitura do texto sempre que houver um "missmatch" de comparação eu rebobino o leitor do cabeçote em <pi>[i] posições, e continuo a leitura normalmente.

Ex: // ESSE EXEMPLO TA DESATUALIZADO NAO PRESTE MTA ATECAO NELE!
o padrão é ababababca

pi[0]=0; pq se a primeira letra deu errado, so posso pular uma, como seria feito normalmente.
pi[1]=0; pq "ab" nao possui um sufixo que seja prefixo de P
pi[2]=1; pq em "aba" o sufixo "a" é prefixo de P e o comprimento dele é 1.
pi[3]=2; pq em "abab" o sufixo "ab" é prefixo de P e o comprimento dele é 2.

e assim por diante.