DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
