Suffix Treeを見た

Ukkonen'sを実装したりした。

graphvizで描画するとなんかかっこいい。

Suffix Arrayでも同じことができて、メモリ消費も少ない。Suffix Treeの利点は？

文字種が少なければ線形なので速いのかな？

文字種が多い時、各ノードに配列を持つのはかなりきつい。

Linked Listも文字種が少ない時はいいけれど多くなるとΘ(|Σ|)がきいてくる。

平衡木やハッシュマップはlog nや定数がまあまあある。

一番いい方法はどういう方法なんだろう？

『次数が少ないうちはリストで、閾値以上になったら配列にする』を考えてやってみた。

ランダム入力で文字種256くらいで閾値を適切に選べばまあまあよかった。

これってどうなんだろう？閾値に対して平均計算力とか出せる？

木なので、それがいいよね。いろいろとできそう。

とりあえずwikipediaにあるアルゴリズムは実装したい。そしたらSuffix Tree特集をしよう。