転置インデックスの圧縮 - 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
静かな注目を集める圧縮アルゴリズム「LZMA」
GNUプロジェクトの配布アーカイブなどを中心に、LZMAを用いた圧縮形式を目にする機会が増えてきた。組み込み用途などへの活用も期待されるこの圧縮形式を紹介しよう。 2001年に開発された可逆圧縮アルゴリズム「LZMA」（Lempel-Ziv-Markov chain-Algorithm）が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。 ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip（.gz）やbzip2（.bz2）が併用されることが多い。 .gzや.bz2をしのぐ圧縮率が特
Lempel-Ziv-Markov chain-Algorithm - Wikipedia
Lempel-Ziv-Markov chain-Algorithm（略してLZMA）は、2001年から開発されているデータ圧縮アルゴリズムで、7-Zipアーカイバの7zフォーマットやXZ Utilsのxzフォーマットで使用されている。LZMAは、LZ77に少々類似した辞書式圧縮法（英語版）を使用し、通常bzip2以上の高い圧縮率と伸張速度、および最大4GBのサイズ可変な圧縮辞書を特徴とする。 LZMA2は、圧縮されていないデータとLZMAデータの両方を含むことができ、複数の異なるLZMAエンコーディングパラメータを含むことができる単純なコンテナ形式である。 LZMA2は、任意にスケーラブルなマルチスレッドの圧縮と展開と、部分的に非圧縮データの効率的な圧縮をサポートする。 LZMAは、改良LZ77圧縮アルゴリズムと、バックエンドにレンジコーダー（Range Coder）を使用している。 辞書
多Byte文字コードの圧縮(2)：エントロピーの比較 - シリコンの谷のゾンビ
前回の多バイト文字コードの圧縮に続いて実験．こんなことをしている場合ではない日に限り，余計なことで手が動く． # 以下，誤っている部分があるかもしれません．むしろ正しい部分の方が少ないかも．おや？と思う点があればご指摘お願いします． 実際に圧縮アルゴリズムを考える以前に，エントロピー（平均記述長）が短くなるようにすればいいのか，と思いつく．エントロピーは平均記述長とも呼ばれるように，ひとつの事象に割り当てる平均ビット長（ビット長の期待値）を表しており，圧縮の理論的限界を意味している． ちなみにハフマン符号はエントロピー符号ではあるものの，各符号長が整数になるようにしているので，理論的限界まで圧縮することはできない．これを解決したパーフェクト超人が算術符号，僕が解説するよりWikipediaを見る方が早いと思うので割愛:) 細かい話をすると，k次エントロピーというものもあり，これはk個前まで
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
