Loạt bài về các thuật toán ước lượng số giá trị phân biệt trong một đa tập hợp tiếp tục với bài về thuật toán state of the art HyperLogLog. Tuy nhiên, mọi ý tưởng đằng sau thuật toán này đều xuất phát từ thuật toán LogLog đã mô tả trước đây, nên nếu muốn đọc tiếp, hãy chắc chắn rằng bạn đã nắm vững LogLog.

Thuật toán LogLog có hai vấn đề chính:

Giá trị ngoại lệ

Ước lượng cuối cùng của LogLog rất nhạy cảm với các giá trị ngoại lệ, tức là các giá trị nằm rất xa các giá trị còn lại. Thường xảy ra chuyện phần lớn độ dài lớn nhất của hậu tố toàn số 0 trong các nhóm xấp xỉ nhau, chẳng hạn nằm trong khoảng từ 12 đến 15, nhưng rồi bùm – một hậu tố toàn số 0 có độ dài 27. Chênh lệch lớn này làm rối ước lượng số giá trị phân biệt, vì số trung bình cộng thông thường không xử lí tốt trường hợp này. Về cơ bản, đây cũng là hiện tượng khi một vài giám đốc và quản lí cấp cao với mức lương rất cao kéo lương trung bình của cả nước lên.

Các tác giả của thuật toán đã cố khắc phục điều này bằng cách loại bỏ các giá trị ngoại lệ, không tính vài giá trị lớn nhất vào số trung bình, nhưng đó không phải là giải pháp tốt. Về sau họ thử cách khác – thay số trung bình cộng bằng trung bình điều hoà, có tính chất tốt hơn nhiều khi có những giá trị nằm xa số trung bình.

Kết quả rất tệ với lực lượng nhỏ

LogLog cho kết quả rất tệ khi ước lượng lực lượng của các đa tập hợp nhỏ. Nếu đa tập hợp chỉ có ít phần tử phân biệt, LogLog trả về một ước lượng lớn vô lí. Các tác giả giải quyết vấn đề này rất khéo – khi đầu vào là đa tập hợp có lực lượng nhỏ, ta không dùng thuật toán LogLog mà dùng một thuật toán hoàn toàn khác, đó là Linear counting quen thuộc. Nhưng làm sao biết đầu vào là đa tập hợp có lực lượng nhỏ khi chính lực lượng là điều ta chưa biết?

Ta để LogLog ước lượng số phần tử phân biệt, và nếu thấy ước lượng này tương đối nhỏ, ta bỏ ước lượng đó và tính lại bằng thuật toán Linear counting. Nhắc nhanh lại cách Linear counting hoạt động. Ban đầu ta cấp phát một mảng (bit) toàn số 0 có kích thước định trước, thường là một luỹ thừa của 2. Ta duyệt mọi phần tử của đa tập hợp, tính giá trị băm của chúng và chuyển giá trị băm thành một số nguyên i từ 0 đến độ dài mảng trừ 1. Sau đó ghi số 1 vào mảng tại chỉ số i. Cuối cùng ta đếm số chữ số 0 và số chữ số 1 trong mảng, rồi ước lượng lực lượng bằng một công thức đơn giản.

Tuy nhiên, thuật toán LogLog không dùng mảng bit nào để “lưu” các giá trị băm đã tính. Thay vào đó, nó dùng một mảng lưu độ dài lớn nhất của các hậu tố. Mảng có thể như sau:

[2, 5, 9, 0, 5, 4, 4, 0]

trong đó mỗi số là độ dài lớn nhất của hậu tố toàn số 0 trong nhóm giá trị băm tương ứng. Một giá trị khác 0 ở vị trí thứ i nhất thiết có nghĩa là trong đa tập hợp có một phần tử có giá trị băm (3 bit) bằng i. Nói cách khác, có thể chuyển mảng này thành mảng bit cho linear counting bằng cách giữ nguyên các số 0 và thay mọi số dương bằng 1. Từ mảng trên ta được mảng bit:

[1, 1, 1, 0, 1, 1, 1, 0]

Bây giờ có thể áp dụng thuật toán Linear counting để ước lượng lực lượng.

Tuy nhiên có một chỗ dễ sai. Ta lưu vào mảng độ dài lớn nhất của hậu tố toàn số 0, nhưng nếu trong một nhóm nào đó mọi giá trị băm đều kết thúc bằng chữ số 1 thì sao? Chẳng hạn, nếu dùng 3 bit cuối làm mã nhóm của giá trị băm, thì độ dài hậu tố toàn số 0 của giá trị băm “01001100” bằng 0 – vì vectơ “01001” kết thúc bằng chữ số 1. Như vậy, ta sẽ lưu số 0 vào mảng các giá trị lớn nhất tại chỉ số 4 (100₂=4₁₀). Nhưng trong thuật toán linear counting, điều này lại có nghĩa là ta không gặp giá trị nào có giá trị băm bằng 4, điều đó sai.

Vì vậy, ta sửa thuật toán để mảng các giá trị lớn nhất không lưu độ dài của hậu tố toàn số 0 dài nhất, mà lưu chỉ số của “chữ số 1 đầu tiên tính từ bên phải” (để rõ ràng – chỉ số bắt đầu từ 1), tức là độ dài hậu tố toàn số 0 cộng thêm 1. Nhờ vậy, số 0 tại chỉ số i có nghĩa là không có giá trị nào có giá trị băm bằng i, và mảng như vậy có thể dùng cho linear counting.

Cài đặt HyperLogLog

Ta làm từng bước:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

Hàm alpha trả về hệ số hiệu chỉnh cho ước lượng đã tính, điều mà ta đã biết từ lần trước; chỉ khác là với HyperLogLog, alpha có giá trị khác nhau tuỳ theo số nhóm.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

Hàm trả về số bit 0 ở cuối một số.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Hàm duyệt mọi giá trị, chia chúng thành num_buckets nhóm và với mỗi nhóm tính chỉ số của chữ số 1 đầu tiên tính từ bên phải (độ dài hậu tố toàn số 0 dài nhất cộng 1).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Hàm tính theo thuật toán Linear counting, có sửa đổi một chút.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

Hàm chính, kết hợp tất cả lại. Trước hết, hàm tính ước lượng bằng LogLog đã sửa đổi, ở dòng thứ tư dùng trung bình điều hoà thay cho số trung bình cộng, và cuối cùng áp dụng hiệu chỉnh bằng Linear counting nếu ước lượng tính được nhỏ hơn 2,5 lần số nhóm (lúc này ta cho rằng ước lượng LogLog thông thường sẽ kém hơn so với dùng Linear counting) và nếu mảng các giá trị lớn nhất có ít nhất một số 0 (mảng toàn số 1 không dùng được cho Linear counting, xem bài trước). Vậy HyperLogLog cho kết quả thế nào?

Ta chạy đoạn mã thử nghiệm ước lượng lực lượng của các tập hợp có lực lượng lần lượt là 10, 100, …, 1.000.000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Kết quả:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Ta thấy các kết quả luôn lệch khỏi kết quả đúng chưa đến 1%. Rất tốt!

Những cải tiến khác của HyperLogLog

HyperLogLog còn có thêm một số cải tiến thú vị. Một trong các vấn đề còn lại là tốn nhiều bộ nhớ. Nghe khá lạ, vì lần trước ta đã hết lời khen ngợi mức tiêu thụ bộ nhớ và tính được rằng để lưu mảng các giá trị lớn nhất chỉ cần 768 byte. Nhưng vấn đề nảy sinh khi bạn không muốn tính lực lượng của một đa tập hợp khổng lồ, mà muốn tính song song cho vài triệu đa tập hợp nhỏ, hoặc muốn lưu các mảng giá trị lớn nhất đã tính vào cơ sở dữ liệu để xử lí về sau.

Chẳng hạn, nếu tính đồng thời lực lượng của 1 tỉ đa tập hợp, với cách cài đặt hiện tại ta cần 1.000.000.000 lần 768 byte, tức là 768 GB. Một mặt thì như vậy không tệ … nhưng mặt khác ta có thể cài đặt HyperLogLog tốt hơn.

Biểu diễn thưa

Giả sử ta đặt k=12, tức là dùng 12 bit để xác định nhóm, và do đó có 2¹² nhóm giá trị băm khác nhau. Khi bắt đầu thuật toán, ta phải cấp phát một mảng độ dài 4.096 (xem dòng 3 của hàm count_maxims). Giả sử đa tập hợp của ta có 3 phần tử khác nhau. Điều đó có nghĩa là ta ghi giá trị vào 3 vị trí khác nhau của mảng, còn 4.093 giá trị còn lại vẫn bằng 0, tức là 4.093 vị trí đó hoàn toàn không được dùng. Không hiệu quả lắm, phải không?

Để tránh có một mảng phần lớn là số 0 và không được dùng mà vẫn chiếm một phần bộ nhớ quý giá, ban đầu ta có thể lưu các giá trị dưới dạng cặp [chỉ số, giá trị]. Một ví dụ để dễ hiểu hơn. Mảng sau

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

có thể biểu diễn tiết kiệm bộ nhớ hơn nhiều bằng hai cặp:

[0, 7], [4, 12]

Thay vì cấp phát sẵn một đống bộ nhớ không dùng đến, ta có thể cấp phát dần đúng phần bộ nhớ thực sự cần. Cách biểu diễn này gọi là biểu diễn thưa (sparse). Tuy nhiên, đến một lúc nào đó, cách biểu diễn này sẽ tốn bộ nhớ hơn so với lưu bằng mảng – khi đó có thể chuyển biểu diễn thưa thành mảng thông thường mà không mất thông tin.

Độ lệch (offset)

Thực tế cho thấy mọi giá trị trong mảng đều xấp xỉ nhau. Mảng các giá trị lớn nhất thường trông như sau:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Mọi giá trị đều xoay quanh số 13. Một chiến lược khác để giảm kích thước mảng như vậy là trừ mỗi phần tử đi một giá trị cố định và ghi nhớ giá trị đó. Chẳng hạn, có thể trừ đi 8:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Lúc này mỗi giá trị trong mảng chiếm ít bộ nhớ hơn – ở mảng thứ nhất ta cần lưu các số từ 0 đến 15, cần 4 bit, còn với mảng thứ hai chỉ cần 3 bit, vì ta chỉ lưu các số từ 0 đến 7. Tất nhiên điều này đòi hỏi mảng được cài đặt ở mức từng bit. Khi muốn đọc giá trị từ mảng, ta phải cộng lại giá trị đã ghi nhớ.

…và còn rất nhiều cải tiến khác. Nghiên cứu trong lĩnh vực này vẫn đang tiếp diễn, nên chắc chắn sẽ còn những ý tưởng thú vị mới. Lần sau ta sẽ nói về hợp và giao của các vectơ HyperLogLog, và trong tương lai gần sẽ bàn vì sao có thể cần lưu hàng tỉ vectơ HyperLogLog.

Liên kết và tài liệu tham khảo

• Toàn bộ cài đặt của tôi có thể xem trên GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – bài báo gốc giới thiệu HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – phiên bản cải tiến của HyperLogLog gốc, chẳng hạn bổ sung biểu diễn thưa nói ở trên.