Árvores de Sufixo
Jeane Cecília
Roteiro



Definição
Aplicações
Construção



Algoritmo de McCreight
Exemplo
Outros Algoritmos
Árvores de Sufixo

Estrutura de dados que permite a
representação de todos os sufixos de um
determinado string S.

Pode ser construída em tempo O(|S|).

Permite a localização de um padrão p em
tempo O(|p|).
Árvore de Sufixo

Árvore enraizada, com n folhas.

Cada aresta é rotulada por um substring de S.

Arestas que saem de um vértice devem ter
rótulos com prefixos diferentes.

Cada folha corresponde a um sufixo de S.
Árvore para abd
abd
1
d
bd
2
3
Árvore para bbabd
d
5
b
3
d
babd
1
abd
abd
2
4
Árvore para aabbabd
a
d
b
abbabd
d
b
abd
babd
d
babd
Aplicações de Árvore de Sufixo

Encontrar todas as ocorrências de um
padrão (sequenciamento de DNA em Larga
escala).

Encontrar todas os substrings que contém
um padrão (localização de primers).

Encontrar o maior substring comum aos
strings S e T (tempo O(|S| + |T|).
Construção de Árvores de Sufixo

Algoritmo de McCreight
 Mapeamento de um string finito S em
uma árvore T.
 Caminhos em T são sufixos de S.
 Nós terminais de T são posições de S.
 Tempo: O(n log||)
Algoritmo de McCreight

Restrições

Uma aresta de T pode representar qualquer
substring não vazio de S.

Cada nó não terminal de T deve ter pelo
menos dois filhos (exceto a raiz).

O caractere final de S não pode aparecer em
outra parte deste.
Árvore para aabbabd
a
d
b
abbabd
d
b
abd
babd
d
babd
Definições

Caminho parcial


Caminho


Qualquer caminho a partir da raiz
Caminho parcial que finaliza em um nó
terminal
Locus

Nó final de um caminho parcial
b
abab...
b2
b
ab
b3
b
ababb...
b4
b
babab...
bbaa...
abab...
ababb...
ababb...
S = b5abab3a2b5c
Definições
 = abbab
 Extensão de 


Locus estendido de 


Qualquer string do qual  é um prefixo:
abbab******
Locus (definido) da menor extensão de 
Locus contraído de 

Locus (definido) do maior prefixo de 
Definições
attgacgattc
head7 = ga
suf7 = gattc
tail7 = ttc



suf i : sufixo de S.
head i : maior prefixo de sufi que
também é prefixo de sufj (j<i).
tail i = sufi-headi
Idéia Geral do Algoritmo


No passo i é inserido o sufi na árvore Ti-1,
obtendo a árvore Ti.
Procedimento



Localiza o locus estendido de headi em Ti-1.
Constrói um novo nó terminal para ser o
locus de headi (caso este não exista)
Acrescenta uma aresta rotulada taili, ligando
o locus de headi a um novo nó terminal.
T2
T3
babc
ab
ababc
babc
2
1
2
abc
1
c
3

Busca pelo locus estendido de headi


Se headi-1 pode ser escrito como a , então  é
prefixo de headi.
Suffix link: liga o locus de x ao locus de .
gtagcagtcgcagtcggacgagca
sufi-1
sufi
sufj-1
sufj
b
abab...
b2
b
ab
b3
b
ababb...
b4
b
babab...
bbaa...
abab...
ababb...
ababb...
S = b5abab3a2b5c
function fastfind (v:node; p:string):no;
{ p está contido em algum caminho iniciado em v }
begin
A partir de v, siga o caminho rotulado por p ;
compare apenas o primeiro símbolo de cada
aresta.
Seja (w,) o último nó implícito;
se  =  então
return w;
senão
return break(w, );
end
function slowfind (v:node; p:string):no;
begin
A partir de v, siga o caminho rotulado pelo
maior prefixo de p, letra por letra.
Seja (w,) o último nó implícito;
se  =  então
return w;
senão
return break(w, );
end
a
a
a
b
b
ea
ea
dc
ea
b
b
b
a
a
a
b
dc
dc
b
a
Último nó
implícito
d
b
a
c
d
b
c
a
O nó criado
break(w,ab) = find(v,p)
b
a
d
c
Algoritmo McCreight;
begin
T := árvore com dois nós e uma aresta rotulada p1
for i:=2 to n do begin
/* insere o proximo sufixo pi*/
 rótulo da aresta (pai[headi-1], headi-1)
 rótulo da aresta (headi-1, leafi-1)
u:= suf[pai[headi-1]];
v:= fastfind (u, );
Se v tem apenas 1 filho então
{v é um nó recentemente inserido}
headi := v
Senão headi := slowfind(v, );
Suf[headi]:=v;
Crie uma nova folha leafi;
Faça leafi como filha de headi;
Rotule a aresta (headi,leafi) de acordo;
end;
end.

a
u
Pai i-1


Head i-1
Fastfind(u,)
v
1
12
headi
2
Folha i-1
leafi
Slowfind(v, )
Outros Algoritmos

Algoritmo de Weiner




Incremental (como o de McCreight)
Processa o texto da direita para a esquerda
Busca a partir do prefixo (+ complexo)
Algoritmo de Ukkonen


Construção da árvore on-line
Tempo linear (alfabeto fixo)