私のブックマーク
簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員)
はじめに
近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、
しかし、圧縮するとランダムアクセスをすることができないという欠点があります。
簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。
近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。
私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。
また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。
そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。
解説記事等
近年、簡潔データ構造はWebやゲノム処理などで主に使われていて、それらに携わっている研究者及びエンジニアの方がブログなどをつうじて解説記事を公開しています。
ここでは、それらのなかで分かりやすい記事及び資料を紹介します。
- 簡潔データ構造の講義資料 http://researchmap.jp/sada/succinct/
- 国立情報学研究所の定兼先生の講義資料。簡潔データ構造の基礎から応用までが網羅されている。
- ビットベクトル上のrank/select辞書の解説記事 http://codezine.jp/article/detail/260
- PFIの岡野原さんによるビットベクトルの解説記事。2006年の解説記事のため解説内容は若干古く、現在はより効率的な手法が提案されている。
- 一般の文字列上のrank/select辞書の解説記事 http://codezine.jp/article/detail/261
- 同じく岡野原さんによる一般の文字列上のrank/select辞書(ウェーブレット木)の解説記事。
- wat-array : wavelet木を利用した高速配列処理ライブラリ http://research.preferred.jp/2010/12/wat-array/
- 岡野原さんによるwavelet木のライブラリwat-arrayの解説記事。
- 簡潔データ構造超入門 ～つくって学ぶ簡潔ビットベクトル～ http://d.hatena.ne.jp/echizen_tm/20110811/1313083180
- echizen_tmさんによるビットベクトル上のrank/select辞書の解説記事。rank/select辞書の実装法がわかりやすく解説されている。
- 大規模キー集合の効率的な格納??法tx bep https://sites.google.com/site/daisukeokanohara/home/2007-1031-massiveKeys.ppt?attredirects=0
- 岡野原さんによる簡潔木と簡潔連想配列の解説資料。
- 最近のtrieの話（xbwなど） http://research.preferred.jp/2011/05/trie_survey/
- 岡野原さんによる最近の簡潔木XBWの解説記事。
- 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた http://d.hatena.ne.jp/echizen_tm/20101230/1293719318
- echizen_tmさんによる圧縮全文索引手法FM-indexの解説記事。
- Compressed Suffix Arrayの解説(1) -Suffix Array- http://d.hatena.ne.jp/echizen_tm/20100203/1265219641
- echizen_tmさんによる圧縮接尾辞配列の解説記事。
- 重要な論文へのリンク集 http://homepage3.nifty.com/wpage/links/index.html
- moriさんによる簡潔データ構造の重要な論文へのリンク集。重要な論文が手法別に分けられていて便利。
ライブラリ
簡潔データ構造のライブラリは整備されてきていて、実用的にも使えるものも数多く存在する。ここでは、役に立つライブラリーを紹介します。
- rank9sel http://sux.dsi.unimi.it/
- 高速なビットベクトル上のrank/select辞書の実装
- wat-array http://code.google.com/p/wat-array/
- 岡野原さんによるウェーブレット木の実装。文字列上のrank/select操作やウェーブレット木上の色々な操作が実装されている。
- libcds http://code.google.com/p/libcds/
- 簡潔木の実装。木の上のあらゆる操作を行うことができる。
- tx-trie http://code.google.com/p/tx-trie
- 岡野原さんによる簡潔木を用いたtrieの実装。文字列の辞書として用いることができる。
- ux-trie http://code.google.com/p/ux-trie
- tx-trieの圧縮率をさらに高めたtrieの実装。
- marisa-trie http://code.google.com/p/marisa-trie
- 矢田さんによるtrieの実装。
- XBW http://xbw.sourceforge.net/
- 簡潔木XBWの実装。
- fujimap http://code.google.com/p/fujimap
- 岡野原さんによる簡潔連想配列の実装。
- bep http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/bep-j.htm
- 岡野原さんによる簡潔連想配列の実装。
- FM-index Version2 http://www.cs.sunysb.edu/~algorith/implement/pizzachili/distrib/FM-indexV2/
- 圧縮全文索引FM-indexの作者Ferraginaらによる実装。
- FM-index++ http://code.google.com/p/fmindex-plus-plus/
- 私(田部井)によるFM-indexの実装。
- libcsa http://researchmap.jp/sada/csalib/
- 定兼先生による圧縮接尾辞配列の実装。
- tsubomi http://code.google.com/p/tsubomi
- echizen_tmさんによる圧縮接尾辞配列の実装。
- dag_vector https://github.com/pfi/dag_vector
- 岡野原さんによる圧縮配列の実装。
- Succinct Data Structure Library(SDSL) http://www.uni-ulm.de/en/in/institute-of-theoretical-computer-science/research/sdsl.html
- Simon Gogさんによる簡潔データ構造のライブラリ。rank/select辞書、木、連想配列、圧縮全文索引などいろいろな手法が網羅的に実装されている。
- Graph-Indexing Wavelet Tree http://code.google.com/p/gwt/
- 私(田部井)によるウェーブレット木を用いたグラフの類似度検索法の実装。
主な研究者
国内外の簡潔データ構造の研究をしている研究者を紹介します。
- 定兼 邦彦 准教授 (国立情報学研究所・情報学プリンシプル研究系) http://researchmap.jp/sada/
- 坂本 比呂志 准教授 (九州工業大学・知能情報工学科) http://www.donald.ai.kyutech.ac.jp/sakamoto-ken.html
- 岡野原 大輔 (株式会社 プリファードインフラストラクチャー) https://sites.google.com/site/daisukeokanohara/
- Gonzalo Navarro 教授 (University of Chile) http://www.dcc.uchile.cl/~gnavarro/
- Rasmus Pagh 教授 (Unversity of Copenhagen) http://www.itu.dk/~pagh/
- Rajeev Raman 教授 (University of Leicester) http://www.cs.le.ac.uk/people/rraman/
- Paolo Ferragina 教授 (University of Pisa) http://www.di.unipi.it/~ferragin/index.html
- Simon Gog (Ulm University) http://www.uni-ulm.de/en/in/institute-of-theoretical-computer-science/m/gog.html
国際会議・ジャーナル
簡潔データ構造の論文は主に理論計算機科学や文字列処理の文字列処理の国際会議やジャーナルから入手することができます。
最新動向を知りたい読者は下記の国際会議やジャーナルを参照してください。
- ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Algorithm Engineering and Experimentation (ALENEX)
- International Symposium on String Processing and Information Retrieval (SPIRE)
- International Conference on Experimental Algorithms (SEA)
- American Theoretical Informatics Symposium (LATIN)
- Algorithmica
おわりに
本稿では、簡潔データ構造に関するページやリソースを紹介しました。近年のデータの大規模化に伴い今後ますます重要度を増してくると思われます。文字列処理などで主に使われている簡潔データ構造ですが、今後はグラフや木などの構造化データに使われるものと予想されます。また、簡潔データ構造自体の発展も見逃せません。このブックマークが、簡潔データ構造に興味を持つ人の参考になることや、多くの人が興味を持つことのきっかけになれば幸いです。