题目：如何从无穷尽流中等概率的抽样出一个单词？
或许我们换一种说法会更加容易理解.等概率的抽取出一个单词，也即随机的抽取一个单词。本体的难点在于没有给定单词数，而是一个无尽的流。
这个问题可以用蓄水池抽样的方法来思考。先简单的介绍一下蓄水池抽样(reservoid sample)算法，我们可以结合算法理解其原理。
Init : a reservoir with the size： kfor i= k+1 to NM=random(1, i);if( M < k)SWAP the Mth value and ith valueend for
该算法设定蓄水池的大小为k，也就是等概率的取出k个单词。
即先把前k个数放入蓄水池，对第k+1，我们以k/(k+1)概率决定是否要把它换入蓄水池，，换入时随机的选取一个作为替换项，这样一直做下去，对于任意的样本空间n，对每个数的选取概率都为k/n。也就是说对每个数选取概率相等。
证明如下：
蓄水池问题是一类问题，可以解决无穷尽流进行等概率抽取的问题。在工作中会有比较重要的应用。
参考：
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生难免遇风雨,天空晴朗有阴云,别因雨水湿透衣衫而难过,
