Suffix Arrayメモ

プログラミング

はじめに

Suffix Arrayあたりをちょっと調べてみたのでとりあえずメモ。
調べてみたら結構研究されていて全部まとめるのが面倒あとできちんと理解しておきたい。

Suffix Array(接尾辞配列)とは

  • 文字列に対して、その文字列の接尾辞集合を辞書順ソートしたもの
  • ここでの接尾辞集合は「abcd」という文字列の場合、以下の4つの接尾辞になる
abcd
bcd
cd
d
  • これは各インデクスから最後までの部分文字列なので、元の文字列があればインデクスから部分文字列を得ることができる
  • 与えられた文字列からある文字列が含まれるかどうかを検索したい場合、Suffix Arrayは辞書順に並んでいるので、2分探索することで高速に検索することができる

構築方法

普通のQuicksort
  • 普通に文字列をソートする方法
    • QuicksortにO(n log n)、文字列比較にO(n)かかる
Mamber-Myers
Larsson-Sadakane
  • 上記のMamber-Myersの方法を発展させた方法
  • Multikey quicksortを使う
二段階ソート法
三分割法
Seward Copy Algorithm
Ito-Tanaka Algorithm
Manzini & Ferragina(Deep Shallow Sorting)
Ko & Aluru
Karkkainen & Sanders
Burkhardt & Karkkainen(Difference-Cover algorithm)
Induced sorting(SAIS)
  • Linear Suffix Array Construction by Almost Pure Induced-Sorting
  • Two Efficient Algorithms for Linear Suffix Array Construction
  • 2009年の論文でこれまでのSA構築アルゴリズムと比較して最強ぽい

関連

高さ配列
  • SuffixArrayにおいて、i番目の接尾辞とその次の接尾辞との共通接頭辞の長さを要素に持つ配列
    • (Ngramカウントのときの話で出てきた)
  • 接尾辞木(SuffixTree)を計算することでO(n)で構築できる
Compressed Suffix Array
FM Index
LZ-index
Repair Suffix Array

参考ページ