SuffixTree 構築プログラムの最適化

数Mバイトのデータの木を作るのに、Gバイトに近いメモリを必要とするのを
改善しようと、プロファイラにかけてメモリ使用量の多い変数を探した。

java -agentlib:hprof=cpu=samples,heap=sites,file=sample.prof -Xms20M -Xmx1000M SuffixTree < sample.txt

cpu=samples は、ときどきVMの状態を見て、そのときどのメソッドを実行していたかを記録する。
heap=sites は、変数ごとのメモリ使用量を見る。

もっとも内側での、むだなインスタンス生成をなくしたところ、
2割程度のメモリ使用量減少につながったみたい。
しかし、1桁落とすくらい（数十Mバイトを、2Gバイトのメモリで扱いたい）には至らず。

500kB, 1000kB ,1500kB ,... のランダムな UTF データで実行時間を
測定したところ、どうも線形時間で動いていない。
（メモリ使用量はおそらく線形だが）

アルゴリズムを見直す必要がある。
線形時間になっていない原因として２つが考えられる。

1. いまの実装にバグがある
suffix link まわりが怪しい。
suffix link はあるべきところにないとか、
不必要に上層すぎる場所につながっていても、ただしく動くので、
結果に誤りはでないが速度が落ちる。

2. アルゴリズムの問題
suffix tree 関係の論文には、
空間効率を改善するとか、大きなデータを扱うときに実用性が高い、
とかいうアルゴリズムがある。
Ukkonenのアルゴリズムは、オーダーでは線形だが、
メモリアクセスの非局所性、領域量の定数部分の大きさ（suffix link分）
などに問題点が指摘されている。

1. を見直すために、木の可視化がどうしても必要。