在不使用python的EMD包的前提下帮我复现python的EMD完整算法

Earth Mover's Distance (EMD) 或称为 Wasserstein 距离是一种衡量两个概率分布之间“距离”的方法，它考虑了将一种分布转换成另一种分布所需的最小工作量。在Python中，如果没有直接使用的EMD包如`scipy.stats.wasserstein_distance`，你可以手动实现基本步骤：

1. **计算累积分布函数** (CDFs): 对于两个输入的概率分布P和Q，首先需要得到它们的累积分布函数。

def cdf(values):
    values = sorted(values)
    cum_dist = np.cumsum(values / sum(values))
    return values, cum_dist

def compute_cdfs(dist1, dist2):
    return cdf(dist1), cdf(dist2)

2. **分配代价矩阵**: 根据两组CDF创建一个二维数组，元素值表示从一个累积点移动到另一个累积点的成本。

def allocate_costs(cdf_p, cdf_q):
    cost_matrix = np.abs(np.outer(cdf_p[1], 1 - cdf_q[1]))
    return cost_matrix

3. **构造运输图**: 这是一个二维网格，其中每个单元格代表从一个累积点到另一个累积点的一个单位转移。

4. **找到最短路径**: 使用经典的匈牙利算法（也称Kuhn-Munkres算法）来寻找成本最低的匹配策略，将其转换为EMD。

from scipy.optimize import linear_sum_assignment as hungarian_algorithm

def emd(dist1, dist2):
    cdf_p, cdf_q = compute_cdfs(dist1, dist2)
    cost_matrix = allocate_costs(cdf_p, cdf_q)
    
    row_ind, col_ind = hungarian_algorithm(cost_matrix)
    emd_value = cost_matrix[row_ind, col_ind].sum()
    
    return emd_value

注意：这个实现没有优化过程，适用于小型数据集。对于大型数据，可以考虑使用更高效的库或者专门的EMD实现。