定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmapresearchmapは、日本の研究者情報を収集・公開するとともに、研究者等による情報発信の場や研究者等の間の情報交換の場を提供することを目的として、国立研究開発法人科学技術振興機構（JST）が運営するサービスです。
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ページを開く
