Enquanto estudava o curso Algoritmos em Strings , enfrentei o problema de construir uma árvore de sufixos . Seguindo o link para materiais adicionais, encontrei uma recomendação para "ver este ótimo comentário no Stack Overflow ". Tendo estudado e implementado de acordo com a descrição livre fornecida , o algoritmo de Ukkonen decidiu compartilhar a tradução.
O que se segue é uma tentativa de descrever o algoritmo de Ukkonen; primeiro mostrando como funciona em uma string simples (ou seja, a string não contém caracteres duplicados), expandindo gradualmente para o algoritmo completo.
Algumas declarações preliminares:
O que estamos construindo é basicamente uma árvore de prefixos . Este é o vértice raiz, cujas arestas saem dele para novos vértices, e arestas subsequentes saem deles e assim por diante.
Mas , ao contrário da árvore de prefixos, os rótulos de borda não são caracteres únicos, para cada borda o rótulo é um par de números [de, para] - ponteiros para posições no texto. Neste caso, cada aresta contém uma string de comprimento arbitrário, mas leva apenas O (1) memória (dois ponteiros)
Principio básico
Primeiro, o autor deseja demonstrar como criar uma árvore de sufixos de uma string extremamente simples, strings sem caracteres duplicados:
abc
O algoritmo funciona em etapas, da esquerda para a direita . Um passo por caractere de linha . Cada etapa pode envolver mais de uma operação individual, mas veremos (veja as observações finais no final) que o número total de operações é O (n).
a
, [0, #]
- 0 . #
, , 1 ( a
).
, :
:
2 ( b
). : . :
a
-ab
b
:
:
:
ab
, :[0, #]
. ,#
1 2.
O(1) , , , .
c
c
.
:
:
:
,
O(n),
#
, O(1). n, O(n)
:
, , . :
abcabxabcd
abc
, , ab
x
, abc
d
.
1 3: 3 :
4: #
4. :
a
.
, ( #
), , , , :
(_, _, _)
,
, :
abc
(, '\0x', 0)
, .._
,_
'0\x',_
. , , , .
1 . , , , 1 ( )
. a
, a
, : abca
. :
[3, #]
. ,a
. , - . , .
(, 'a', 1)
. , -a
, , 1 . ,a
. , ( , , ).
, 2
Spoiler
[4, #]
, , a
3
: , , , (
). , ( a
). , ( , O(1)), .
5: #
5. :
,
2, : ab
b
. - , :
a
. , ,
ab
.
b
.
, ( a
, abcab
), b
. : , b
.
, . :
(, 'a', 2)
( , ,b
)
3, , .
: ab
b
, ab
, b
. ? , ab
, ( b
) . , , , - , .
6, #
. :
3, abx
, bx
x
. , ab
, x
. , x
, abcabx
:
- , O(1).
, abx
2. bx
. , . , , 1, , _
( 3 ).
1, :
-
_
-
_
, , ..b
-
_
1
C, (, 'b', 1)
, bcabx
, 1 , b
. O(1) , x
. , . x
, , :
O(1),
1, (, 'x', 0)
, 1.
-. 2:
, , , , .
Spoiler
1 2
, , , , .
, . ( ):
, x
. _
0, . x
, :
Spoiler
, .
7, #
= 7, , , a
. () , . , , (, 'a', 1)
.
Spoiler
#
, , #
8, #
= 8, b
, , , , (, 'a', 2)
, , b
. ( O(1)), . (1, '\0x', 0)
. 1
, ab
.
, #
= 9 'c', :
:
, #
c
, , , 'c'. , 'c' , (1, 'c', 1)
,
.
#
= 10
4, abcd
( 3 ), d
.
d
O(1):
_
, , .
3
_
, , , ,_
, . ,_
._
_
.
(2, 'c', 1)
, 2 :
abcd
,
3 : bcd
. 3 , bcd
, d
.
, - 2 :
: , O(1). , , ab
b
( ), abc
bc
.
.
2, 3, . _
( ) , . (, 'c', 1)
.
, , c
: cabxabcd
, , c
. :
, 2 :
( Graphviz Dot . , , , , - )
1, _
, 1 (root, 'd', 0)
. , d
:
Spoiler
, . :
#
1 . O(1).
:
,
.
, . , #
. . : O(1), , , . ? ( , ).
, , , , ,
> 0. , , . , . ,
> 0, , .
Spoiler
,
> 0? , - , - . , . $
. ? → , , . , , .
- , , , . , , , .
? n , , n ( n + 1, ). ( ),
, O(1) .
, , , , , -, n ( n + 1). , O(n).
, : , , , , _
_
. , :
( . )
, (, 'd', 3)
, f
defg
. , , 3. (, 'd', 3)
. d
-, - de
, 2 . , , , (, 'f', 1)
.
_
,
, n. , , , , , n . , O(n2),
O(n), - _
O(n)?
. , (, , ), , , _
. , , , _
, , , , _
. _
,
,
O(n) , , -
O(n), O(n).
Notas do tradutor
Em geral, o algoritmo é descrito em uma linguagem fácil e compreensível. Seguindo a descrição, é possível implementá-lo, e otimizações naturais acontecerão em tempo real. Eu destaquei os lugares que criaram dificuldades para mim com spoilers.
Na minha implementação , o alfabeto ACGT é usado, uma vez que perseguia o objetivo de passar nos testes de um problema dentro de um curso.