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

Làm thế nào để đếm số giá trị phân biệt trong một tập dữ liệu khi dữ liệu thực sự rất nhiều? Chẳng hạn, ta có thể có một dịch vụ đo số người dùng phân biệt trên một trang web lớn, hay thậm chí trên toàn bộ tên miền .vn/.com/.whatever hoặc đại loại như vậy.

Cách làm ngây thơ

Có gì đâu mà phải nghĩ: cứ duyệt qua dữ liệu và lưu mỗi giá trị đúng một lần vào một cấu trúc dữ liệu phù hợp. Trong Python, có thể viết như sau (mã cố ý viết dài dòng):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Cách này chạy được. Nhưng nếu dữ liệu là các mã định danh v4 duy nhất dài 36 kí tự và có chẳng hạn 10 triệu mã như vậy thì sao? Chương trình vẫn tính ra giá trị đúng, nhưng tốn bao nhiêu bộ nhớ? Ta thử tính. Để đơn giản, giả sử ta lưu uuid đúng dưới dạng xâu 36 kí tự. Một uuid chiếm 36 byte, 10 triệu mã chiếm 360 MB.

Phải thừa nhận là không ít. Nếu có 100 triệu mã phân biệt, bộ nhớ chiếm dụng đã lên đến cỡ gigabyte. Mà đó mới chỉ là phần bộ nhớ của riêng dữ liệu. Cộng thêm chi phí phụ của Python/JavaScript chẳng hạn, thì chỉ với 10 triệu mã cũng có thể lên đến cỡ gigabyte:

Chẳng ai muốn vậy. Làm sao thoát khỏi tình huống này?

Có thể thử lưu bản thân các mã hiệu quả hơn, có thể dùng C thay cho Python để giảm đáng kể bộ nhớ cần dùng, nhưng vẫn chưa ổn, chương trình vẫn chiếm một lượng bộ nhớ khổng lồ. Còn lại một câu hỏi: ta có thật sự cần biết chính xác đến từng đơn vị rằng số giá trị phân biệt đúng là 9.563.618 không? Có sao không nếu ta làm việc với con số 9.547.666? Nếu câu trả lời của bạn là có sao và bạn muốn con số chính xác, thì xin cứ tự nhiên. Còn không, ta hãy xem các cách ước lượng số giá trị phân biệt trong một tập dữ liệu sao cho chính xác nhất, nhanh nhất và tốn ít bộ nhớ nhất.

Hàm băm – cứu tinh của ta

Xét một hàm băm nhận đầu vào là một xâu và trả về một số n bit. Nếu bạn quen với các hàm băm “trả về xâu” hơn, thì cứ hình dung là xâu đó lại được chuyển thành số, chẳng có gì phức tạp. Số bit cho biết số đó lớn đến đâu. Hàm 8 bit trả về một số chiếm 8 bit, mà 8 bit lưu được 2⁸ giá trị khác nhau, thường là các số nguyên từ 0 đến 255. Từ đây ta làm việc với hàm băm 24 bit. Hàm như vậy trả về 2²⁴ giá trị khác nhau, tức là 16.777.216 giá trị.

Thay vì lưu bản thân các giá trị, ta lưu giá trị băm 24 bit của chúng. Để lưu 10 triệu giá trị băm 24 bit, ta cần 30 MB. Như vậy tốt hơn 360 MB trước đó cả một bậc độ lớn. Mã có thể như sau:

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

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

Hàm hash là hàm có sẵn của Python và trả về một số nguyên; hàm nhash là một cách cài đặt ngây thơ hàm băm n bit. Không cần hiểu nó hoạt động thế nào, vì dù sao nó cũng không hoạt động đúng – kết quả của hàm không chiếm 24 bit – nhưng điều đó lúc này không quan trọng, tôi chỉ muốn minh hoạ nguyên lí.

Tiếp theo là hàm count_unique_using_nhash đếm các giá trị phân biệt. Hàm duyệt qua mọi giá trị, tính giá trị băm của chúng và lưu vào biến found nếu giá trị đó chưa có ở đó.

Vấn đề của cách làm này là hàm băm có thể trả về cùng một checksum cho các xâu khác nhau – có thể xảy ra xung đột. Càng nhiều xung đột, kết quả càng kém chính xác. Hàm count_unique_using_nhash hầu như luôn trả về số giá trị phân biệt nhỏ hơn số thực tế.

Nên chọn hàm băm nào? Điều đó không quá quan trọng, nhưng nói chung người ta khuyên dùng một biến thể của MurmurHash.

Bitmap

Nếu đã học lập trình C, hẳn bạn biết bitmap (mảng bit). Có thể tận dụng chúng thế nào?

Ta phác thảo ý tưởng bằng một mảng. Thực ra ta không cần lưu các checksum đã tính; ta có thể tạo một mảng độ dài 2²⁴ và khởi tạo mọi phần tử bằng 0. Mỗi khi gặp một checksum – mà checksum là một số! – ta ghi số 1 vào mảng tại chỉ số checksum, đánh dấu rằng checksum này đã gặp. Khi đó số phần tử phân biệt xấp xỉ bằng số chữ số 1 trong mảng. Mã có thể như sau:

def count_unique_using_array(values):
    # danh sach do dai 2^24, khoi tao toan so 0
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Tuy nhiên, dùng mảng trong trường hợp này rất tốn bộ nhớ, vì mỗi ô chỉ cần lưu số 1 hoặc số 0. Thay vào đó, ta có thể dùng mảng bit. Để dễ hiểu: một số nguyên (integer) có thể lưu, chẳng hạn, trong 32 bit. Chuyển số 354 sang hệ nhị phân, ta được 101100010. Như vậy, số 354 được lưu trong máy tính dưới dạng integer 32 bit (bỏ qua các chi tiết nhỏ) như sau:

00000000 00000000 00000001 01100010

Đây là một định dạng khá dễ chịu mà ta có thể tận dụng, đúng không? Trong hàm của ta, ta chỉ muốn lưu các số 0 và 1, và vừa thấy rằng một số thông thường thực ra chỉ là một đống số 0 và số 1 (cũng như mọi thứ trong máy tính…). Tóm lại, nhờ các phép toán thao tác bit, ta có thể lưu số 1 sao cho nó thực sự chỉ chiếm 1 bit.

Quay lại hàm dùng mảng. Nếu viết lại bằng mảng bit, với hàm băm 24 bit ta chỉ cần mảng bit kích thước 2²⁴ bit, tức là 2 MiB. Một cải tiến đáng kể!

Nếu dùng hàm băm 32 bit, có 2³² giá trị đầu ra khác nhau, tức là 4.294.967.296 giá trị, ta cần mảng bit kích thước nửa gigabyte. Như vậy không tệ chút nào, vì với nó ta có thể đếm số giá trị phân biệt lên đến cỡ hàng tỉ.

Linear Counting

Tôi đã nói rằng khi dùng hàm băm, ta chỉ được một ước lượng của số giá trị phân biệt. Số giá trị phân biệt càng gần số giá trị đầu ra khác nhau của hàm băm thì ước lượng này càng kém chính xác. Dễ hiểu là với tập dữ liệu có 5 tỉ giá trị phân biệt, hàm băm 24 bit đơn giản là không đếm được.

Tuy nhiên, ước lượng tính bằng hàm băm có thể làm chính xác hơn. Người ta dùng một ý tưởng đơn giản: tập dữ liệu càng có nhiều giá trị phân biệt thì càng dễ xảy ra xung đột. (Xung đột = hai đầu vào khác nhau cho cùng một đầu ra của hàm băm, cùng một checksum.) Bây giờ ta sẽ tính toán một chút, vì vậy ta đặt vài biến:

Ta làm việc với hàm băm n bit h.
Số đầu ra có thể có của hàm h là 2ⁿ. Kí hiệu số này là m, tức là m=2ⁿ.
Kí hiệu A (chữ in hoa) là mảng bit dùng để ghi lại những checksum đã gặp. Mảng A có độ dài m.
Sau khi thuật toán duyệt hết tập dữ liệu, một số giá trị trong mảng bit bằng 0 và một số bằng 1. Ta đặc biệt quan tâm đến tỉ số “số chữ số 0 chia cho độ dài mảng”, cho biết tỉ lệ số 0 trong mảng bit. Ban đầu tỉ số này bằng 1, vì mảng được khởi tạo toàn số 0. Nếu một nửa là 0, một nửa là 1, tỉ số bằng một nửa, v.v. Kí hiệu giá trị này là Z và tính bằng Z = (số chữ số 0) / m.

Lúc này ta có: Z càng lớn thì ta càng chắc rằng ước lượng số giá trị phân biệt là chính xác. Chẳng hạn, nếu duyệt một tập dữ liệu rỗng, mảng bit vẫn toàn số 0 và Z bằng 1 – ta hoàn toàn chắc chắn rằng tập dữ liệu có số phần tử phân biệt đúng bằng số chữ số 1 trong mảng bit, tức là 0.

Nếu Z bằng 0,99, mảng bit có 1% số ô là số 1, còn 99% là số 0. Vẫn tốt: nhiều khả năng trong quá trình tính không có quá nhiều xung đột, và chỉ cần hiệu chỉnh rất ít hoặc không cần hiệu chỉnh. Nhưng nếu Z bằng 0,05, chỉ 5% mảng còn là số 0, và nhiều khả năng trong quá trình tính ta đã gặp rất rất nhiều xung đột – cần hiệu chỉnh nhiều.

Vậy tính phần hiệu chỉnh này thế nào? Ta dùng đến lôgarit, là hàm số có dạng như sau:

Ta quan tâm đến phần màu đỏ trên nửa khoảng (0; 1]. Nếu lấy giá trị Z trên trục x, thì Z càng lớn, giá trị y càng gần 0. Ngược lại, Z càng nhỏ, giá trị y càng nhỏ. Ước lượng cuối cùng nhận được bằng cách nhân số này với -m. Lưu ý rằng với Z đủ nhỏ, ta được một số thậm chí nhỏ hơn -1, và nhân giá trị này với -m, ta được một ước lượng lớn hơn m: ta ước lượng rằng số giá trị phân biệt lớn hơn số checksum có thể có của hàm băm h.

Công thức đầy đủ để tính số p giá trị phân biệt như sau:

$p = - m \cdot \ln Z$

Một cách cài đặt (không dùng mảng bit, chỉ dùng mảng thông thường) có thể như sau:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

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

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log o day la logarit tu nhien co so e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

Trong hàm linear_counting, trước hết ta tính ước lượng ban đầu bằng thuật toán trước, dùng hàm băm n bit. Sau đó ta tính tỉ lệ số 0 trong mảng và hiệu chỉnh theo công thức. Lôgarit trong mã là lôgarit tự nhiên. Biến nonunique_values chứa number_of_unique_values xâu phân biệt, nên trong ví dụ này danh sách nonunique_values có 10.000 giá trị phân biệt. Dòng thứ sáu trông hơi lạ có tác dụng làm cho mảng có các giá trị lặp lại: đơn giản là ta nối thêm chính danh sách đó vào cuối danh sách, nên mỗi giá trị xuất hiện trong mảng 2 lần. Sau đó là tính toán. Lí tưởng nhất là hàm cho kết quả danh sách có 10.000 giá trị phân biệt. Đầu ra:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Vì mỗi lần chạy danh sách nonunique_values được sinh khác nhau, nên kết quả mỗi lần sẽ khác nhau. Ta đã dùng hàm băm 16 bit. Ta thấy ước lượng ban đầu từ hàm count_unique_using_array là danh sách có 9.289 giá trị phân biệt. Nhờ hiệu chỉnh, ta làm chính xác ước lượng này thành 10.017, khá tốt: ước lượng chỉ lớn hơn 0,17%, trong khi trước đó nhỏ hơn 7,11% – khá nhiều.

Nếu dùng hàm băm “lớn hơn”, chẳng hạn 24 bit, ta được kết quả chính xác hơn:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Bản thân ước lượng ban đầu đã ổn, sau khi hiệu chỉnh ta được đúng 10.000. Để minh hoạ, có thể thử với 1 triệu mã phân biệt, tức là number_of_unique_values = 1000000. Với hàm băm 24 bit, ta được kết quả sau:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Khá ổn. Hơn nữa, nếu cài đặt bằng mảng bit, mảng chỉ chiếm 2 MB như đã nói (cộng với phần bộ nhớ mà ngôn ngữ lập trình dùng). Theo tôi là khá tốt. But we can do better! Much better. Nhưng để lần sau.

Trong lúc chờ đợi, bạn có thể đọc bài báo A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Hoặc có thể đọc tiếp phần sau của loạt bài: thuật toán min-value.

Mục lục: Linear counting: Cách ước lượng số giá trị phân biệt, Min Value: Cách ước lượng số giá trị phân biệt, LogLog: Cách ước lượng số giá trị phân biệt, HyperLogLog: Cách ước lượng thật chính xác số giá trị phân biệt

« Bài trước: Chuyển ôtômat thành biểu thức chính quy

Bài tiếp: Min Value: Cách ước lượng số giá trị phân biệt »