接尾辞配列 検索方法

接尾辞配列

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

検索方法

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

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

ブロックソート

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

歴史

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

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


  1. ^ Manber, Udi; Myers, Gene (1990). “Suffix arrays: a new method for on-line string searches”. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327. http://dl.acm.org/citation.cfm?id=320176.320218 
  2. ^ Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). “Linear Suffix Array Construction by Almost Pure Induced-Sorting”. 2009 Data Compression Conference. pp. 193. doi:10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0 
  3. ^ sais
  4. ^ SUFARY 臨時復旧ページ
  5. ^ sary: Suffix Arrayのライブラリとツール


「接尾辞配列」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「接尾辞配列」の関連用語

接尾辞配列のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



接尾辞配列のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの接尾辞配列 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS