FlajoletMartin

FlajoletMartin 算法

原始算法：

"Mining Massive dataset"中介绍的改进过程：

3-4. 构造m组hash函数，每组n个函数。对每个字符计算hash值，h11,...,h1n, h21,...,h2n,..., hm1,...,hmn

4. for each hij, get its 0-tailing length:

<!--WizRtf2Html Charset=0 -->private int rho(long v) {

        int rho = 0;

        for (int i = 0; i < m_bitmapSize; i++) { // size of long=64 bits.

            if ((v & 0x01) == 0) {

                v = v >> 1;

                rho++;

            } else {

                break;

            }

        }

        return rho == m_bitmapSize ? 0 : rho;

    }

rho(hij) -> k (in {1,...,64})

Keep a bitset Xij, set Xijk<- 1.

After the stream finishes, calculate X(hij)= k; Xijk is the first 0 in {Xij1, ..., Xij64};

for each group i, calculate the avage value of {X(hii), ... }.

5. calculate the median result among the groups, that is R

 

java代码参见：

https://github.com/rbhide0/Columbus/blob/master/src/main/java/rbhide0/streaming/algorithm/FlajoletMartin.java