文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。
文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。ヘルシンキ大のDjamal BelazzouguiさんとSimon J. Puglisiさんとの共著論文です。arXivからダウンロードできます。
Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei: Rank, select and access in grammar-compressed strings 論文へのリンク(arXiv)
内容はタイトルが示す通り文法圧縮されたテキスト上のrank/select/accessに関するものです。一般の文字列上のrank/select/access操作はFM-indexを代表とするさまざまなデータ構造を実装する際の重要なデータ構造であることは良く知られています。これらの操作を実現する代表的なデータ構造にWavele木があります。
一方、文法圧縮は反復テキストという同じ部分列を多く含むテキストのクラスに対して高い圧縮率を達成するという良い性質があり、文法圧縮されたテキスト上での効率的なrank/select/accessに関する研究は既存のデータ構造を反復テキストに対してより効率的に処理できるように改良する可能性を秘めています。これまでの研究は構文木がバランスされている場合を仮定したアルゴリズムしか提案されていませんでした。今年のSPIREに[1]があります。実用的にはこれで良いのかもしれませんが、今回はより一般的な場合である構文木がアンバランスな場合を仮定して議論を進めています。論文中では、一般的な構文木上でのrank/select/access操作の困難性を提示した後、これらに対するアルゴリズムを提案しています。
[1] Gonzalo Navarro and Alberto Ordonez: Grammar Compressed Sequences with Rank/Select Support. To appear in Proc. SPIRE'14.
NIPS2013読み会で発表しました
東大で開催されたNIPS2013読み会で発表させていただきました.
http://connpass.com/event/4728/
参加者60人と大盛況で, 機械学習の人気の高さを再確認しました.
僕は, Scalable graph kernels for continuous attributesというタイトルの論文を発表しました.
要点は
- ノードに実数値ベクトルをもつグラフに対するGraphHopper Kernelを提案
- 類似度は２つのグラフに存在する同じ長さの最短路上のノードの類似度の和で定義
- 式変形により最短路におけるノードを通過する回数に関するforward-backward計算に帰着
- 実際のグラフに対しては, ノードの数の２乗で計算可能
- 高速かつ高精度
です.
下は発表スライドです.
2013年度の文法圧縮の進展
年が明けて2014年の１月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。
はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます.
文法圧縮には２つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズムが提案されてきました. 代表的な手法にRePairというGreedyアルゴリズムがあります。, RePairは入力文字列の各２文字ペアーに着目し, 再頻出ペアーを新しい非終端記号に置き換えるという操作を収束するまで繰り返します。オンラインアルゴリズムにはLCAと呼ばれるアルゴリズムがあります.
２つ目の問題は, 構築したCFGをいかに符号化するかという問題で, CPM2013の論文ではCFGの符号化に関する情報理論的下限を示しました.
論文とスライドを以下に置きます.
Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto: A Succinct Grammar Compression, 24th Annual Symposium on Combinatorial Pattern Matching (CPM), 2013. 論文(PDF)
さらにSPIRE2013では, 入力文字列読みつつオンラインでCFGを構築し, 直接簡潔表現にエンコードする完備オンライン文法圧縮法を提案しました. この手法における簡潔表現はCPM2013で提示したCFGの簡潔表現の情報論的下限に漸近的に一致します.
Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane: Fully-Online Grammar Compression, 20th String Processing and Information Retrieval Symposium (SPIRE), 2013.
今年のDCC2014では, この完備オンライン文法圧縮を定数領域で動くように改良しました. これにより巨大文字列に対しても, 予め決めたメモリーで文法圧縮することができます.
Shirou Maruyama and Yasuo Tabei: Fully-Online Grammar Compression in Constant Space, Data Compression Conference (DCC), 2014. (論文準備中)
2014/1/22更新
DCC2014論文をarXivにアップしました。
http://arxiv.org/abs/1401.5143
2013年前半振り返り
暑い日々が続きますが、いかがお過ごしでしょうか？ 早いもので2013年もう８月ということでだいぶ遅いですが2013年の前半の成果を振り返ってみたいと思います。幸いにも2013年の前半に4本論文を出す事ができました。内分けは、データマイニング・機械学習1本、バイオインフォマティクス1本、 文字列処理２本となります。以下では１つ１つ論文の内容を簡単に紹介していきたいと思います。
Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, Yoshihiro Yamanishi: Succinct Interval Splitting Tree for Scalable Similarity Search of Compound-Protein Pairs with Property Constraints, 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2013 論文PDFへのリンク
データマイニングと知識発見に関するトップ国際会議SIGKDD2013の論文。内容は、化合物・タンパク質ペアーを高速検索するための簡潔データ構造を提案したというもの。化合物・タンパク質ペアーはフィンガープリント(バイナリーベクトル)として表現できる。一方、化合物・タンパク質ペアーは実数値で表現される性質 (例えばLogP値, タンパク質の表面積など)を持つ。よって、タンパク質・化合物ペアーの検索問題はクエリーに対して(i)フィンガープリントが似ているかつ(ii)性質が似ているペアーをデータベースからすべて発見する問題として定式化できる。近年の、ドラッグ・ターゲット相互作用データベースの登場そして大規模化によりこの問題はますます重要度を増しています。たとえば、今回扱ったドラッグ・ターゲット相互作用データベースは約２億の相互作用を含みます。一方、フィンガープリントの検索問題は、データマイニングとケモインフォマティクスの分野で非常に良く研究されているが、(i)フィンガープリントの類似度にだけに基づく手法に対しては大規模データベースにたいしては検索速度に問題があり使い物になりません。そこで、(i)と(ii)の類似度にもとづき化合物-タンパク質ペアーを高速検索するための簡潔データ構造を提案しました。提案手法は(i)のフィンガープリントの類似度に基づく手法よりも100-1000倍高速に検索することができます。
KDD発表日とある面接日が8月12日と重なってしましい、東京で面接受けてすぐにシカゴに飛んで自分の発表の15分まえに会場に到着して研究発表するという無茶をやってのけました。これは一生忘れない....
Masaaki Kotera, Yasuo Tabei, Yoshihiro Yamanishi, Toshiaki Tokimatsu, Susumu Goto: Supervised de novo reconstruction of metabolic pathways from metabolome-scale compound sets, ISMB/ECCB2013. 論文へのリンク
バイオインフォマティクスに関するトップ国際会議ISMB/ECCB2013の論文。内容は代謝ネットワークを化合物集合から再構築する手法を開発したというもの。主な工夫点は、化合物ペアーからネットワークを高精度に予測するための解釈可能な特徴量を作ったところで、この特徴量とスパース分類器を組み合わせることにより、ネットワークを高精度に予測しつつ、予測に貢献する化合物の部分構造を抽出することに成功している。
ISMB/ECCBに参加したのは2007年の6年ぶりでした。分野はだいぶdivergeしている印象でした。
Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto: A Succinct Grammar Compression, 24th Annual Symposium on Combinatorial Pattern Matching (CPM), 2013. 論文(PDF)へのリンク
文字列パターンマッチングに関する国際会議CPM2013の論文。主な内容は文法圧縮されたテキストをエンコーディングする際の情報論的下限を示したというもの。証明の際には、DAGのスパニング木分解、順序木の列挙など技をいろいろ使っています。その他、提示した情報論的下限を漸近的に達成するエンコーディング法も提示しています。
Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane: Fully-Online Grammar Compression, 20th String Processing and Information Retrieval Symposium (SPIRE), 2013.
文字列と情報検索に関する国際会議SPIRE2013の論文。本論文では圧縮サイズがCPM2013で示した情報論的下限を漸近的に達成するオンライン文法圧縮を提示しました。提案法により文字列をオンラインで読みつつ、直接的に簡潔表現にエンコードする(Fully-Online)ことができます。簡潔表現では部分文字列復元もサポートしています。
GW前に締め切りが延期されたこともあって急遽仕上げることになった論文で、GW中ずっと篭って論文書いていました。共著者の皆様にはご迷惑をお掛けしました。
大規模フィンガープリント類似検索のための簡潔マルチビット木の実装を公開しました
以前のブログで紹介した簡潔マルチビット木のc++による実装 (Succinct Multibit Tree (SMBT)) を公開致しました。ソフトウェアーはgoogle codeからダウンロードすることができます。
http://code.google.com/p/smbt/
SMBTは去年のWABIで発表した内容にもとづいています。
簡潔マルチビット木に関するブログ記事 :
http://d.hatena.ne.jp/tb_yasu/20120808/1344415559
論文 :
Yasuo Tabei: Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches, Workshop on Algorithms in Bioinformatics (WABI) ALGO, 2012 論文PDFへのリンク
発表スライド :
以下ではSMBTの簡単な使い方を解説します。はじめにソースをダウンロードして解凍してコンパイルします。
tar -xzvf smbt-X.X.X.tar.bz2 cd smbt-X.X.X make
SMBTはフィンガープリントデータベースを入力として、類似度検索のための索引を作成します。このためsmbt-buildコマンドを使用します。
./prog/smbt-built -mode 1 ./dat/fingerprints.dat index
fingerprints.datは入力となるフィンガープリントデータベースのファイル名で、indexは出力の索引ファイルです。
modeは1,2,3から選べます。簡潔マルチビット木を使うためには1または2を、ポインターによるマルチビット木を使うためには3を指定します。この例では１の簡潔マルチビットを使用しています。メモリー使用量は 3 > 2 > 1の順で3のポインターによる実装が最もメモリーを使用し、1の簡潔マルチビット木の実装が最もメモリー効率が良いです。検索速度は 3 > 2 > 1の順で3のポインターによる実装が最も早く、1の簡潔マルチビット木が最も遅くなります。
このトレードオフがどの程度かを下のテーブルに示しています(論文からの抜粋)。データはPubChemデータベースから3千万化合物フィンガープリントを用いて、類似度のしきい値0.98, 095, 0.9におけるクエリー１つあたりの検索時間とメモリーのトレードオフを調べています。SMT+TRIEがmode=1, SMT+VLAがmode=2, MT+RAWがmode=3に対応しています。mode=3で, メモリーを20GB消費して検索時間が0.98,0.95,0.9の各しきい値で0.006秒, 0.048秒, 0.294秒、mode=2でメモリーが4GBで検索時間が0.014秒, 0.114秒, 0.724秒, mode=1でメモリーが2GBで検索時間が0.021秒, 0.182秒, 1.7秒程度となります。
注意として、自然言語処理などの単語をフィンガープリントとした場合、単語の種類数が多くなり圧縮が効かなくなる場合があります。その場合はmode=3のポインターによるマルチビット木を使う方が良いです。
作成した索引からクエリーフィンガープリントの類似検索を行うためには、smbt-searchコマンドを使用します。
./prog/smbt-search -similarity 0.8 index ./dat/fingerprints.dat
indexはsmbt-buildコマンドで作成した索引ファイル、fingerprints.datはクエリーフィンガープリントです。 -similarityにて類似度のしきい値を指定します。類似度はJaccard (Tanimoto)類似度です。この例ではしきい値0.8を指定しています。
SMBTの実装では岡野原さんによるrank/select辞書の実装rsdicを使わさせていただいております。
http://code.google.com/p/rsdic/
会議はスロベニアのリュブリャナで開催されました。リュブリャナは町並み気候ともよく楽しめました。会議規模はちょうどよいくらいで、会議の参加者でポストイナ鍾乳洞に行く遠足もありました。
SPIRE2012の効率的な文法圧縮のための可変長コードに関する論文とオンライン文法圧縮のソフトウェアー (olca++)を公開しました。
SPIRE2012で発表したメモリー効率の良い文法圧縮のための可変長コードに関する論文を公開しました。
Y.Takabatake, Y.Tabei, H.Sakamoto: Variable-Length Codes for Space-Efficient Grammar-Based Compression, Symposium on String Processing and Information Retrieval (SPIRE), Cartagena, Colombia, 2012. Link to the PDF
上記の論文に基づくオンライ文法圧縮(online LCA)のC++による実装(olca++)を公開しました。
下のサイトからダウンロードできます。
https://code.google.com/p/olca-plus-plus/
文法圧縮のアルゴリズムは@marugorithmさんが開発したonline LCA[1]に基づいています。online LCAは、入力文字列からそれを一意に復元可能な文脈自由文法の生成規則を作成することで文字列を圧縮します。online LCAは名前から想像できる通り、入力文字列を一文字づつ読みつつ生成規則を作成するので入力文字列自体をメモリーに保つ必要はありません。
文法圧縮アルゴリズムを実装する上でメモリーは、(1)入力文字列、(2)文法の生成規則を格納する辞書と呼ばれる配列、(2)ハッシュテーブルで消費されますが、online LCAでは(2)辞書と(3)ハッシュテーブルでほとんどのメモリーが消費されます。一般的にハッシュテーブルは生成規則を逆引きするために使用され、衝突を解消するためにキーと値の両方を保持する必要があります。 文法圧縮の場合、衝突が起こった場合でも辞書を参照すれば衝突を解消することができるのでキーをメモリーに保持する必要はありません。そのため、文法圧縮では(2)辞書によりほとんどのメモリーが消費されることになります。
そこで、今年のSPIREでメモリー効率良く文法圧縮を実装するために可変長コードから辞書を提案しました。関連研究として、ガンマ符号に基づく可変長コードからなる配列[2]と、[2][4]に基づく@hillbigさんによるライブラリーdag_vector[3]があります。しかし、ガンマ符号は小さい値を表現するには有効ですが、大きい値を表現した場合その値は固定長ビットを超えることがあります。例えば、65536(=2^16)以上の値をガンマ符号で表現すると32ビットを超えます。そのため、これらの配列は文法圧縮での応用には有効な手法ではありませんでした。提案手法はこの点を克服しています。online LCAと組み合わせることにより、従来のarrayや[2]の配列を使った実装よりもおおよそ1/3のメモリーで文法を構築することができます。
[1] S. Maruyama, H. Sakamoto, M. Takeda, An Online Algorithm for Lightweight Grammar-Based Compression, Algorithms 5(2):214-235, 2012.
[2] N.R.Brisaboa, S.Ladra, and G.Navarro, Directly addressable variable-length codes in SPIRE, pages122-130, 2009.
[3] https://github.com/pfi/dag_vector
[4] http://lbd.udc.es/research/DACS/
下はコロンビアの写真
