加权水库采样的初始化（A-Chao实现）

Question

我正在尝试实现A-Chao版本的加权储层采样，如https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao所示>

但是我发现Wiki中描述的伪代码似乎是错误的，尤其是在初始化部分。我读了paper，它提到我们需要处理超重的数据点，但我仍然不知道如何正确初始化。

据我了解，在初始化步骤中，我们要确保所有选择的初始数据点都应具有相同的概率*权重。但是，我不知道超重点与此相关。

我根据Wiki实现的代码，但结果显示它是错误的。

const reservoirSampling = <T>(dataList: T[], k: number, getWeight: (point: T) => number): T[] => {
  const sampledList = dataList.slice(0, k);
  let currentWeightSum: number = sampledList.reduce((sum, item) => sum + getWeight(item), 0);
  for (let i = k; i < dataList.length; i++) {
    const currentItem = dataList[i];
    currentWeightSum += getWeight(currentItem);
    const probOfChoosingCurrentItem = getWeight(currentItem) / currentWeightSum;
    const rand = Math.random();
    if (rand <= probOfChoosingCurrentItem) {
      sampledList[getRandomInt(0, k - 1)] = currentItem;
    }
  }
  return sampledList;
};

我正在尝试实现A-Chao版本的加权水库采样，如https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao所示，但我发现Wiki中描述的伪代码...] >

Answer 1

获得Chao算法产生的分布的最佳方法是实施VarOpt _{k]采样，如Cohen等人从the paper that introduced VarOptk sampling标记为算法1的伪代码中一样>]}

这是arXiv链接，因此非常稳定，但是总而言之，我们的想法是将项目分为“重”（重量足以保证到目前为止包含在样本中）和“轻”（其他）。将较重的项目放在优先队列中，以便轻松删除最轻的项目。当有新物品进来时，我们必须确定它是重的还是轻的，以及哪些重的物品变轻了（如果有）。然后是一个采样程序，用于删除一个项目，该项目使用加权采样专门处理重→轻项目，然后退回到选择统一的随机轻项目（如Chao算法的简单情况）。

使用伪代码的一个窍门是，如果使用浮点算术，则必须对“不可能”的情况稍加小心。将您完成的代码发布到“代码审查”上，如果需要反馈，请在此处ping我。