Kazuho@Cybozu Labs: Compressing URLs in your Webapp, for size and speed
Last year I had a chance to talk about the internals of our service: Pathtraq at Percona Performance Conference (slides), in which I described the methods we use to compress the URLs in our database to below 40% of the original size, however had not released the source code since then. I am sorry for the delay, but have finally uploaded the code to github.com/kazuho/url_compress. It is generally
Kazuho@Cybozu Labs: Range Coder の終了処理
« Tritonn (MySQL+Senna) の join を高速化 | メイン | Range Coder の展開速度を SSE で高速化 (してもらった) » 2008年02月22日 Range Coder の終了処理 CodeZine：高速な算術圧縮を実現する「Range Coder」（算術圧縮, データ圧縮, Range Coder）等を見ていると、多くの Range Coder の実装では、終了処理において冗長な出力をしているようです。 私の理解と記憶が正しければ、予測の上限値と下限値が異なる最初のビットまで出力すれば、残りのビットの出力は不要なはずです。Range Coder が一般化する以前の、ビット単位の操作を行っていた Jones 符号化器はそのような実装がされていたように思うのですが、Range Coder で速度を稼ぎ始めた時に、この点が見過ごされるようになったので
Kazuho@Cybozu Labs: Range Coder の展開速度を SSE で高速化 (してもらった)
ご覧のように、データを出現頻度の降順で並び替えた上で SSE によるシーケンシャルサーチを使うことで、二分検索を使った場合と比べて 56% パフォーマンスが向上しています。また、この手法はデータのアクセスパターンも改善する (二分検索によるランダムアクセス→シーケンシャルアクセス) ので、前段で多数のテーブルの切り替えを行っている場合等にも有効です (キャッシュミスの影響が小さくなるため)。 この最適化を施した Range Coder は CodeRepos においてあります。興味のある方はご覧ください (/lang/cplusplus/range_coder/ - CodeRepos::Share - Trac) 。上のベンチマークは、 $ ./build_table.pl --ordered < ../calgary_corpus/paper1 > table.c && g++ -DR
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮 - naoyaのはてなダイアリー
先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。 BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。 今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。 http://github.com/naoya/perl-algorithm-mtf/tree/master に置いています。 use Algorithm::MTF; my $encoder = Algorithm::MTF
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
