CodeZine(コードジン)

特集ページ一覧

高速かつ省メモリなbit vector「sucBV」を作る

大規模データを効率的に扱う操作付きbit vectorライブラリの実装

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/01/18 12:00

ダウンロード バイナリファイル (58.6 KB)
ダウンロード ソースコード (4.6 KB)

本記事では大規模なデータを扱うためのデータ構造である操作付きBit Array (SUCcinct Bit Vector: sucBV)を紹介します。sucBVは、vectorと同様に2値配列情報を保存する他にrank, selectと呼ばれる二つの操作を定数時間でサポートします。作業領域量はvectorの約3倍です。sucBVを用いることで、圧縮索引やsuccinct data structureなどを実装できます。

目次
※印刷用ページ表示機能はメンバーのみが利用可能です(登録無料)。
  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2007/09/04 10:57 スペルミスチェック ns -> us。ysnさん指摘ありがとうございます。

著者プロフィール

All contents copyright © 2005-2020 Shoeisha Co., Ltd. All rights reserved. ver.1.5