Échantillonnage par réservoir : un échantillon uniforme à partir d'un flux de longueur inconnue

Objectif

Sélectionner k éléments de façon uniformément aléatoire dans une séquence dont la longueur n'est connue qu'à la fin, en une seule passe et avec une mémoire indépendante de cette longueur : échantillonner des lignes de journal pour inspection, choisir des lignes dans un export volumineux, ou sélectionner des exemples pour un rapport sans tout charger en mémoire.

Prérequis

Un générateur pseudo-aléatoire doté d'une fonction d'entier uniforme. Le module random de Python, documenté comme reposant sur le Mersenne Twister, convient à l'échantillonnage statistique ; la même documentation avertit qu'il ne convient pas à des fins de sécurité, donc utiliser secrets lorsqu'un adversaire ne doit pas pouvoir prédire l'échantillon. Le flux est lu une seule fois ; les k éléments tiennent en mémoire.

Étapes

1. Stocker les k premiers éléments dans une liste, le réservoir.
2. Pour chaque élément suivant, numéroté i (en comptant à partir de 1), tirer un entier j uniformément entre 1 et i. Si j est inférieur ou égal à k, écraser l'emplacement j du réservoir avec cet élément ; sinon, écarter l'élément.
3. Lorsque le flux se termine, le réservoir constitue l'échantillon. L'ordre des emplacements n'a aucune signification ; le mélanger si l'ordre importe en aval.
4. Se convaincre de l'uniformité du résultat. L'élément i entre avec une probabilité k/i. Un élément du réservoir survit à l'arrivée de l'élément t avec une probabilité 1 - 1/t = (t-1)/t. En multipliant les probabilités de survie pour t allant de i+1 à n, la formule se télescope en i/n, et (k/i) * (i/n) = k/n, la même valeur pour chaque élément, y compris les k premiers, qui entrent avec une probabilité de 1 et survivent avec une probabilité k/n.
5. Cas particulier k = 1 : remplacer l'unique emplacement avec une probabilité 1/i.
6. Tester avec un petit flux, par exemple 10 éléments et k = 3, en répétant la procédure de nombreuses fois et en vérifiant que la fréquence d'inclusion de chaque élément se rapproche de 0,3 ; vérifier également que le code ne demande jamais la longueur du flux.
7. Amorcer (seed) le générateur dans les tests pour garantir la reproductibilité, et journaliser la graine en production afin qu'un échantillon signalé puisse être régénéré.

Résultat attendu

Chaque élément se trouve dans l'échantillon avec une probabilité exactement égale à k/n, avec un seul tirage aléatoire par élément, une mémoire proportionnelle à k, et sans jamais avoir besoin de la longueur du flux.

Limites et base de vérification

L'échantillon est uniforme par éléments, pas par temps ni par octets ; un flux en rafales est échantillonné par comptage. Plusieurs flux parallèles nécessitent de fusionner leurs réservoirs avec des poids proportionnels à leur nombre d'éléments. Il existe des variantes pondérées et des variantes qui sautent en avant pour économiser des tirages aléatoires, non traitées ici. La correction découle du calcul de l'étape 4 ; aucune mesure n'est revendiquée.