はじめに 本ブログでは現在、圧縮文字列索引に関する連載を書いているが、そこのpart3で「経験エントロピー」なる概念が登場した。そこではさらっと流してしまったので、改めて丁寧に解説する記事も別に書こう、ということで本エントリに独立させることにし…

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

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

はじめに 本記事から、連載という形で圧縮文字列索引についての現状を紹介しようと思う。 本エントリは、アルゴリズムの詳細には踏み込まずに、圧縮文字列索引とは何か、そしてその研究の経緯について紹介する。加えて、今後書いていく各エントリへのリンク…