簡潔データ構造
Succinct Data Structure
簡潔データ構造は、操作が高速でありながら作業領域量が小さいという2つの性質を兼ね備えたデータ構造であり、データ圧縮と索引の技術が組み合わさったものである ( #高速文字列解析の世界 p. 41)
要するに可変長のデータ列を効率的に扱うためにはデータ長だけのビット列を用意してやってビット列上の位置から何番目のデータなのか知るにはrankを、データからビット列上の位置を知るにはselectを使えば良いよ、という話。 「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「ウェーブレット木」の実装には「簡潔データ構造」が必要で、さらに前述のとおり「ウェーブレット木」を用いることで「BWT」が効率化出来る。つまり「簡潔データ構造」→「ウェーブレット木」→「BWT」という順で応用に向かっていく 「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei