Suffix Vector まとめ
- Krisztian Monostori さんの博士論文[2005-11-02-1]が原典
- suffix tree を格納する形式のひとつ
他の形式： suffix tree は木なので、一般的な木の格納形式が使える
suffix tree 特有の冗長性を利用した、より効率的な格納形式がありえる
- ほかにも冗長性を利用した格納形式はある（DAG とか）が、いまのところ実用上領域最小なのが Suffix Vector
- 冗長性：同型な部分木が多い
+ABC+--DEF
+--GHI↑のような部分木があったとき、
↓のような部分木、またはそれにいくつかの部分木を加えた部分木がかならず存在する。
+BC+--DEF +--GHI
+C+--DEF +--GHI
- ↑の例で、Aが1文字目、Bが2文字目、… つまり S[0..4] = ABCDEF
だとする。
３つの部分木の分岐ノードは、そこに流入する枝の最後の文字のインデックスが同じという共通点を持つ。
（自然なラベルづけ：木の構築時に、ラベルづけは初出位置のインデックスを用いる ことを仮定）
これを利用して、これらのノードの情報を「流入枝ラベルの初出位置」に格納し、そこで共通部分を共有させる。
- 根はこの方法だとどこにも置けないので、根だけは特別に通常の木の表現で格納。
- 流入枝の初出位置を共有するノード集合を格納するものを box と呼ぶ
- box 内で、ノードの深さ順に並べられ、隣り合うノードの深さの差は1文字
- ノードから流出する枝は、同様に初出位置（の開始と終了）へのポインタとして表現
- １つの box 内のすべての流出枝は、１つの連結リストとして格納され、
あるノードから出る枝の集合は、その連結リストの部分リストとして表現できる
（流出枝の集合は、深さの増加に対して同じか減る … 文脈がより長く与えられるため）
- 文字列が与えられたとき、どの枝をたどればいいかを探すには
連結リストを順に調べる（連結リストの長さはアルファベットの大きさ以内）
- 根からラベルにしたがって枝をたどり、葉にたどりつく
↑↓
根からラベルにしたがって、そのラベルの初出位置に行き、
そのラベルと異なりが出た位置で box に入り、適切な深さのノードを選んで、
つづきの枝を求め、たどり、葉にたどりつく
