話題の新技術、簡潔データ構造の入門用資料をまとめてみた

最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ！と個人的に思っている。
というわけで入門用の資料をまとめてみた。

簡潔データ構造では、すべての基礎である簡潔ビットベクトルがあって、その上に応用として簡潔木(LOUDSなど。Google日本語入力で利用されている)、簡潔文字列(ウェーブレット木など。FM-Indexに利用されている)がある。最近ではこれらより複雑なデータ構造に対する簡潔構造も研究されている。
ということをふまえて以下の資料を読むと良い。

Efficient dictionary and language model compression for input method editors
Taku Kudo et al.
Google日本語入力の論文。具体的な利用例を見ないと動機づけが困難という人向け。

私のブックマーク ： 簡潔データ構造
@tb_yasuさんの資料まとめ。ほとんどここを見ればOK。とても助かります。

ALSIP2011 Invited Talk
ALSIP2011の3つの招待講演は優れたまとめ資料になっている。
それぞれ定兼先生が木の簡潔構造を、岡野原さんが文字列の簡潔構造を、
Raman先生が木や文字列より複雑な簡潔構造をまとめて下さっている。
いずれの資料も冒頭で、基礎である簡潔ビットベクトルについては言及されている。

簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
入門用の論文をまとめた記事。(1)、(3)、(4)あたりを読んでおけば基礎はバッチリ。

簡潔データ構造超入門VI 〜これまでのまとめと集合の簡潔構造〜 - EchizenBlog-Zwei
入門用記事。実際に実装しつつ理解できるように書いたつもり。
簡潔ビットベクトルからLOUDSまでをカバーしている。