Cadinality Estimationアルゴリズム学習(一)

最近は菜鳥教程でredisを独学しています.Redis HyperLogLogを見たとき、「基数」と他の接触したことのないもの(または忘れたもの)に好奇心を持ちました.
そこで「HyperLog Log」を検索して、Cadinality Estimationアルゴリズムとそれを学ぶ時に参考にする文章を引き出しました.
　　http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-i.html
文章から見れば、基数とは、集合(ここの集合は重複要素の存在を許可し、集合論の厳密な定義とは少し違っています.特別な説明をしないと、ここで述べた集合は重複要素の存在を許可します.)の異なる要素の個数を指します.
これは「1つの配列の中で重複しない要素の個数を求める」というアルゴリズムと似ています.配列a[10]={1,2,3,4,1,2,3,4,5,6,7}のように、重複しない要素は{1,2,3,4,5,6,7}全部で7つです.その応用シーンについては、例えば、ウェブサイトで「一人」の訪問回数を統計する場合、例えば明ちゃんには「明ちゃん」にマークを付けて、今度訪問する時、総訪問回数はプラスできません.「明ちゃん」ではない人に限って、例えば「麗ちゃん」が訪問して、総訪問回数を増やす.
これは前にやったような計算方法の問題です.統計文字列「abcdaabceedia」の中で重複しない文字の個数です.もちろん、最も簡単な太い爆発の方法は、前のn-1文字を遍歴して比較することです.これは時間の無駄です.文字列はアルファベットだけで、長さ26のハッシュ表を作って、一度文字列を巡回して、読んだ文字をハッシュ表に記入して、最後にハッシュ表を巡回すればいいです.
hash.

 1 #include 
 2 #include <string.h>
 3 
 4 int main()
 5 {
 6     char str[] = "abcdaaabceeda";
 7     int hash[26] = {0};
 8     int size = strlen(str);    
 9     int i;
10     for(i = 0; i < size; ++i)
11     {
12         int temp = str[i] - 'a';
13         ++hash[temp];
14     }
15     int num = 0;
16     for(i = 0; i < 26; ++i)
17     {
18         num += hash[i] > 0 ? 1 : 0;
19     }
20     printf("num = %d
", num);
21 }

26文字の小文字を統計するだけであれば、26個のint型のスペースが必要です.bitmapが空間を節約できると思い、それを使って書きました.
bitmap.c

 1 #include 
 2 #include <string.h>
 3 
 4 int hamming_weight(unsigned int bitmap)
 5 {
 6     unsigned int temp = bitmap;
 7     temp = (temp & 0x55555555) + ((temp &  0xaaaaaaaa) >> 1);
 8     temp = (temp & 0x33333333) + ((temp &  0xcccccccc) >> 2);
 9     temp = (temp & 0x0f0f0f0f) + ((temp &  0xf0f0f0f0) >> 4);
10     temp = (temp & 0x00ff00ff) + ((temp &  0xff00ff00) >> 8);
11     temp = (temp & 0x0000ffff) + ((temp &  0xffff0000) >> 16);
12     return temp;
13 }
14 
15 int main()
16 {
17     char str[] = "abcdaaabceeda";
18     unsigned int bitmap = 0;
19     int size = strlen(str);    
20     int i;
21     for(i = 0; i < size; ++i)
22     {
23         int loc = str[i] - 'a';
24         int temp = 1 << loc;
25         bitmap |= temp;
26     }
27     printf("num = %d
", hamming_weight(bitmap));        
28 }

違いはhashでも単一文字の出現回数を統計することができます.bitmapはhamming weightを使って合計回数を統計することができます.
ウェブサイトの統計では、「小明」などのアクセス数の問題は、「小明」をハッシュ関数に導入し、該当するアドレスを見つけて、「訪問済み」と表記することに相当する.統計するときは、ハッシュテーブルのデータ構造に従って巡回したり、bitmapの中の1の個数を計算するなどの方法で統計します.以上は私の個人的な見解で、確率などの実現問題に関わりません.