「Data Structures for Efficient String Algorithms」が良さそう

簡潔データ構造のサーベイ論文を探していたら良さそうなのを見つけたのでメモ。

Data Structures for Efficient String Algorithms Johannes Fischer; 2007

文字列検索に関する論文で、RMQs(Range Minimum Queries, 範囲内の最小要素を探す)や簡潔データ構造を用いて効率的なSuffix Arrayを実装するよ、という話みたい(RMQsがメインで簡潔データ構造については利用するほうがメインで実装についてはあまり書いてない様子)。
それぞれの技術についてどの論文を当たればよいかがきちんと書いてあるのでサーベイ論文としても価値がある気がする。
RMQsはSuffix Arrayを高速に検索する際の予備データ構造であるLCP Arrayに利用されている。アリ本にも出てきていて気になっていた技術なのでこれを機にしっかり勉強しようと思う。