Quasi-Succinct Indices
Compressed inverted indices in use today are based on the idea of gap compression: documents pointers are stored in increasing order, and the gaps between successive document pointers are stored using suitable codes which represent smaller gaps using less bits. Additional data such as counts and positions is stored using similar techniques. A large body of research has been built in the last 30 ye
ウェーブレット木の世界
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
A x86-optimized rank&select dictionary for bit sequences
A x86-optimized rank&select dictionary for bit sequences1 of 28
LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(4) -unary記法- < | > Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Bector- > ================================================ ものすごい勢いで更新をサボっていたCSAの解説を再開。今回はSuccinct Bit Vectorというデータ構造について。 Succinct Bit Vector(簡素なビットベクトル)とは、ビット列に対してrank()、select()という操作を追加したもの。CSAではΨ VectorやB Vectorなどのビットベクトルに対してrank()、select()をガンガン使うので、しっかり抑えておきたい。 rank(pos, bit)はビットベクトルのposの位置までにbitの出てきた回数を
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
How to choose a Haskell array library
Choosing an array type in Haskell is a difficult task. For one-dimensional random access data structure the vector library seems to be the optimal choice most of the time. Things are more complicated if you happen to need two- or multi-dimensional arrays (matrices), access their blocks and slices as first-class structures (like in Python), enjoy destructive updates, use some linear algebra, intero
Advanced Data Structures
6.851: Advanced Data Structures (Spring'07) Prof. Erik Demaine TA: Oren Weimann [Home] [Lectures] [Assignments] [Project] [Accessibility] Lectures are MW 1–2:30 in 56-114. Scribing Use this template when scribing. Submissions must be via email to oweimann#at#mit.edu and include a compiled PDF attachment, the LaTeX source, and whatever figures you use. Please give real bibliographical citations for
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Succinct Data Structure for Analyzing Document Collection