如何在BigQuery/SQL中计算整数概率分布的One-dimensional earth mover's distance？

嘿，我帮你把这个一维推土机距离（Earth Mover's Distance）的计算逻辑和实现方案整理成清晰的Markdown格式啦，方便你理解和落地：

核心定义 #

给定两个整数上的有限概率分布P和Q，它们的支撑集都落在0到某个大整数N之间。一维推土机距离指的是将P转换为Q所需的最小总成本——其中把整数n上的概率值r移动到整数m的成本计算公式为：r * |n - m|。

简单计算算法（伪代码+实现思路） #

这个问题的核心算法非常直观，本质是通过追踪累积概率的差值来计算总移动成本：

伪代码实现 #

# 初始化变量
emd = 0
cumulative_p = 0  # P的累积概率
cumulative_q = 0  # Q的累积概率
n = 0

# 遍历所有可能的整数点
while n <= N:
    # 累加当前n点的概率（支撑集外的点概率为0）
    cumulative_p += P在n处的概率（若n不在P的支撑集则取0）
    cumulative_q += Q在n处的概率（若n不在Q的支撑集则取0）
    
    # 累加当前累积概率的绝对差值到总距离
    emd += |cumulative_p - cumulative_q|
    
    n += 1

实际落地说明 #

假设你有两张存储概率分布的表（比如数据库表或者内存中的结构化数据），表结构包含n（整数列）和对应的概率列（比如prob_p、prob_q），你可以按照以下步骤实现：

• 先确定最大整数N：取P和Q支撑集中的最大整数即可，无需遍历到不必要的大数
• 遍历从0到N的每个整数n：
  • 从表中取出P在n处的概率（没有则取0），累加到cumulative_p
  • 同理取出Q在n处的概率，累加到cumulative_q
  • 计算当前累积概率的绝对差，加到总距离emd中

Python示例代码 #

如果用Python实现，假设P和Q用字典存储（key是整数n，value是对应概率），代码可以写成这样：

def calculate_1d_emd(P: dict, Q: dict, max_n: int) -> float:
    """计算一维整数概率分布的推土机距离"""
    total_emd = 0.0
    cum_p = 0.0
    cum_q = 0.0
    
    for n in range(max_n + 1):
        cum_p += P.get(n, 0.0)
        cum_q += Q.get(n, 0.0)
        total_emd += abs(cum_p - cum_q)
    
    return total_emd

注意事项 #

• 务必确保P和Q是归一化的概率分布（所有概率之和为1），否则计算出的距离会不符合定义
• 如果不确定max_n，可以用max(max(P.keys()), max(Q.keys()))来自动获取最大整数点，减少遍历次数

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