転置インデックスの索引の効率的な保存 - Negative/Positive Thinking
はじめに 索引データの保存に関する記事を読んだのでメモ。 索引データの効率的な保存 ドキュメント数やできた索引数が多くなるにつれ、効率的に索引データを保存することが重要になってくる 工夫して索引データを保存することで、いろんなメリットがある メモリの節約 ディスクのIO処理が減って読み込みスピードアップ 各手法 例えば転置インデクスでの索引では「索引単語：ページ番号1、ページ番号2、、、」という感じになっているので、右側のページ番号(整数列)を効率よく格納することを考える。 整数列をそのまま保存するのではなく、ソートしてその差分を保持するようにして符号化することで、効率よく格納することを考える。 VarByte バイト単位の操作のみで符号化できる 整数を1〜5byteで符号化(最上位1bit+下位7bit) 整数の1byte分読み込む 下位7bitに整数を入れる。もし、もとの整数が入りきら
29ビット以上のint値にも対応できるようにSimple9を調整 - kaisehのブログ
Simple-9について解説 - tsubosakaの日記 http://ameblo.jp/th0083/entry-10483740192.html Simple9は、整数列を高速に圧縮するアルゴリズムです。32bitのint値を上位4bitと下位28bitに分けて、下位28bitにデータをできるだけ多く詰め込み、上位4bitで詰め込みのパターンを表現します。パターンは全部で9種類あります。 上位4bit パターン 0000 1bit x 28 0001 2bit x 14 0010 3bit x 9 0011 4bit x 7 0100 5bit x 5 0101 7bit x 4 0110 9bit x 3 0111 14bit x 2 1000 28bit x 1 ただしこのレイアウトでは、圧縮対象の整数列の中に29bit以上の数値が入っている場合に対応できません。そこで、詰め込
Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
Vertical Codeはunary符号の6倍すごい - EchizenBlog-Zwei
Vertical Codeを実装してみたらunary符号のときよりデータサイズが1/6になった。とても感動したので、この気持ちを伝えるため記事を書いてみるよ。 Vertical Codeを使うことになった経緯は↓を参照 Vertical Codeを調べたよ - EchizenBlog-Zwei Vertical Codeはその名の通り、データをVerticalに持っておく符号形式。デルタ符号くらいのデータサイズで収まる。だったらデルタ符号でいいじゃんと思うのだが、Vertical Codeにはselect()、rank()という操作が簡単に実装できるメリットがある。 select(pos)とはpos番目のデータ値の累計値を求める操作。rank(value)とは累計値がvalue以上になるはじめてのposを求める操作。互いに逆関数の関係にある。(unary符号を用いたときとrank()、se
Vertical Codeを調べたよ - EchizenBlog-Zwei
故あってCompressed Suffix Array(CSA)を実装していたのだがΨ Vectorのデータ構造にunary符号を採用したら圧縮前よりもサイズが大きくなるという惨事が発生。 これに対処するため急遽データ構造をVertical Codeに変更した。デルタ符号(δ符号)並の圧縮率で、しかも高速らしい。 例えば index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 value: 0 1 0 1 0 1 0 1 0 1 2 3 0 1 2 3というデータを考える。 Vertical Codeはデータを固定サイズM毎にブロックとして扱う。ここではM=8とする。また値はビット列に置き換え縦に並べる。すると最初のブロックは index: 0 1 2 3 4 5 6 7 value: 0 1 0 1 0 1 0 1 bit : 0 1 0 1 0 1 0
5分でわかる(かもしれない)圧縮の基本 - EchizenBlog-Zwei
大規模データを日常的に扱う人にとって、データ圧縮は基本。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。 でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を背けがち。そこで5分でわかるような感じで説明を書いておく。 基本的な圧縮の方法は差分圧縮というのがある。今回はこれを説明する。 char型のデータが8つ並んでいると考える。 6 3 2 1 7 5 4 8とりあえずバイナリにしてみる。便宜上、縦に書く。 6 3 2 1 7 5 4 8 =============== 1の位:0 1 0 1 1 1 0 0 2の位:1 1 1 0 1 0 0 0 4の位:1 0 0 0 1 1 1 0 8の位:0 0 0 0 0 0 0 1 16の位:0 0 0 0 0 0 0 0 32の位:0 0 0 0 0 0 0 0
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
データ量を操る圧縮／展開を究めよう
というふうに変換します。 文字数で比較してみると、圧縮前は14文字でしたが圧縮後は6文字と半分以下になっています。圧縮後のデータから元のデータに戻すことも容易にできます。 ランレングス法の実装 それでは早速、ランレングス法を実装してみましょう。サンプルデータは某巨大掲示板から引用しました。 <html> <head> <script type="text/javascript"> function getStringById(id) { var element = document.getElementById(id); return element.innerHTML; } </script> </head> <body> <div id="area1"> <pre> ＿＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿ （＿＿＿＿＿ ＼ ⊂⊃ ／ ＿＿＿
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
転置インデックスの圧縮 - tsubosakaの日記
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
