Ukkonen's algorithm

Suffix tree を線形時間で作るアルゴリズム．しかも文字列を先頭から処理できるオンラインアルゴリズムになっている．なぜかその元論文を読んだのでここにメモっておく．

とりあえず，二乗コストで suffix trie をオンラインに作るアルゴリズムがベース．この suffix trie は，各リーフが suffix に対応し，中間ノードは部分文字列に対応する．このアルゴリズムは，空文字列に対応する suffix trie から始め，それを逐次的に更新していくことで文字列全体に対する suffix trie を構成する．１文字追加することに対応する suffix trie の更新は，各ノードに持たせた suffix link を辿って行われる．suffix link は，そのノードの表現する部分文字列から先頭の一文字を取り去った文字列に対応するノードへのリンク（つまりは，suffix を取る操作に対応した状態遷移のこと）．

このベースとなるアルゴリズムは１文字分の更新にtrieの大きさに比例したコストがかかるため，二乗のコストがかかる．

Ukkonen のアルゴリズムのアイデアは，分岐せずに一列につながった suffix trie のノード達をその根元のノード一つで代表させること．実際のところ，ベースアルゴリズムで構成する suffix trie にはこういった一列に並んだだけのノード列が多く現れ，それらの suffix link の更新が非常に無駄だと感じる．

一文字追加する際の更新で少々面倒なのは，一纏めにされたノード達を適宜分割する操作が必要なこと．これ以外はベースと同じで，一纏めになっているノードに対して suffix link を保持していく．この作業は順次大きくなっていく木を下から上に辿るように行うだけなので（横に飛んだりするけれど概ね全部の分岐で上に向かうイメージ），結局のところならし計算量で線形コストになっている．あとは頭のいいインデックスを使っていて，その更新作業中にループが出てくるが，こちらもならしでループ本体が線形回しか呼ばれないので問題ない．そのならし計算量の見積りは，インデックシングに使われている文字列上のポインタ二つが常に大きくなる方向にしか動かないことによる．

まあ，並列化できそうにないね．