What is the difference between Θ(n) and O(n)?
Short explanation: If an algorithm is of Θ(g(n)), it means that the running time of the algorithm as n (input size) gets larger is proportional to g(n). If an algorithm is of O(g(n)), it means that the running time of the algorithm as n gets larger is at most proportional to g(n). Normally, even when people talk about O(g(n)) they actually mean Θ(g(n)) but technically, there is a difference. More
C++ containers that save memory and time
The latest news from Google on open source releases, major projects, events, and student outreach programs. We’re pleased to announce C++ B-Tree, a C++ template library that implements B-tree containers with an analogous interface to the standard STL map, set, multimap, and multiset containers. B-trees are well-known data structures for organizing secondary storage, because they are optimized for
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
Pairing heap - Wikipedia
A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986.[1] Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algor
gwtのwavelet木の実装をwavelet行列に変更しました - Yasuo Tabeiの日記
大規模グラフ類似度検索のためのソフトウェアーgwtの内部で使われているwavelet木の実装をwavelet行列に変更しました。 下のサイトからgwt-wm-3.0.0.tar.bz2をダウンロードできます。 http://code.google.com/p/gwt/ gwtに関する説明は以前のブログ記事を参照してください。 gwtについての解説記事 wavelet行列に関する説明は論文とechizen_tmさんの記事を参照して下さい。 http://d.hatena.ne.jp/echizen_tm/20120801 Francisco Claude and Gonzalo Navarro.The Wavelet Matrix.Proc. SPIRE'12, pages 167-179. LNCS 7608
Graph-indexing wavelet tree (gWT)のグラフ検索が超速い
高速文字列解析の流れで、タイミングよく統数研チャンネルの資料が公開されていて、最後のほうのスライド(65枚目)にグラフの類似度検索の実装としてgwtが紹介されていたので遊んでみた。 データベースは、ChEMBLから取ってきた。なぜpubchemじゃないかというと面倒なので略。 入力のフォーマットがgSpanとかGASTONと一緒だったので、昔書いたのを流用しようとしたんだが、昔書いたpythonスクリプトはどうもOBMolAtomIterあたりがバグっていて動かないようだ(OBMolBondIterも動かなかった。) File "sdf2gsp", line 17, in convert for i,atom in enumerate(ob.OBMolAtomIter(mol)): File "/usr/local/Cellar/python/2.7.3/lib/python2.7/sit
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
"高速文字列解析の世界"を読んだ - 射撃しつつ前転 改
高速文字列解析の世界というタイトルからは、どんな中身なのかあまり伝わってこないので、どんなことが書いてある本なのか、中身をちょっと紹介してみる。 1章、2章は概観や準備であり、3章からが本番なのだが、Burrows Wheeler Transform、簡潔データ構造、ウェーブレットツリー、データ圧縮、全文検索、テキストマイニングのためのデータ構造、という章題になっている。 何に使うのかという目的ベースで考えると、この本に載っているのは、データ圧縮、情報検索とテキストマイニングの基盤技術である（データ圧縮については基盤と言うよりはそのものだが）。ただ、この本には本当に基盤技術の話しか載っていないので、「この本で情報検索はバッチリだぜ！！」というような訳にはいかない。テキストマイニングに関しても同様である。別途入門書を読むなりしないと、より高次元（ここでの高低は技術の積み重ねの高低であり、難し
高速文字列解析の世界が素晴らしかった
丸4日かけて8章（最終章）以外を読んだ。正月休みの後半の時間をこの本を読むのに費やしたのは正解だった。新年開始早々、知的な満足感が得られた。 本書を読めば、BWT、簡潔データ構造、ウェーブレット木、FM-Indexが理解できる。 LF-mappingのところ(p.28の補題3.4)を理解するのに時間がかかったが、これを理解できればFM-Indexのアルゴリズムが理解できる。ついでにWavelet Matrixも理解できた。ひとつひとつ丁寧に読み進めていけば理解できるようになっていたので良かった。 本や論文で書いてあるなら、まず読んで知っているのが必要条件(slide 24)と著者のスライドに書いてあるように、BWT、簡潔データ構造、ウェーブレット木、FM-Indexは知らないといけない知識になるんだろうなぁと。 pubmed調べたら、bioinformatics用途でしかみつからないのでc
Posts by Topic
Update: Jeremy Kubica's third book of humorous explanations of computer science, The CS Detective, is now available! Details on all books here. Computational Fairy Tales includes over 70 stories that cover a range of different computer science concepts from introductory programming, to high level CS concepts, to data structures and algorithms, to computational complexity, to practical programming
SPIRE2012の効率的な文法圧縮のための可変長コードに関する論文とオンライン文法圧縮のソフトウェアー (olca++)を公開しました。 - Yasuo Tabeiの日記
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
Tony Finch
Data Structures Tries - Information Technology- E-University - Wisdom Jobs
Google Search
Priority Queues in CL
BOOT_COMPLETEDが受信出来ない - Google グループ
jsrun.it - このウェブサイトは販売用です！ - jsrun リソースおよび情報
Adam Kirsch's Publications