はじめに 本記事は圧縮文字列索引についての連載第3弾である。 前半は、文字列圧縮のために提案された概念であるBurrows-Wheeler Transform(BWT)*1について、そしてそれを用いた文字列検索アルゴリズムについて説明する。 後半にはBWTを利用した文字列索引の…

はじめに 本記事は圧縮文字列索引に関する連載のpart2である。 今回は「接尾辞配列（Suffix Array）」について説明する。これ自体は圧縮文字列索引ではないが、多くの索引のベースとなっている重要な概念だ。 はじめに 文字列の定義 接尾辞配列とは 接尾辞配…