ストリングスのアルゴリズムコースを勉強しているときに、サフィックスツリーを作成するという問題に直面しました。追加資料のリンクをたどると、「StackOverflowに関するこのすばらしいコメントを表示する」という推奨事項に出くわしました。与えられた無料の説明に従って研究および実装した後、Ukkonenのアルゴリズムは翻訳を共有することを決定しました。
以下は、Ukkonenのアルゴリズムを説明する試みです。最初に、単純な文字列（つまり、文字列に重複する文字が含まれていない）でどのように機能するかを示し、徐々に完全なアルゴリズムに拡張します。
いくつかの予備的な声明：
私たちが構築しているのは基本的にプレフィックスツリーです。これはルート頂点であり、そのエッジは新しい頂点に移動し、後続のエッジはそれらから移動します。
ただし、 プレフィックスツリーとは異なり、エッジラベルは単一の文字ではなく、各エッジのラベルは[from、to]のペアの数字（テキスト内の位置へのポインタ）です。この場合、各エッジには任意の長さの文字列が含まれますが、必要なのはO（1）メモリ（2つのポインタ）のみです。
基本的な原則
最初に、作成者は、非常に単純な文字列、重複文字のない文字列のサフィックスツリーを作成する方法を示したいと考えています。
abc
アルゴリズムは、左から右に段階的に機能します。行文字ごとに1ステップ。各ステップには複数の個別の操作が含まれる場合がありますが、操作の総数は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).
翻訳者のメモ
一般に、アルゴリズムは簡単で理解しやすい言語で記述されています。説明に従って、それを実装することが可能であり、自然な最適化がその場で行われます。ネタバレで困ったところを強調しました。
私の実装では、コース内の問題のテストに合格するという目標を追求したため、ACGTアルファベットが使用されています。