定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmapresearchmapは、日本の研究者情報を収集・公開するとともに、研究者等による情報発信の場や研究者等の間の情報交換の場を提供することを目的として、国立研究開発法人科学技術振興機構（JST）が運営するサービスです。
大規模データ処理のための簡潔データ構造 | CiNii Research
データ列に対して検索効率などを効率化するため，索引を付加することがある．演算を効率化するために，データに対して特定の情報を付加したものを，ここではデータ構造と呼ぶこととする．本稿ではこのようなデータ構造のうち，もとのデータの長さnに対してo(n)程度の付加情報のみを与える，簡潔データ構造と呼ばれる分野について解説する．特に，最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる．ビットベクトルBに対して，先頭からi番目までのビット中の1の数を与えるrank1(B i)と，i番目の1の位置を与える select1(B i)という演算は，基本的かつ重要な演算である．これらの演算が定数時間で可能な簡潔データ構造について，具体的なデータ構造とアルゴリズムを紹介し，次に付加するデータサイズの下界についての結果を示し，最後に今後の展望について述べる．
Engineering the LOUDS Succinct Tree Representation - 射撃しつつ前転 改
Engineering the LOUDS Succinct Tree Representation(O. Delpratt et al., 2006)を読んだ。モチベーションとしてはTxの実装ってどういう風になってるのかが知りたかったというのがある。 LOUDSというのは順序木を効率的に実装するためのアルゴリズムで、この論文ではさらにそれを改良したLOUDS++というのを実装・提案している。 基本的なアイデアは、木の上の方から、ノードに存在する子ノードの数だけ1を並べる。デリミタは0。（まぁ、1と0が逆でもいいんだけど。）そうすると、それぞれの1とノードの対応が取れるようになる。このビット列をLBSと呼ぶ。LBSに対してis_leaf, parent, next_siblingなどの関数が実装できれば順序木が実現できる訳だけど、これらの関数はそれぞれ数個のrank, select操作で実
Sux: Implementing Succinct Data Structures
Sux in an umbrella nickname for the results of my fiddling with the implementation of basic succinct data strucures. The resulting code is rather sparse. The main highlights are: a novel, broadword-based implementation of rank/select queries for up to 264 bits that is highly competitive with known 32-bit implementations on 64-bit architectures (additional space required is 25% for ranking and 12.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
