計算機で大規模なデーターを処理する時

を小さくしたい

計算時間減らそうとする時は、大体索引を作る

そうすると、さらにメモリ量が増える

このトレードオフ状態、データの構造を工夫して改善する

文字列検索を効率的にできるようにする方法 (索引の圧縮)

接尾辞木 (木構造)

接尾辞のリストを、一文字一節の木構造で持つ

効率がいいけど、メモリを多く使う

接尾辞 = suffix (n番目~最後までの部分文字列)

単純に、全ての接尾辞を辞書順でソートして並べた配列

接尾辞木よりは軽量

機能

接尾辞配列のi番目、接尾辞配列の逆配列のi番目をO(\log n)時間で出せる

文字列の部分文字列をO(\log n + l)時間で出せる

この二つがあると、ある接尾辞より一文字短い接尾辞の場所が分かる?

これと、T(元の文字列)があれば検索が素早く?できる

サイズが情報理論的下限にほぼ一致する表現

L通りの入力がある場合は、下限は\lceil \log L \rceilbits

簡潔索引

ビットベクトル/配列 (ex: {1,0,0,1,1,0,1}みたいな) へ、

rank操作: ある範囲に存在する1の数を返す

簡潔索引: サイズが最小になるようにブロックに分割して、それぞれのブロックへの問い合わせの答えをあらかじめ用意しておく?

正しく理解できていない気がする

select操作: i番目の1の位置を返す

木構造の簡潔表現

順序木(同じ親の子間に順序があるもの)の場合

節点の次数を、幅優先順に1進数で符号化

1進数符号化: 1が並んでる数で数字を表す

なぜ? --> 0は区切りに使いたいから

これはビットベクトルになるので、簡潔索引のrankとselectを駆使すれば木に関するいろいろな処理ができる

(()((())())())(()())()) 、のような表現

階層構造をカッコで表す、 ( が0、 ) が1みたいな

findcloseなどの操作を実現するために、区間最大最小木というデータ構造を使う

ブロックに分割して、各ブロックの最大値、最少値を持つ

そのブロックで木構造を作る

そうすると、fwd_searchができる