Flajolet-Martin算法与HyperLogLog实现输出不符合预期的问题排查

基础实现背景 #

• 待估算数据集：共6000余条记录
• 基础Flajolet Martin实现输出结果：4096，与真实基数存在明显偏差
• 自行编写的HyperLogLog实现输出结果：2560，估算值远低于真实规模

基础Flajolet Martin 算法实现代码 #

import xxhash
import math

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

def gethash(line):
  num=abs(xxhash.xxh32(line).intdigest())
  return num

fp=open("/content/drive/MyDrive/Data.txt","r")
h_max=0
for line in fp:
  hash_value_1 = gethash(line)
  binary_1 = format(hash_value_1, '032b')       
  t1 = return_trailing_zeroes(binary_1)
  if t1>h_max:
    h_max=t1
fp.close()
print(2**h_max)

该版本存在的核心错误

• 等值判断写法错误：使用is关键字判断字符是否为'0'，is用于判断对象内存地址一致性，等值判断应使用==。当前写法依赖Python小字符串驻留机制碰巧可运行，属于不可靠实现，长文本场景下会直接导致 trailing zero 计数完全失效
• 哈希值处理破坏位分布：对xxhash返回的有符号32位整数取绝对值，会将原符号位纳入数值范围，打乱哈希值各位的独立均匀分布特性，导致 trailing zero 的概率偏离“第r位为1的概率为1/2^r”的理论假设
• 估算值缺失经验修正系数：基础Flajolet Martin算法直接输出2^h_max存在固有正偏差，经典经验修正系数为0.77351，缺失修正项会导致估算结果系统性偏高
• 函数缩进语法错误：return_trailing_zeroes函数内代码缩进层级混乱，未调整的原始代码运行会直接抛出IndentationError

自行实现HyperLogLog算法代码 #

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")
for line in 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 = format(hash_value_1, '032b')
    binary_2 = format(hash_value_2, '032b')
    binary_3 = format(hash_value_3, '032b')
    binary_4 = format(hash_value_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)
    if t1>h1_m:    h1_m=t1
    if t2>h2_m:    h2_m=t2
    if t3>h3_m:    h3_m=t3
    if 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]))
print(distinct_elements)

该版本存在的核心错误

• HyperLogLog核心逻辑完全缺失：标准HyperLogLog需要取哈希值的前k位作为分片标识，分配到m=2^k个独立寄存器存储对应分片的最大 trailing zero 值，当前代码无分片、无寄存器数组，本质是4路独立运行的基础Flajolet实现，不属于HyperLogLog
• 聚合公式完全错误：未使用HyperLogLog标准的调和平均聚合公式，仅对两组单路估算值做算术平均后取中位数，既没有多寄存器的方差降低效果，也没有小基数区间的偏差修正项，会导致估算值系统性偏低
• 依赖未导入：代码中调用了hash32、jhashcode.hashcode、mmh3.hash、statistics模块，但缺少对应的import语句，原始代码运行会抛出NameError
• 同时继承了基础版本的is判断字符错误、哈希值取绝对值破坏位分布的问题

内容的提问来源于stack exchange，提问作者12100