DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
「高速文字列解析の世界」を読むのに参考にした資料
現時点では、ビッグデータではなく、サンプリングされたデータを扱っているのですが、「大規模」データであることには違いなく、それらを如何に高速に処理するかに頭を悩ませています。 この本は、その悩みを解決する助けになりました。 実際には、いくらかの前提知識が必要ですし、対象とする問題や開発環境も考慮しなければなりませんでした。 部分的な調整しかできていませんが、それでも、当初は致命的とも思われた実行速度を、何とか現実的な速度まで持てくることができました。 以下に、この本を読む際に参考にしたページ、各種実装関連のページなどへのリンクを（備忘録も兼ねて）記しておきます。 なお、「参考にした」ページですので、必ずしも本書にて解説されている項目とは限りません。 ※実装コードの項目に記載したライセンスは調査時のものですし、未確認・未記載のものもあります。利用に際しては、それぞれ確認が必要です。 ■全般
γ符号、δ符号、ゴロム符号による圧縮効果 - 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 ビット
Variable byte codes
Variable byte (VB) encoding uses an integral number of bytes to encode a gap. The last 7 bits of a byte are ``payload'' and encode part of the gap. The first bit of the byte is a continuation bit . It is set to 1 for the last byte of the encoded gap and to 0 otherwise. To decode a variable byte code, we read a sequence of bytes with continuation bit 0 terminated by a byte with continuation bit 1.
Perlで圧縮
5. ディスクリードと圧縮 HDD vs メモリ -> 10 -6 ~ 10 -9 の差 HDD 上のデータのシーク ･･･ ディスクの回転待ち、ヘッドの移動に ms ∴ ディスクシーク回数を最小化したい OS ( カーネル ) ブロック単位での読み出し 連続したデータは近い場所に保存 アプリケーション B+ 木など最適なデータ構造の選択 圧縮して保存 -> 消費ブロック数を減らす 6. 復号処理と負荷 圧縮して保存 -> CPU処理と I/O のオーバーラップでスループット向上 圧縮済みデータの読み出し ･･･ I/O 負荷 圧縮されたデータの展開 ･･･ CPU 負荷 データが小さい ･･･ キャッシュに載りやすい
MySQLの新しいInnoDB ページI/O圧縮機能について解析してみた: hasegaw blog
InnoDBにはデータの圧縮機能がありますが、パフォーマンスが低いことからあまり使われていません。ただ今年の Percona Live で Oracle MySQL, MariaDB, そして Percona Server が新しい InnoDB Compression を出してきました。これはFusion-ioの R&D チームがフラッシュストレージ向けの MySQL 高速化の一環で開発したパッチが元になっています。ちなみに私は Fusion-io の社員ですのでこの発表をワクテカして待っていたのですが、折角コードが一般にリリースされたので、ソースコードを眺めて動作を調べることにしました。 参考にしたのは MySQL Server Snapshots (labs.mysql.com) にある MySQL with InnoDB PageIO Compression のソースコード、および
テキスト圧縮はこれ一冊でOK！？な優良書籍「The Burrows-Wheeler Transform」を読んだ - EchizenBlog-Zwei
以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額な本だったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。 本書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年の本なので比較的新しい話題も扱っていて満足度が高い。 また本書の特色は圧縮ありきで始まり、そこから全文検索可能な
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
Googleの新しい圧縮アルゴリズムZopfliについて調べた。 - EchizenBlog-Zwei
Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。 Compress data more densely with Zopfli - Google Developers Blog deflateアルゴリズム zopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77を改良した圧縮法で圧縮し、その後ハフマン符号で符号化したもの。 deflateアルゴリズムの実装としてはzlibやgzipがある。zlibとgzipの違いはヘッダとフッタの持っている情報。 使ってみる googlecode(http://code.google.com/p/zopfli/)から取ってくる。 $$ git clone https://code.google.com/p/zopfli/ $$ cd zopfli $$ ma
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
