Min Value: Cách ước lượng số giá trị phân biệt

Trong bài trước về Linear Counting, ta đã xem các thuật toán cơ bản để tính và ước lượng số giá trị phân biệt trong một tập dữ liệu. Hôm nay ta xét thêm một thuật toán xác suất cho phép ước lượng số giá trị phân biệt với độ chính xác khá tốt và tốn ít bộ nhớ.

Min Value

Trong bài này ta chỉ làm việc với các số thực thuộc khoảng đơn vị (0; 1). Hãy hình dung một tập hợp các số thuộc khoảng này được phân bố đều, chẳng hạn tập hợp {0,25; 0,5; 0,75}. Hai số kề nhau luôn cách nhau (và cách 0, cách 1) đúng 0,25. Điều này giúp gì cho việc đếm số phần tử phân biệt?

Nếu tôi nói rằng có một tập hợp các số thuộc khoảng đơn vị được phân bố đều như vậy, và các số cách nhau đúng 0,2 – bạn có tính được tập hợp đó có bao nhiêu phần tử không? Tất nhiên, đó là tập hợp {0,2; 0,4; 0,6; 0,8}, có lực lượng bằng 4. Nếu đầu vào là các số thuộc khoảng đơn vị được phân bố đều và ta biết khoảng cách giữa hai số kề nhau, ta dễ dàng tính được số phần tử.

Hơn nữa, khoảng cách giữa hai số kề nhau bằng phần tử nhỏ nhất của tập hợp – khoảng cách giữa hai phần tử kề nhau của tập hợp {0,25; 0,5; 0,75} là 0,25, v.v. Để tính số phần tử của một tập các số phân bố đều, ta chỉ cần tìm được phần tử nhỏ nhất bằng cách nào đó. Khi đó số phần tử p tính bằng công thức đơn giản:

$$p=\frac{1}{m}-1$$

trong đó m là phần tử nhỏ nhất đó.

Và lại băm…

Đúng vậy, nhưng làm sao tận dụng điều này khi đầu vào là các xâu hay các giá trị khác, vốn không thoả mãn điều kiện phân bố đều trong khoảng đơn vị? Ta lại nhờ đến hàm băm cũ quen thuộc, có thể trả về một số hữu tỉ thuộc khoảng đơn vị với mọi đầu vào. Xây dựng hàm băm như vậy rất dễ.

Như vậy từ dữ liệu ta nhận được các số hữu tỉ, nhưng làm sao để các số này phân bố đều? Điều đó thì không làm được, nhưng có thể xoay xở theo cách khác. Từ góc nhìn của ta, hàm băm hoạt động khá “ngẫu nhiên”. Với các xâu rất giống nhau như “chao”, “chap” và “chaq”, hàm băm nhiều khả năng sẽ trả về các checksum rất khác nhau. Nói cách khác: nếu băm 1.000 giá trị khác nhau vào khoảng đơn vị, rất khó xảy ra chuyện phần lớn các số, chẳng hạn, nhỏ hơn một nửa. Ngược lại, rất có thể các số này phân bố tương đối đều. Băm càng nhiều dữ liệu, phân bố càng đều.

Từ ý tưởng này, ta có một thuật toán đơn giản: duyệt dữ liệu vào, băm mỗi phần tử vào khoảng đơn vị và ghi nhớ phần tử nhỏ nhất. Số phần tử phân biệt được ước lượng theo công thức trên. Cài đặt bằng Python:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Hàm unit_interval_hash trả về một số thập phân thuộc nửa khoảng (0; 1]. Hàm count_unique_using_minimum trước hết chuyển mọi giá trị đầu vào thành số như vậy, tìm giá trị nhỏ nhất và trả về 1 / minimum - 1. Lưu ý rằng số giá trị trùng nhau trong tập dữ liệu hoàn toàn không ảnh hưởng – với hai giá trị giống nhau, hàm băm trả về cùng một số hữu tỉ, không làm thay đổi giá trị nhỏ nhất. Vì vậy thuật toán này đếm số phần tử phân biệt.

Kết quả thế nào? (Mỗi dòng là một lực lượng ước lượng được, trong khi lực lượng đúng là 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Chẳng ra gì, phải không? Thuật toán chạy trên 10 tập mã khác nhau, mỗi tập luôn có 10.000 giá trị phân biệt. Các ước lượng tính được phần lớn lệch khá xa. Nếu lấy trung bình, ta được giá trị 18.352. Vẫn lệch khá xa, nhưng mặt khác, hãy xem bộ nhớ cần dùng – nó là hằng số! Để tìm giá trị nhỏ nhất, chỉ cần luôn giữ trong bộ nhớ một biến lưu giá trị nhỏ nhất hiện tại, thế là đủ. Vậy đấy, ước lượng thì tệ, nhưng bù lại hầu như không tốn gì.

Cải tiến

Ta thấy vấn đề chính của thuật toán là không ổn định – lần này cho ước lượng khá tốt (9362), lần khác cho ước lượng lệch hẳn (65536). Khắc phục thế nào? Có thể chia dữ liệu vào thành nhiều phần, đếm số phần tử phân biệt trong từng phần rồi cuối cùng lấy trung bình tất cả. Có thể chia theo kí tự đầu tiên của mã. Tức là ta đếm riêng số giá trị phân biệt của các mã bắt đầu bằng chữ “a”, rồi các mã bắt đầu bằng chữ “b”, v.v. Mã nguồn:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Các thay đổi nằm trong hàm count_unique_using_minimum. Biến min_values lưu giá trị nhỏ nhất của từng nhóm. Cuối cùng ta cộng mọi giá trị nhỏ nhất và chia cho số giá trị đã lưu – được giá trị nhỏ nhất trung bình. Biểu thức 1/average_minimum cho biết số giá trị phân biệt trung bình trong mỗi nhóm – nhân giá trị này với số nhóm, ta được số giá trị phân biệt ước lượng của tập dữ liệu đã cho. Cách làm đã sửa này cho kết quả thế nào?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Vẫn chưa tốt, nhưng chắc chắn tốt hơn. Thuật toán ổn định hơn. Có thể thử sửa hàm để các nhóm được tạo không theo kí tự đầu tiên mà, chẳng hạn, theo hai kí tự đầu tiên của mã, tức là:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Khi đó kết quả như sau:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Như vậy là không tệ, phải không? Nếu thử thêm với 100.000 giá trị phân biệt, hai kí tự đầu tiên và n = 24, ta được các kết quả sau:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Khá chấp nhận được. Nhưng đừng lo, vẫn còn những thuật toán tốt hơn.

Còn bộ nhớ cần dùng thì sao? Ta chỉ cần lưu giá trị nhỏ nhất của mỗi nhóm, không gì thêm. Nếu các mã ở dạng hex, điều đó có nghĩa là ta phải nhớ nhiều nhất 16^x giá trị nhỏ nhất, trong đó x là số kí tự dùng để tạo khoá của nhóm. Mỗi giá trị nhỏ nhất là một số hữu tỉ, tức là một biến kiểu double hoặc float.

Lưu ý cuối cùng: ta có thể chia đầu vào thành nhiều nhóm vì đầu vào là các mã hoạt động như các xâu ngẫu nhiên. Nếu đầu vào không phải xâu ngẫu nhiên mà là dữ liệu theo một định dạng nhất định, ta sẽ phải chia theo cách khác. Chẳng hạn, nếu mọi mã đều bắt đầu bằng tiền tố userid-, thì việc chia nhóm theo kí tự đầu tiên hẳn sẽ không hiệu quả lắm, đúng không.