Segundo seminário informal (mas formal!)
do Grupo de Teoria da Computação
Algoritmos Para Pesquisa
Aproximada em Palavras
Rodrigo Miranda
Mestrado em Informática
Universidade de Brasília
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Sumário





Distância de edição entre duas palavras
Algoritmo de programação dinâmica
Similaridade e Alinhamento
Algoritmo de programação dinâmica com
espaço O(n)
Acelerando a programação dinâmica com
árvores de sufixos
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição entre 2 palavras


Dadas duas palavras t e p, definimos a distância de
edição D(t, p) entre elas como a quantidade mínima de
operações necessárias para transformar t em p ou vice-versa.
As operações podem ser:






Substituição (Replacement)
Inserção (Insertion)
Remoção (Deletion)
Pareamento (Match)
A operação de pareamento não é contada na distância
de edição.
Valores menores indicam menor distância de edição
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição entre 2 palavras
- Exemplo 

Sejam t= ontologico e p= antologia
Podemos transformar t em p com 3 operações:




r m m m m m m m r d
o n t o l o g i c o
a n t o l o g i a
E podemos transformar t em p com 3 operações:



r m m m m m m m i r
a n t o l o g i
a
o n t o l o g i c o
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição - Cálculo



Sejam as palavras p = t1...tm e p = p1...pn
Calculamos a matriz D0...m, 0...n onde D(i,j) é a distância de
edição entre t1...ti e p1...pj
Acrescentamos uma coluna e uma linha (j=0 e i=0,
respectivamente) e podemos calcular a matriz com as
distâncias de edição entre t e p com o seguinte algoritmo:
 j , se i  0



D(i, j )  i, se j  0

minD(i  1, j  1)d (i, j ), D(i  1, j ) 1, D(i, j  1), caso contrário 


onde d (i, j )  0 se ti  p j , ou 1 caso contrário.
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição – Algoritmo

O algoritmo pode ser implementado de forma eficiente usando
técnicas de programação dinâmica, dadas t e p:
Criamos a matriz D0..m,0..n
Para i = 0..m faça D[i,0] = i
Para j = 0..n faça D[0,j] = j
Para i = 1..m faça
Para j = 1..n faça
Se t[i]=p[j] então d=0 senão d=1
D[i,j]=MIN(D[i-1,j-1]+d,D[i-1,j]+1,D[1,j-1]+1)

Podemos recuperar o transcrito de edição acrescentando
ponteiros de traceback à matriz.
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição - Exemplo
0

a 1
n 2

t 3
o 4

l 5
o 6

g 7
i 8

a 9
o
n
t
o
l
o
g
i
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
2
3
3
4
5
1
2
3
4
5
2
1
2
3
4
3
2
1
2
3
4
3
2
1
2
5
4
3
2
1
6
5
4
3
2
7
6
5
4
3
6
7
8
6
7
8
5
6
7
4
5
6
3
4
5
2
3
4
1
2
3
2
1
2
Algoritmos para pesquisa aproximada em palavras
c
o
9 10 

9 10 
8 9

7 8
6 7

5 6
4 5

3 4
2 3

2 3
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Distância de Edição – Análise do
Algoritmo



Complexidade de tempo: O(mn)
Complexidade de espaço O(mn) para armazenar
a tabela de programação dinâmica
Para palavras muito grandes (o espaço é
limitante:
Duas palavras p e t, cada uma com 106 caracteres, o
tamanho da matriz será de 106 x 106 = 1012
 Se cada caractere ocupar 1 byte de memória, a matriz
para p e t ocupará 1 terabyte!

Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Similaridade





Variação do problema de distância de edição
Usamos uma função s(a,b), s:s x sN, e o peso g
representando o peso de um espaço (remoção ou
inserção).
Valores usuais para s(a,b) são -1 se a ≠ b e +1 se a =
b, e g = -2
Dadas as palavras t e p, a similaridade será dada por
V(t,p)
Valores maiores indicam maior similaridade
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Similaridade - Cálculo

Dadas as palavras p e t, a função s(a,b) e o peso g de
um espaço, calculamos a similaridade V(t,p) sobre a
matriz V0...m, 0...n onde V(i,j) é a similaridade entre
t1...ti e p1...pj, e V(t,p)=V(m,n):
 j.g , se i  0



V (i, j )  i.g , se j  0

max V (i  1, j  1) s (t , p ),V (i  1, j ) g ,V (i, j  1)  g , caso contrário 
i
j



Algoritmos para pesquisa aproximada em palavras

Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Alinhamento

Alinhamento global



Alinhar as duas palavras de forma completa
Usa-se o algoritmo de cálculo da similaridade com os
ponteiros de traceback.
Alinhamento semi-global (|p| < |t|)

Identificar ocorrências da palavra p em t com similaridade
mínima k (também podemos dizer com no máximo k
diferenças)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Alinhamento

Alinhamento local




Identificar subpalavras de t e p com alto grau de similaridade,
achamos i, j tal que V(i,j)≥k
Usamos uma variação do algoritmo de cálculo de similaridade
com ponteiros de traceback
Alteramos o algoritmo tal que V(i,j)≥0 para todo i=0...m,
j=0...n
A recuperação dos alinhamentos é feita a partir de cada i,j,
seguindo os ponteiros de traceback até que V(i,j)=0
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Alinhamento
Alinhamento Global
Alinhamento Local
Alinhamento Semi-Global
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço
O(n)


Para calcular somente a similaridade (ou distância de
edição), é preciso apenas usar 2 linhas da matriz, a
corrente e a anterior, de forma que a complexidade de
espaço se torna linear.
Para recuperar o alinhamento usando espaço linear
precisamos usar algumas observações para alterar o
algoritmo (Hirschberg)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)




Dada a palavra s=s1...sn, dizemos que sr=sn...s1 é a palavra reversa
de s.
Dadas as palavras t e p, definimos Vr(i,j) como a similaridade de
tr1... tri e pr1... pr j (ou seja, é a similaridade dos últimos i caracteres
de t e os últimos j caracteres de p).
Dadas t e p e a matriz V de similaridade, vale a seguinte relação:
V(m,n) =max0≤k≤m[V(m/2,k)+Vr(m/2,n-k)]
Isso significa que existe uma posição k* entre 0 e mque maximiza
V(m/2,k)+Vr(m/2,n-k), ou seja, existe um alinhamento ótimo de
t e p passa pela célula V(m/2,k*).
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)
Primeira parte do Algoritmo

Podemos achar k* na linha m/2 da matriz usando
O(mn) e O(n) espaço.




Usamos o algoritmo de programação dinâmica para calcular
V(m/2, k) e Vr(m/2,n-k)
O espaço usado é linear porque só precisamos de 2 linhas,
incluindo dois conjuntos de ponteiros de traceback
Uma vez encontrado k*, na linha m/2, seguimos o
primeiro conjunto de ponteiros de traceback a partir de
(m/2,k*) até uma célula (m/2 -1, k1)
De forma similar, usamos o segundo conjunto de
ponteiros de traceback a partir de (m/2,k*) até uma
célula (m/2 + 1, k2)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)
Completando o Algoritmo

Até este passo no algoritmo obtivemos 3 pontos do
alinhamento ótimo global, e podemos dividir o
problema restante em dois subproblemas:
i)
ii)

encontrar o alinhamento ótimo entre t1...tm/2-1 e p1....pk1
encontrar o alinhamento ótimo entre tm/2+1...tm e pk2....pn
Cada subproblema pode ser resolvido com o mesmo
algoritmo, recursivamente
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)

Algoritmo
Dadas t e p, de tamanho m e n respectivamente
AlinhamentoPalavras(t,p,m0,m1,n0,n1,V0,V1)
h = (m1-m0)/2
Para j = 0..(n1-n0) faça V0[i] = j*g(), V1[i] = j*g()
Para i = 1..h faça
Para j = 1..(n1-n0)
Calcule a sim. da linha i e mantendo os ponteiros de traceback
usando V1 e V0
Repita usando i = m..h (decrementando i)
Encontre k* tal que V(h,k*) + Vr(h,n-k*) é máximo
Siga os ponteiros de traceback a partir de k* e guarde o subcaminho
subcaminho_k* formado desde k1 até k2 (k1 onde o traceback a partir de k* seguir
para a linha h-1, k2 onde o traceback a partir de k* seguir para a linha h+2)
subcaminho_k1 = AlinhamentoPalavras(t,p,m0,h-1,n0,k1)
subcaminho_k2 = AlinhamentoPalavras(t,p,h+1,m1,k2,n1)
Retorne o subcaminho concatenando subcaminho_k1, subcaminho_k* e subcaminho_k2,
nessa ordem

A chamada inicial seria AlinhamentoPalavras(t,p,1,m,1,n,V0,V1)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)
0
0
k1
k*
k2
n
m/2-1
m/2
m/2+1
m
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)
Análise do Algoritmo

Análise de Tempo

O trabalho executado pelo algoritmo é o trabalho da programação
dinâmica mais o trabalho de cada chamada recursiva, que nos dá uma
relação de recorrência da seguinte forma:
T(mn) = mn + T(A) + T(B), onde A e B são os subproblemas


Cada A e B corresponde à execução do algoritmo sobre metade das
linhas e uma quantidade variável de colunas, mas como as colunas de A
e B não se sobrepõe, a quantidade total de colunas de A e B ≤ m, de
forma que o trabalho total T(A)+T(B) ≤ T(mn/2).
Isso nos dá uma relação de recorrência da forma:
T(mn) = mn + T(mn/2)

Resolvendo a relação de recorrência chegamos à complexidade de tempo
do algoritmo:
T(mn) ≤ 2mn
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Programação Dinâmica com espaço O(n)
Análise do Algoritmo

Análise de Espaço




Para o passo de programação dinâmica, precisamos de 2
vetores de O(n) elementos, incluindo os os ponteiros de
traceback
O alinhamento pode ser armazenado em O(m), onde m≥n
O espaço gasto na pilha de execução do algoritmo será
O(log2m), porque cada chamada recursiva será feita com
metade das linhas anteriores
Assim o espaço total S será:
S = O(n) + O(m) + O(log2m) = O(m)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Árvores de Sufixo




Uma árvore de sufixos T para uma palavra t=t1...tm é
uma árvore com raiz com exatamente m folhas
numeradas 1 a m
Cada nó interno da árvore com exceção da raiz tem
pelo menos 2 ramos e cada ramo é rotulado com uma
subpalavra de t
Se dois ramos partem do mesmo nó de T, então seus
rótulos diferem pelo menos no primeiro caractere
Para qualquer caminho da raiz até uma folha i de T, a
concatenação dos rótulos dos ramos nos dá um i-ésimo
sufixo de t (ti...tm)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Árvores de Sufixo
Exemplo

Árvore de sufixoS para a string GATGACCA$:
GA
C
A
TGACCA$
$
CA$
A$
CCA$
9
$
CCA$
6
7
1
8
4
TGACCA$
5
TGACCA$
3
2
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Árvores de Sufixo
Características



Podem ser construidas com tempo O(m)
O espaço utilizado também é O(m), embora m seja
multiplicado por um fator grande (em geral 14 a 20)
A pesquisa de qualquer padrão p=p1...pn leva exatamente
n comparações no pior caso, para qualquer tamanho de
t
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k
diferenças





Dada um texto t e um padrão p, queremos buscar todas
as ocorrências de p em t com no máximo k diferenças
(substituição, remoção, inserção)
Os espaços no fim de t não contam como diferenças
Também chamado de alinhamento semi-global
Podemos resolver com programação dinâmica em
O(mn)
Usamos uma árvore de sufixos para acelerar a
programação dinâmica (Landau/Vishkin)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k
diferenças




Usamos as diagonais da tabela de programação
dinâmica
A diagonal principal da tabela consiste das células
(i,i), para 0 ≤ i ≤ n ≤ m
Numeramos as diagonais acima da diagonal principal de
1 a m sendo a diagonal que inicia na célula (0,i) a
diagonal i
Numeramos as diagonais abaixo de -1 a –n, sendo a
diagonal que inicia na célula (i,0) a diagonal -i
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k
diferenças


Um d-caminho na tabela de PD é um caminho que
inicia na linha 0 e contém um total de d substituições e
espaços.
Um d-caminho é o mais longo na diagonal i se
termina na diagonal i e o índice da coluna onde termina
é maior que o de todos os outros d-caminhos que
terminam em i
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Diagonais na matriz de Programação
Dinâmica

Em verde um (d-1)-caminho que é o mais longo na
diagonal i
0
i-1 i i+1
Algoritmos para pesquisa aproximada em palavras
c
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k
diferenças


Temos um d-caminho mais longo na diagonal i, quando d=0, é o
maior prefixo comum de ti...tm e p1...pn
Se d>0, então obtemos o d-caminho mais longo na diagonal i a
partir de 3 (d-1)-caminhos:




O (d-1) caminho mais longo na diagonal i-1, extendido em uma célula
para a direita para a célula (a,b)
O (d-1) caminho mais longo na diagonal i+1, extendido em uma célula
para baixo para a célula (c,d)
O (d-1) caminho mais longo na diagonal i, extendido em uma célula na
diagonal (representando uma substituição) para a célula (e,f)
Quando temos todos os k-caminhos mais longos nas diagonais –
n a m identificamos todas as posições onde p ocorre em t com no
máximo k diferenças
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Diagonais na matriz de Programação
Dinâmica

Em verde um (d-1)-caminho que é o mais longo na
diagonal i
0
i-1 i i+1
Algoritmos para pesquisa aproximada em palavras
c
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k
diferenças – Algoritmo

Temos então uma versão em alto nível do algoritmo
para resolver o problema da pesquisa aproximada com
k diferenças:
Para d=0...k faça:
Para i = -n ... m faça:
A partir do mais longo (d-1) caminho nas
diagonais i-1, i e i+1 encontre o mais
longo d-caminho na diagonal i
Cada caminho que chega à linha n numa coluna c
define uma ocorrência de p em t com no máximo k
diferenças

O que falta é uma maneira eficiente de calcular a
extensão máxima na diagonal
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k diferenças
Usando Árvores de Sufixos




Construímos uma árvore de sufixos P para p
Calculamos em tempo O(m) dois vetores l e q onde l(i) é
o comprimento da maior subpalavra de t iniciando na
posição i que também é substring de p, e q(i) é a posição
inicial de uma dessas subpalavras de p.
Fazemos a busca da maior extensão comum de ti...tm e
pj...pn buscando o lowest-common-ancestor (lca) das folhas
q(i) e j de P, e usando o menor valor entre m(i) e
lca(q(i),j).
Podemos calcular o lca em P de duas palavras de p em
O(1) após pré-processamento de P em tempo O(n)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k diferenças
Usando Árvores de Sufixos

Combinando o algoritmo descrito com a capacidade de
encontrar a maior extensão comum de duas subpalavras
de t e p em tempo O(1) temos que a complexidade de
tempo do algoritmo será:





Pré-processamento de p e t para gerar os vetores l e q: O(m)
Construção da árvore de sufixos P de p: O(n)
Pré-processamento de P para obter o lca de duas folhas em
tempo O(1): O(n)
Algoritmo de pesquisa aproximada O(k(m+n)) = O(km)
Logo, temos que a complexidade total de tempo será:
O(m + n + km) = O(km)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k diferenças
Usando Árvores de Sufixos

A complexidade de espaço sera similar.
Os vetores l e q usam espaço O(m)
 a árvore de sufixos P usa espaço O(n)
 para guardarmos (m+n) passos dos d-caminhos para
k diferentes valores de d temos que o espaço
necessário será de O(km)


O espaço total será então:
O(m + n + km) = O(km)
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Pesquisa aproximada com k diferenças
Usando Árvores de Sufixos
Algumas observações




Na prática, o método só é eficiente para m e n
grandes e k < n (Baeza-Yates)
Apesar de usar espaço O(km), por usar árvores
de sufixo, existe um multiplicador grande de km
embutido
Precisa ser modificado para tratar o problema de
alinhamento (baseado em similaridade)
Não resolve para o alinhamento local
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Conclusão


Para um determinado problema com solução em
programação dinâmica, podemos análisá-lo com
cuidado e buscar uma solução que melhor o uso
de espaço gastando um pouco mais de tempo
Podemos usar técnicas para acelerar a
programação dinâmica, combinando estruturas
de dados avançadas, realizando a programação
dinâmica implicitamente
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004
UNIVERSIDADE DE BRASÍLIA
SEGUNDO SEMINÁRIO INFORMAL (MAS FORMAL!) DO GRUPO DE TEORIA DA COMPUTAÇÃO
Bibliografia



GUSFIELD, Dan. Algorithms on Strings, Trees and
Sequences. 1997. Cambridge University Press
LANDAU, G. e VISHKIN, U. Introducing efficient
parallelism into approximate string matching and a new serial
algorithm in Proceedings of the eighteenth annual ACM
symposium on Theory of computing. 1986. ACM Press
BAEZA-YATES, R. e GONNET, G. 1994. Fast string
matching with mismatches in Information and Computation
108, 2, 187-199. Preliminary version as Tech. Rep. CS88-36, Data Structuring Group, Univ. of Waterloo,
Sept. 1988.
Algoritmos para pesquisa aproximada em palavras
Rodrigo Miranda – Outubro/2004