接尾辞配列
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/19 15:57 UTC 版)
接尾辞配列(せつびじはいれつ)やサフィックス・アレイ(英: suffix array)とは、文字列の接尾辞(開始位置を異にし終端位置を元の文字列と同じくする部分文字列)の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した[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
- ^ 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
- ^ sais
- ^ SUFARY 臨時復旧ページ
- ^ sary: Suffix Arrayのライブラリとツール
- 1 接尾辞配列とは
- 2 接尾辞配列の概要
- 3 検索方法
- 4 実装
- 接尾辞配列のページへのリンク