Á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
12
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)
Download
