1

以下は、私が実装するために書いたコードです Flajolet and Martin’s Algorithm。私はデータのJenkins hash function生成に使用しました。32 bit hash valueプログラムはアルゴリズムに従っているように見えますが、約 20% ずれています。私のデータ セットは 200,000 を超える一意のレコードで構成されていますが、プログラムは約 160,000 の一意のレコードを出力します。私が犯した間違いを理解するのを手伝ってください。ハッシュ関数は、Bob Jerkins の Web サイトに従って実装されています。

import numpy as np
from jenkinshash import jhash

class PCSA():
    def __init__(self, nmap, maxlength):
        self.nmap = nmap
        self.maxlength = maxlength
        self.bitmap = np.zeros((nmap, maxlength), dtype=np.int)

    def count(self, data):
        hashedValue = jhash(data)
        indexAlpha = hashedValue % self.nmap
        ix = hashedValue / self.nmap
        ix = bin(ix)[2:][::-1]       
        indexBeta = ix.find("1")    #find index of lsb
        if self.bitmap[indexAlpha, indexBeta] == 0:
            self.bitmap[indexAlpha, indexBeta] = 1


    def getCardinality(self):
        sumIx = 0
        for row in range(self.nmap):
            sumIx += np.where(self.bitmap[row, :] == 0)[0][0]

        A = sumIx / self.nmap

        cardinality = self.nmap * (2 ** A)/ MAGIC_CONST

        return cardinality
4

1 に答える 1

1

これを Python2 で実行している場合、A を計算するための除算により、A が整数に変更される可能性があります。

この場合は、次のように変更してみてください。

A = sumIx / self.nmap

に

A = float(sumIx) / self.nmap
于 2015-01-22T19:18:40.310 に答える