Hồ chứa mẫu

Hồ chứa mẫu (tiếng Anh: Reservoir sampling) là một họ trong các giải thuật ngẫu nhiên để lựa chọn ra một mẫu gồm k phần tử từ một tập S gồm n phần tử, trong đó n là một số rất lớn không thể lưu trữ được trong bộ nhớ trong của máy tính hoặc chưa biết.

Dưới đây là một thuật toán O(n) đơn giản được miêu tả trong cuốn sách Dictionary of Algorithms and Data Structures

Giải thuật mẫu

array R[k]; // hồ chứa mẫu lưu kết quả

integer i, j;

// làm đầy hồ chứa mẫu bằng k phần tử đầu tiên của S
for each i in 1 to k do
R[i] := S[i]
done;

// thay thế các phần tử trong hồ chứa mẫu với xác suất giảm dần
for each i in k+1 to length(S) do
j := random(1, i);  // lưu ý: bao gồm 1 và i
if j <= k then
  R[j] := S[i]
fi
done

Trong thuật toán này, ban đầu một hồ chứa mẫu gồm k phần tử được tạo ra bởi k phần tử đầu tiên trong tập S. Sau đó chúng ta sẽ xử lý từng phần tử còn lại của S: với mỗi phần tử thứ i của tập S, một số ngẫu nhiên j từ 1 đến i được tạo ra (xác suất 1/i) và được đưa vào hồ chứa nếu nó nhỏ hơn k (xác suất k/i). Sau khi thuật toán kết thúc, mỗi phần tử trong S sẽ được đưa vào bể chứa với xác suất bằng nhau là k/n.

Hạn chế của giải thuật

Giải thuật trên được xây dựng dựa trên giả thuyết rằng toàn bộ hồ chứa mẫu có thể được lưu trong bộ nhớ trong của máy tính (nghĩa là k không phụ thuộc vào n). Trong trường hợp k phụ thuộc vào n (ví dụ chúng ta muốn lấy một hồ chứa mẫu có kích cỡ bằng 1/3 tập S (k=n/3) thì chúng ta sẽ phải sử dụng giải thuật khác. Một số cài đặt thực thi phân tán của giải thuật này cũng đã được đề xuất