5分で分かる!？ 有名論文ナナメ読み

摘要

文書から任意の文字の並びを検索することを全文検索と呼ぶ.全文検索を高速に行うためには，あらかじめ文書を検索しやすいように索引化しておけばよい.索引法の1つとして知られる接尾辞配列は，文書中に現れるすべての接尾辞A1を辞書順にソートし，各接尾辞の出現位置を記録したデータ構造である.図-1に文書："ATGAATGCGA$"の接尾辞配列を示す.接尾辞配列では，接頭辞が共通する接尾辞は隣り合うため，パターン"ATG"の存在を確かめるには接尾辞配列を二分探索すればよいのだが，文書の大きさに依存した検索時間が必要となってしまう.本稿では，接尾辞配列と密接な関係があるBurrows-Wheeler変換（BWT)を用いて文書の大きさに依存しない検索時間を実現した索引法の論文を紹介する.本論文自体の引用件数は1,012 にとどまるがな2，この画期的な索引法は後にFM-indexと名づけられ30,000件を超える研究論文で利用されている.FM-indexは一体何に応用されたのか.