Suffix Array(接尾辞配列)を学びたい人のためのリンク集

私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。
CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。

解説記事

# ［を］ Perl による Suffix Array の実装]
SUFARYの開発者、たつを氏による解説
perlで20行くらいでSuffix Arrayが作れる
入門用におすすめ
　　　　
# DO/Suffix Array
岡野原氏によるSuffix Arrayの解説記事
高速化などの高度な話題が豊富
中級者向け
　　　　
# white page
Suffix Arrayのリンク集が充実
多くのライブラリが公開されている

ツール・ライブラリ

# SUFARY 臨時復旧ページ
たつを氏によるSuffix Arrayライブラリ
非常に使い勝手が良い

# sary: Suffix Arrayのライブラリとツール
高林哲氏によるSuffix Arrayライブラリ

# 定兼 邦彦 - 圧縮接尾辞配列ライブラリ csalib
定兼 邦彦氏によるCompressed Suffix Arrayライブラリ
FM-Indexを使っている(多分)
元テキストの1/3くらいに圧縮
オブジェクト構築にちょっと時間がかかる
複数のアルゴリズムがオプション切り替え可能
Pizza&Chili APIに準拠
　　　　
# Pizza&Chili Corpus
CSAライブラリやテストコレクションがまとまったサイト
コーパスという名前に混乱しないように
統一インタフェース(Pizza&Chili API)を提案
各種ライブラリのラッパーが公開されている

論文

# Suffix Array
Suffix arrays: A new method for on-line string searches
(U. Manber & G. Myers, 1989)
元祖Suffix Array

# Multi-key Quicksort
Fast Algorithm for Sorting and Searching Strings
(J. L. Bentley & R. Sedgewick, 1997)
高速な文字列ソート
Suffix Arrayの構築を現実的な速度で実行するために利用する

# Vertical Code
現実的な圧縮付全文索引
(岡野原 大輔, 2005)
高速、高圧縮な圧縮データ構造。CSA実装時に利用する
その他CSAに関する話題が纏まっていて資料として価値が高い

# Compressed Suffix Array
Compressed Text Databases with Efficient Query Algorithms based on the Compressed Suffix Array
(Kunihiro Sadakane, 2000)
定兼版CSA。一般にCSAといったらこれ

Compressed suffix arrays and suffix trees with applications to text indexing and string matching
(R. Grossi & J. S. Vitter, 2000)
元祖CSA。定兼版を理解できなかったら、こっちから読むと良い

# FM-Index
Opportunistic Data Structures with Applications
(P. Ferragina & G. Manzini, 2000)
元祖FM-Index。データ構造が微妙

An alphabet-friendly FM-index
(P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004) 
データ構造にWavelet木を採用したFM-Index
大変賢い手法