问题标签 [flajolet-martin]

我试图理解这个草图，但无法理解。如果我错了，请纠正我，但基本上，假设我有一个文本数据..单词..我有一个散列函数..它需要一个单词并创建一个整数散列，然后我将该散列转换为二进制位向量？对.. 然后我跟踪我从左边看到的第一个 1.. 那个 1 的位置（比如说，k）......这个集合的基数是 2^k？

http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html

但是……说我只有一个字。并且它的散列函数使得它生成的散列是2 ^ 5，那么我猜有5个（？？）尾随0？所以它会预测 2^5 (??) 基数？这听起来不对？我错过了什么

以下是我为实现而编写的代码 Flajolet and Martin’s Algorithm。我曾经Jenkins hash function生成过32 bit hash value数据。该程序似乎遵循算法，但偏离了大约 20%。我的数据集包含超过 200,000 条唯一记录，而程序输出大约 160,000 条唯一记录。请帮助我理解我所犯的错误。哈希函数是按照Bob Jerkins 的网站实现的。

我试图理解为什么 Flajolet-Martin 算法 (FM) 工作时间过长。这里对算法的描述（第 4.4.2 节）很有希望，但并不完美。

为什么任何元素的最大尾部长度（尾随零的数量）可以作为流中不同元素数量的估计值？想象一下只有两个不同的元素 {1,2}，它们分别散列到 {10001, 10000}。这意味着不同元素的数量是 2^4，这显然是不正确的。

有什么诀窍？

我正在尝试实现 Flajolet Martin 算法。我有一个包含超过 6000 条记录的数据集，但以下代码的输出是 4096。请帮助我理解我所犯的错误。

我尝试了 HyperLogLog 算法的这种实现，以下代码的输出为 2560。

def return_trailing_zeroes(s): s = str(s) rev = s[::-1] count = 0 for i in rev: if i is '0': count = count + 1 else: break
return count

h1_m=0

h2_m=0

h3_m=0

h4_m=0

fp=open("/content/drive/MyDrive/Data.txt","r")

对于 fp 中的行：

hash_value_1 = abs(xxhash.xxh32(line).intdigest())

hash_value_2 = abs(hash32(line))

hash_value_3 = abs(jhashcode.hashcode(line))

hash_value_4 = abs(mmh3.hash(line))

binary_1 = 格式（哈希值_1，'032b'）

binary_2 = 格式（哈希值_2，'032b'）

binary_3 = 格式（哈希值_3，'032b'）

binary_4 = 格式（哈希值_4，'032b'）

t1 = return_trailing_zeroes(binary_1)

t2 = return_trailing_zeroes(binary_2)

t3 = return_trailing_zeroes(binary_3)

t4 = return_trailing_zeroes(binary_4)

如果 t1>h1_m：h1_m=t1

如果 t2>h2_m：h2_m=t2

如果 t3>h3_m：h3_m=t3

如果 t4>h4_m：h4_m=t4

fp.close()

avg_hash12 = (2**(h1_m) + 2**(h2_m))/float(2)

avg_hash34 = (2**(h3_m) + 2**(h4_m))/float(2)

distinct_elements = math.ceil(statistics.median([avg_hash12, avg_hash34]))

打印（不同的元素）