グレイコード - WebCrawler2
先日某勉強会で出たグレイコードについて、一応概念的には知っていたのですが、実装とかをよく知らなかったため調査。 グレイコードについてはWikipediaに結構詳しく書いてあります。 グレイコード - Wikipedia このグレイコード、何がいいかというと、数字的な近さがそのままグレイコード表現でも近くなることです。 普通の２進数の場合だと、例えば、 7 => 0111 8 => 1000となって、数字上ではとなりの数字なのに、２進数では４ビットも違う表現になってしまいます。 しかし、グレイコードの場合は、 7 => 0100 8 => 1100のようになって、数字上のとなりの数字が、グレイコード表現でも１ビット違いで表現されます。 このグレイコードの構成方法ですが、いろいろとあるのですが、ひとつの簡単な方法としては「反射２進グレイコード」というものがあります。 これは前半部分のグレイコー
heap sortを使った上位ランキング取得プログラム - 遥かへのスピードランナー
Managing Gigabytes 4.6章で解説されているソートのプログラムを実装してみた。 検索エンジンなどでN個のデータの中から上位r個を取得したい場合、まずN個のデータからなるmax-heapを構成して、ルート（最大値）から順にr個をヒープから取り除くというアプローチが考えられる。しかしN>>rの場合、r個のデータからなるmin-heapを構成して、残りのN-r個のデータをheapのルート（最小値）と順次比較して、ルートよりも大きい場合はルートと入れ替えて、heapを再構成する、という手順を取った方がより計算量が少なくて済む、という話。 10万件のランダムな数値をスペース区切りで出力するプログラム #include <iostream> #include <stdlib.h> using namespace std; int main (int argc, char *argv[
DMC(Dynamic Markov Coding)のによるデータ圧縮プログラムを書いてみた - 遥かへのスピードランナー
最近Managing Gigabytes勉強会に参加しているのでせっかくなので、この本に載っているアルゴリズムを使ってプログラムを組んでみました。 今回実装したのは、「2.5 SYMBOLWISE MODELS」の後半で説明されている「Dynamic Markov Coding(DMC)」です。書籍の他に、元論文「G. Cormack and R. Horspool, "Data compression using dynamic Markov modelling,"」を参考にしました。 実装はC++で行い、ソースはgithubに置きました。（CentOS 5.2+gcc 4.1.2で動作確認済） http://github.com/thorikawa/MG/tree/master/dmc 以下、アルゴリズムの概要と実装上の工夫などをまとめてみます。 意見・指摘などは絶賛大歓迎です。 DM
γ符号、δ符号、ゴロム符号による圧縮効果 - 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 ビット
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
