Mientras estudiaba el curso Algoritmos sobre cadenas , me enfrenté al problema de construir un árbol de sufijos . Siguiendo el enlace para materiales adicionales, encontré una recomendación para "ver este gran comentario sobre Stack Overflow ". Habiendo estudiado e implementado de acuerdo con la descripción gratuita dada , el algoritmo de Ukkonen decidió compartir la traducción.
A continuación se muestra un intento de describir el algoritmo de Ukkonen; mostrando primero cómo funciona en una cadena simple (es decir, la cadena no contiene caracteres duplicados), expandiéndose gradualmente hasta el algoritmo completo.
Algunas declaraciones preliminares:
Lo que estamos construyendo es básicamente un árbol de prefijos . Este es el vértice raíz, cuyas aristas salen de él a nuevos vértices, y las aristas subsiguientes salen de ellos, y así sucesivamente.
Pero , a diferencia de un árbol de prefijos, las etiquetas de los bordes no son caracteres individuales; para cada borde, la etiqueta es un par de números [desde, hasta]: punteros a posiciones en el texto. En este caso, cada borde contiene una cadena de longitud arbitraria, pero solo ocupa O (1) memoria (dos punteros)
Principio básico
Primero, el autor quiere demostrar cómo crear un árbol de sufijos de una cadena extremadamente simple, cadenas sin caracteres duplicados:
abc
El algoritmo funciona en pasos, de izquierda a derecha . Un paso por carácter de línea . Cada paso puede involucrar más de una operación individual, pero veremos (ver las observaciones finales al final) que el número total de operaciones 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 del traductor
En general, el algoritmo se describe en un lenguaje fácil y comprensible. Después de la descripción, es posible implementarlo y las optimizaciones naturales ocurrirán sobre la marcha. Destaqué los lugares que me causaron dificultades con spoilers.
En mi implementación , se utiliza el alfabeto ACGT, ya que persigue el objetivo de aprobar pruebas para un problema dentro de un curso.