跳转到内容

蓄水池抽样

本页使用了标题或全文手工转换
维基百科,自由的百科全书

蓄水池抽样(英语:Reservoir sampling)是一系列的随机算法,其目的在于从包含n个项目的集合S中选取k个样本,其中n为一很大或未知的数量,尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter英语Jeffrey Vitter在其论文[1]中所提及的算法R

引用Dictionary of Algorithms and Data Structures[2]所载的算法,包含以下步骤(假设数组S以0开始标示):

從S中抽取首k項放入「水塘」中
對於每一個S[j]項(j ≥ k):
   隨機產生一個範圍從0到j的整數r
   若 r < k 則把水塘中的第r項換成S[j]項

实例

高德纳计算机程序设计艺术中,有如下问题:

可否在一未知大小的集合中,随机取出一元素?

例如在一很大,但未知确实行数的文字档中抽取任意一行。如果要确保每一行抽取的几率相等,即是说如果最后发现文字档共有N行,则每一行被抽取的几率均为1/N,则有如下算法(以Perl表示)

$line;
$n = 0;
srand;
while(<>) {
    $n++;
    $line = $_ if (rand < (1/$n));
}

以下Perl程序为上述程序之精简写法:

srand;
rand($.) < 1 && ($line = $_) while <>;

上例中,在循环内第n行被抽取的几率为1/n,以表示。如果文件共有N行,任意第n行被抽取的几率为

故此,各行被抽取的几率均相同。

由于上述算法不需要先把整个文件扫描以判定总行数再作抽样,此算法是一在线算法

以上问题可扩展为

可否在一未知大小的集合中,随机取出k个元素?

亦即是说,如果文件共有行,则每一行被抽取的几率为,则算法为

$k = 輸出數量;
@lines;
$n = 0;
srand;
while(<>) {
    $n++;
    if ($n <= $k) {
        push(@lines, $_);
    } else {
        $r = int(rand($n));
        if ($r < $k) {
            $lines[$r] = $_;
        }
    }
}

上例中,在循环内第n行被抽取的几率为k/n,以表示。如果文件共有N行,任意第n行被抽取的几率为

因此,各行被抽取的几率均相同。同理,此算法亦是在线算法。

在蓄水池算法的定义中,并没有要求每一项目被抽取的几率相同,然而相同几率的情况较常用。

参考文献

  1. ^ Jeffrey Scott Vitter. Random Sampling with a Reservoir (PDF). [2020-02-09]. (原始内容存档 (PDF)于2020-02-28) (英语). 
  2. ^ reservoir sampling. [2020-02-09]. (原始内容存档于2018-10-13) (英语).