SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 | GREE Engineering
こんにちは。アプリケーション基盤チームのよやと申します。 バイナリの目利きや書き換えを主な業務フィールドとし、1% でも多くのユーザの皆様にサービスをお届けする為、より良質のバイナリを探し求める毎日です。 SWF の番外編として zlib 伸張について２回のブログに分けて解説します。(圧縮処理は対象外です) 前編の今回は概要についてお話し、具体的な実装は後編で扱う予定です。 はじめに SWF フォーマットは zlib 圧縮を多用します。例えば、GIF/PNG 画像は独自画像形式(DefineBitsLossless の BitmapPixelData)に変換後 zlib 圧縮して格納します。 http://labs.gree.jp/blog/2010/12/1902/ SWFバイナリ編集のススメ第五回 (PNG) SWF バイナリの中の zlib 圧縮されたデータが怪しい場合に、zlib
カスタムハフマン符号 - 七誌の開発日記
ZIP勉強会（id:n7shi:20110529）を開催しましたが、時間の都合もありカスタム（動的）ハフマン符号については「RFC 1951を読んでください」で説明を省略しました。IO_Zlib開発者のid:yoyaさんからコメントを頂いたので、某「例示は理解の試金石」を実践してみました。 よやさんのまとめ id:yoya:20110726:io_zlib .NETのDeflateStreamはどんな短いものでもカスタムハフマンで圧縮します。それを利用して "aaaaa" というASCII文字列をカスタムハフマン圧縮してみます。 open System.IO open System.IO.Compression open System.Text let fs = new FileStream("test.bin", FileMode.Create) let ds = new Deflate
ソート済の整数列を圧縮する件
圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号
How gzip uses Huffman coding
I wrote a blog post quite a while ago called gzip + poetry = awesome where I talked about how the gzip compression program uses the LZ77 algorithm to identify repetitions in a piece of text. In case you don’t know what LZ77 is (I sure didn’t), here’s the video from that post that gives you an example of gzip identifying repetitions in a poem! I thought this was a great demonstration, but it’s only
HTTP2のヘッダ圧縮 Huffman Encode の原理とメリット・デメリット - Qiita
この記事は HTTP2 Advent Calendar 2014 の 16 日目の投稿です。 HTTP2 では、通信の遅延を小さくするために、ヘッダのサイズを小さくする機構を備えています。 その仕様は HPACK と呼ばれ、下記の組み合わせで構成されます。 Literal ASCII Encoding 非圧縮のエンコーディングと言える。 Huffman 今回の主人公。 出現頻度が高い文字ほど、小さいデータサイズで表現。 Index 「Static Table に事前定義されている値」または「既にインデックス化した値」を番号で指定する。 圧縮に大きく寄与する。 今回は、Huffman Encoding の原理とメリット／デメリットを解説します。 gzip じゃダメなんですか？ HTTP/1.1 では、Body を gzip エンコードすることでサイズを圧縮することが出来ます。ヘッダも同じよう
データ圧縮の基礎『ハフマン符号化』の仕組みを見てみよう | パソコン実践BLOG -道すがら講堂-
何度かこのブログでデータ圧縮（書庫やエンコードなど）について解説してきましました。 しかし、その詳しい仕組についてはまだ書いていません。実際、実践的なところは難しすぎるので私もよく分かっておらず、専門的なことまではわかりません。（プログラミングは今後しっかり勉強していきたいですね。） ですが、漠然と「取り敢えずデータが少なくなるんだよ！」と言われても釈然としないでしょう。少なくとも、私は「元の情報を残したままデータを小さくするってどうやるんだろう？」と疑問を持ちました。 なので、この記事ではデータ圧縮の基礎部分でよく使われる「ハフマン符号化」について書いてみたいと思います。 情報数学のお話になりますが、概要だけならとても理解しやすいものなので、今回はこれをテーマにしてみます。データの圧縮とはどうゆうことなのか、その一端でも知りたい方はお付き合いください。 ついでに「なぜコンピューターは0と
Deflate
2. このスライドについて • Deflateの実装に必要な知識はRFC 1951に 網羅されている • しかし定義が並んでいるだけなので、いきな り読んでも意味がわからない • 実際のDeflateのデータとRFC 1951を見比 べながら試行錯誤して、ようやく把握 • RFC 1951を読む前の導入的なスライドを目 指して作成、網羅的解説ではない 3. Deflate • ZIP, gzip, PNGで使われている圧縮方式 – ZIPはコンテナ込み、gzipはコンテナなし（→tar） • RFC 1951で定義 • 圧縮率はtar.gz, tar.bz2, tar.xzを比較すれば 目安になる – そこそこの圧縮率とそこそこの処理速度 • バイトの可変長bit化とコピペで圧縮 – 可変長bit化をハフマン符号化と呼ぶ – コピペをLZSSを呼び、LZ77の亜種 4. テスト（Pytho
Twitter本文と言及URLの圧縮 - kaisehのブログ
最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつgzip等で圧縮してもほとんど意味がないか、オーバーヘッドが出て逆効果になってしまいます。 そこで、収集済みのサンプルデータを元にハフマン木を作っておき、それを共通利用してtweetを圧縮してみました。 用意したのは、英語ユーザ/日本語ユーザ/韓国語ユーザ各1000人のtweetサンプルをベースにしたハフマン符号と、tweet本文から抽出したURL文字列をベースにしたハフマン符号の4種類です。 頻度表は次のようになりました。 char (en) freq (en) char (ja) freq (ja) char (ko) f
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ひけらかし会：辞書式圧縮
Why isn’t it possible to read gzip files from the middle?
An efficient compression algorithm for short text strings