bit-struct
Class for packed binary data stored in ruby Strings. BitStruct accessors, generated from user declared fields, use pack/unpack to treat substrings as fields with a specified portable format. Field types include: signed and unsigned integer (1..16 bits, or 24, 32, 40, 48... bits) numeric fields (signed, unsigned, float) can be designated as any of the following endians: little, big, native, network
高速かつ省メモリなbit vector「sucBV」を作る
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するデータ構造は「操作付きbit vector（SUCcinct Bit Vector:sucBV）」です。sucBVは、圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。STLのvector<bool>と同様に、bit列情報B[0....n-1]を保存します。このbit列情報は前もって与えられ、変更が無いことを前提とします。sucBVは、次の二つの操作を定数時間でサポートします。 rank(p,bit)――B[0...p]中のbit（bitは1
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
sary: Suffix Arrayのライブラリとツール
saryとは? sary は Suffix Array のライブラリとツールです。Suffix Array と呼ばれるデータ構造を用いることにより、 10MB, 100MB といっ た巨大なテキストファイルに対する高速な全文検索を実現します。 特定の個所だけにインデックスポイントを割り当てることにより、 特定のフィールドのみを検索対象にすることもできます。 目次 新着情報 特徴 Suffix Arrayの簡単な説明 libsaryのリファレンスマニュアル 付属ツールの使い方 FAQ ダウンロード TODO 関連リンク集 メーリングリスト 新着情報 2005-03-30: sary 1.2.0 公開 ABIが変更されました 細かなバグ修正がされました 2002-09-18: sary 1.0.4 公開 検索結果の表示を高速化しました ヘルプメッセージを修正しました 2001-04-20: さ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
