データ構造

Last updated Unknown Edit Source

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

  • 計算時間
  • メモリ量

• を小さくしたい

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

  • そうすると、さらにメモリ量が増える
  • このトレードオフ状態、データの構造を工夫して改善する

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

  • 接尾辞木 ([[木]]構造)
    • 接尾辞のリストを、一文字一節の[[木]]構造で持つ
    • 効率がいいけど、メモリを多く使う
  • 接尾辞配列
    • 接尾辞 = suffix (n番目~最後までの部分文字列)
    • 単純に、全ての接尾辞を辞書順でソートして並べた配列
    • 接尾辞木よりは軽量
  • 圧縮接尾辞配列
    • 機能
      • 接尾辞配列のi番目、接尾辞配列の逆配列のi番目を$O(\log n)$時間で出せる
      • 文字列の部分文字列を$O(\log n + l)$時間で出せる
    • この二つがあると、ある接尾辞より一文字短い接尾辞の場所が分かる?
      • これと、T(元の文字列)があれば検索が素早く?できる

• 簡潔表現

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

  • L通りの入力がある場合は、下限は$\lceil \log L \rceil$bits

  • 簡潔索引

    • ビットベクトル/配列 (ex: {1,0,0,1,1,0,1}みたいな) へ、
      • rank操作: ある範囲に存在する1の数を返す
        • 簡潔索引: サイズが最小になるようにブロックに分割して、それぞれのブロックへの問い合わせの答えをあらかじめ用意しておく?
          • 正しく理解できていない気がする
      • select操作: i番目の1の位置を返す

  • 木構造の簡潔表現

    • [順序木]の場合
      • LOUDS表現
        • 節点の次数を、幅優先順に1進数で符号化
        • 1進数符号化: 1が並んでる数で数字を表す
          • なぜ? –> 0は区切りに使いたいから
        • これはビットベクトルになるので、簡潔索引のrankとselectを駆使すれば木に関するいろいろな処理ができる
      • BP表現
        • (()((())())())(()())())、のような表現
        • 階層構造をカッコで表す、(が0、)が1みたいな
        • findcloseなどの操作を実現するために、区間最大最小木というデータ構造を使う
          • ブロックに分割して、各ブロックの最大値、最少値を持つ
          • そのブロックで木構造を作る
          • そうすると、fwd_searchができる