Suffix Tree から Sparse Suffix Tree への変換

Sparse Suffix Tree とは、Krisztian さんの論文[2005-11-02-1]で紹介されている、
単語単位 Suffix Tree のようなもの。
形式的には、文字列と文字列中でのすべての単語の開始位置（区切り記号の位置 -1）が与えられたとき、
単語の開始位置から始まる suffix のみを含む suffix tree。

単語辞書と文字単位 suffix tree が与えられたとき、
木を sparse suffix tree に変換するために、連結のアルゴリズムが使える。
単語辞書を長さ順にソートして、各単語内の先頭2文字から順に
[2005-11-01-1]の方法で連結に関する更新を繰り返していくと、
sparse suffix tree が得られる。

変換の最悪の計算時間は、辞書の合計長 x 単語出現頻度の最大値 か？
たぶんあまり頭のいい方法ではない。

sparse suffix tree は suffix tree と比べて、
matching statistics algorithm という文字列間の類似度判定を行う際に、
単語の途中から始まるsuffix を考慮しない点で効率がいい、とか書かれている。