文法圧縮上でのaccess、rank、select操作に関する論文が、アルゴリズム分野のトップ会議ESA2015に採択されました。 Djamal Belazzougui, Patrick Cording, Simon J. Puglisi, Yasuo Tabei: Access, rank, and select in grammar-compressed strings, 23rd European Symposium on Algorithms (ESA), 2015. 内容は、以前このブログで紹介した論文です。 文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。 %6月20追加 早くもaccepted paper listが出ているようです。 http://algo2015.upatras.gr/esa/accepted.html

様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 Data Compression Conference (DCC2015)に採択された論文でarXivから入手出来ます。 Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Alberto Ordóñez, Simon J. Puglisi, Yasuo Tabei: Queries on LZ-Bounded Encodings, Data Compression Conference (DCC), 2015. 論文へのリンク(arXiv) 提案法はLempel-Ziv(LZ)法に類似性がありその簡易版になっています。LZ法では各テキスト上の位置より前に出現する部分文字列の最長一致文字をテキスト

年が明けて2014年の１月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には２つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム

暑い日々が続きますが、いかがお過ごしでしょうか？ 早いもので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 Conferenc

以前のブログで紹介した簡潔マルチビット木の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

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/ 文法圧縮のアルゴリズムは@marugo

人工知能学会誌の私のブックマークに簡潔データ構造という題で記事を書きました。私のブックマークは研究者が自らの研究をする中で普段使っているWeb上のリソースを公開するための記事です。今までいろいろな研究者が記事を書かれています。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/ 幸いにも今回は、私が執筆の機会を頂くことができたので情報検索などでよく使われている簡潔データ構造のリソースについてまとめてみました。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/26-6.html 記事を書いてみて思ったことは、ライブラリの充実により実際の場面で使いやすくなっていることと、多くのエンジニアや研究者がブログなどをつうじて記事を公開してくださっているおかげでこの分野が日本語で勉強しやすくなってい

MinHashを用いたSketchSortの論文がMolecular Informaticsに採択されました。 論文は下のサイトからダウンロードすることができます。 Yasuo Tabei and Koji Tsuda: SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular Fingerprints, Molecular Informatics, 2011. Link ソフトウェアをgoogle codeにて公開しています。 本論文では、以前紹介したCosine距離に基づく高速な全点間類似度検索法(SketchSort)をJaccard-Tanimoto距離に基づく手法に拡張しました。このため、以前は与えられた任意の２点間のCosine距離をハミング距離で保存したままバイナリ文字列へとハッ

５月２４日から２７日に中国深センで開催されたPAKDD2011で、以前のブログで紹介した線形グラフのマイニングアルゴリズム(LGM: Linear Graph Miner)について発表しました。 下はexcursionの写真. 発表スライドをアップしました。 Lgm pakdd2011 public View more presentations from Yasuo Tabei

データマイニングの国際会議 PAKDD2011に線形グラフのマイニングアルゴリズムに関する論文がアクセプトされました。本研究は、PFIの岡野原さん(@hillbig)、産総研の廣瀬さん、津田さん(@kojitsuda)との共同研究です。 論文をarxiv.orgにアップしました。 LGM: Mining Frequent Subgraphs from Linear Graphs, Yasuo Tabei, Daisuke Okanohara, Shuichi Hirose, Koji Tsuda, The 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD2011), link to the paper 線形グラフ(Linear Graph)とは、通常のグラフの頂点に順序がついたグラフです(下

SketchSort(スケッチソート)法の論文が ACML2010にアクセプトされました。今年も採択率30%の難関でした。 http://sugiyama-www.cs.titech.ac.jp/ACML2010/ Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML2010), Tokyo, Japan, 2010. Link to the paper SketchSort法は、データー点の集合が与えられたら、集合中の２点間の距離がある閾値以内のペアー(近傍ペアー)を全て求める問題(全点間類似度検索)を高速

FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の３つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、４文字種のDNAや２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離

もぐりででている授業で紹介されていたカーネル法の本(OSじゃなくて)が出版されていたので読んでみました。カーネル法の本はいろいろ出版されていますが、この本独自の章は8章「平均による確率分布の特徴づけ」と9章「正定値カーネルによる依存性・独立性」です。最近提案されたカーネル法を用いたデーターの分布の等しさや独立性のテストを学ぶことができます。 カーネル法入門―正定値カーネルによるデータ解析 (シリーズ 多変量データの統計科学) 作者: 福水健次出版社/メーカー: 朝倉書店発売日: 2010/11/01メディア: 単行本 クリック: 19回この商品を含むブログ (11件) を見る

東京工業大学の杉山研究室でSketchSort法に関する講演をさせていただきました。杉山研はいろいろな国からの留学生が多くゼミでの公用語は英語だそうです。企業と同様に大学の研究室単位でもグローバル化しているようです。ツッコミも激しかった。杉山研での発表のためにスライドを少し修正したので再アップしました。またまた英語で発表したので英語のスライドになっております。 Sketch sort sugiyamalab-20101026 - publicView more presentations from tbyasu. 今後の予定 11月4日〜6日に行われるibis2010にて以下のタイトルでポスター発表します。 「大規模化合物のスケッチ表現によるクラスタリング」 http://ibis-workshop.org/2010/index.html SketchSort法を2千５百万からなる化合物デ

SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。　アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ

カナダのバンクーバーで開催された機械学習の最高レベルの国際会議NIPSに参加しました。 https://nips.cc/ 面白かった発表等は、後日まとめます。 12/6 バンクーバーに到着する。会議は次の日からなので、街をぶらぶら歩く。クリスマスパレードの日だったので、パレードを見る。 下はマショマロ入りコーヒー。カナダでは、コーヒーにマショマロを入れるらしい。