接尾辞配列 検索方法

ウィキペディア

接尾辞配列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/19 15:57 UTC 版)

検索方法

接尾辞配列を使えば検索対象文字列の出現位置を高速に検索することができる。接尾辞配列においては、文字列が出現する位置を求めることはつまり、その文字列で始まっている接尾辞を求めることと同じである。接尾辞配列は辞書順にソートされているので、検索対象となる文字列の検索には、高速な二分探索アルゴリズムが利用できる。$m$を検索文字列の長さとすると、単純な実装では二分探索で $O(m\log n)$の計算時間になる。

直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合、その最大文字数を最長共通接頭辞（LCP, Longest Common Prefix）と呼ぶが、あらかじめ求めておいたLCPにより無駄な比較を省き検索を高速化することができる。このとき、$O(m+\log n)$ の時間で検索できる。

ブロックソート

接尾辞配列のソートアルゴリズムを利用して ブロックソート (Burrows-Wheeler 変換, BWT) を行うこともできる。技術的に、ブロックソートには接尾辞ではなく巡回シフトした文字列の辞書順のソートが要求される。このため、すべての文字列に番人としての文字"$"などを加えて巡回シフトを行うことで、接尾辞配列と同等の結果を得られる。

歴史

接尾辞配列は、接尾辞木と比べメモリ消費の少ない手法として、ジーン・マイヤーズとウディ・マンバーによって開発された。これにより圧縮された接尾辞配列とBWTベースの圧縮全文インデックスへの傾向が強まることとなった。

2000年に、圧縮全文インデックスとして、圧縮接尾辞配列やFM-Indexが登場する。