LogLog: Cách ước lượng số giá trị phân biệt
Sau các phần trước về Linear Counting và Min Value, cuối cùng ta đến với LogLog, gần như tốt nhất trong các thuật toán xác suất ước lượng số giá trị phân biệt trong một tập dữ liệu. Tốt hơn nữa chỉ có người em HyperLogLog, phát triển từ LogLog, nhưng thuật toán đó để lần sau.
Nhắc lại bài toán. Đầu vào là một tập dữ liệu/đa tập hợp, chẳng hạn một mảng/bộ sinh các mã định danh. Trong mảng này, một số giá trị xuất hiện nhiều lần, và ta muốn đếm số giá trị phân biệt trong mảng. Số này gọi là lực lượng. Ta giả định lực lượng này thực sự rất lớn, nếu không thì có thể dùng các thuật toán thông thường.
Ý tưởng của thuật toán LogLog
Giả sử ta có một tập các vectơ nhị phân. Đừng lo, chẳng hạn 0001011001001100 là một vectơ nhị phân độ dài 16. Giả sử ta có các vectơ nhị phân độ dài 32, tổng cộng 1 triệu vectơ, tất cả đều được sinh hoàn toàn ngẫu nhiên. Có bao nhiêu vectơ kết thúc bằng chữ số 0?
Tất nhiên ta không biết chính xác, nhưng nếu các vectơ thực sự được sinh ngẫu nhiên thì khoảng một nửa số vectơ kết thúc bằng 0, tức là 500 nghìn vectơ. Bao nhiêu vectơ kết thúc bằng 00? Một phần tư. Bằng 000? Một phần tám. Và cứ thế. Có thể minh hoạ đại khái như sau:
dạng vectơ tỉ lệ trong tất cả các vectơ
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Nếu hỏi về hậu tố (hậu tố là xâu nằm ở cuối một xâu khác – ngược với tiền tố) độ dài d, ta kì vọng tìm được v vectơ kết thúc bằng hậu tố đó. Giá trị v tính bằng:
trong đó N là tổng số vectơ trong tập. Hậu tố độ dài 3 (chẳng hạn …010) sẽ xuất hiện ở khoảng 1/2^3 N = 1/8 N vectơ, tức là 12,5% tổng số vectơ.
Bây giờ là một chút “xoắn não”. Cho đa tập hợp gồm 1024 vectơ phân biệt. Có bao nhiêu vectơ kết thúc bằng hậu tố 0000000000 (10 chữ số 0)? Thay vào công thức, ta được
Ồ, đúng 1! Trong khoảng một nghìn vectơ nhị phân sinh ngẫu nhiên, theo kì vọng sẽ có đúng một vectơ kết thúc bằng 10 chữ số 0. Làm sao dùng thông tin này để ước lượng số phần tử phân biệt? Ta có thể đi theo chiều ngược lại. Nếu duyệt mọi vectơ nhị phân đầu vào và thấy rằng trong tập chỉ có đúng một vectơ kết thúc bằng 10 chữ số 0 thì sao? Khi đó ta có thể ước lượng rằng tập có 1024 vectơ!
Tổng quát hoá và xây dựng thuật toán
Mục tiêu là tìm một hậu tố chỉ có ở đúng một vectơ, đồng thời hậu tố đó ngắn nhất có thể. Tuy nhiên điều này rất khó, vì để thực sự tìm được vectơ như vậy, ta phải lưu mọi hậu tố, mà ta không muốn thế vì sẽ tốn quá nhiều bộ nhớ. Thay vào đó, ta bằng lòng với việc tìm dãy chữ số 0 dài nhất ở cuối vectơ.
Như vậy, ta duyệt mọi vectơ, với mỗi vectơ đếm xem nó có bao nhiêu chữ số 0 ở cuối, và dùng một biến lưu giá trị lớn nhất trong các giá trị này. Duyệt xong mọi vectơ, ta biết độ dài của hậu tố dài nhất chỉ gồm chữ số 0. Kí hiệu độ dài này là d. Bây giờ ta biến đổi công thức trên để biểu diễn N theo các đại lượng khác, tức là để N là đầu ra của thuật toán, không phải đầu vào. Ở đây có thể thay v bằng 1, vì ta kì vọng tìm được đúng một vectơ như vậy, tức là kì vọng v=1.
Như vậy, khi tìm được độ dài d của hậu tố toàn số 0 dài nhất, ta ước lượng lực lượng bằng công thức N=2d.
Làm sao có các vectơ nhị phân ngẫu nhiên?
Với các vectơ nhị phân ngẫu nhiên, thuật toán đã hoạt động, nhưng làm sao áp dụng cho dữ liệu thực? Như thường lệ, ở đây ta cũng dùng một hàm băm phù hợp. Với tập dữ liệu đầu vào, chẳng hạn các mã định danh (xâu), trước hết ta băm chúng. Đầu ra của hàm băm n bit là n bit, mà về mặt thực tế trông như các vectơ nhị phân sinh ngẫu nhiên.
Bây giờ ta có thể viết thuật toán:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
Hàm trailing_zeroes trả về số chữ số 0 ở cuối một số. Nó làm việc đó thế nào? Nếu bạn chưa hiểu từ mã nguồn thì tốt nhất đừng hỏi. Còn hàm cho kết quả tốt đến đâu? Với tập hợp có 100 nghìn phần tử phân biệt, hàm cho ước lượng 524.288.
Ừm…
Chẳng tốt lắm, phải không? Nhưng không sao! Ta thử cải tiến thuật toán đúng như với Min Value trước đây. Ta chia dữ liệu vào thành nhiều nhóm rời nhau, với mỗi nhóm tính hậu tố toàn số 0 dài nhất, cuối cùng tính độ dài trung bình của hậu tố toàn số 0 và dùng nó để ước lượng số giá trị phân biệt.
Chẳng hạn, ta có thể quy định 2 bit cuối của mỗi vectơ xác định số thứ tự của nhóm chứa vectơ đó. Sáu vectơ sau
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
có thể chia thành 4 nhóm theo phần đuôi của chúng:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Tiếp theo, ta tính độ dài hậu tố toàn số 0 dài nhất của mỗi vectơ, nhưng bỏ qua các bit đã dùng làm số thứ tự nhóm. Các “hậu tố” toàn số 0 được tô màu xanh lá:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Ở cuối là độ dài của hậu tố toàn số 0 dài nhất trong mỗi nhóm. Từ các độ dài này, ta tính được số trung bình cộng, bằng 2,75. Thay giá trị này vào công thức, ta được
Đó là số phần tử phân biệt trung bình trong mỗi nhóm. Tất nhiên con số này hoàn toàn không khớp, nhưng đừng bận tâm, với các tập nhỏ thuật toán LogLog cho kết quả rất tệ.
Để ước lượng lực lượng của toàn bộ tập hợp, ta còn phải nhân giá trị này với số nhóm: 6,727 · 4 = 26,908. Thuật toán tính ra rằng tập có khoảng 27 giá trị phân biệt. Thực tế có 6 giá trị, nên kết quả lệch hoàn toàn, nhưng lúc này điều đó thật sự không quan trọng.
Cài đặt thuật toán
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
Tham số k xác định số bit được dùng làm chỉ số nhóm. Tham số này quyết định độ chính xác của thuật toán – k càng lớn, độ chính xác càng cao. Biến bucket_index lưu số thứ tự của nhóm. Phép “ảo thuật” ở vế phải của dấu bằng hoạt động thế nào?
Biến num_buckets lưu số nhóm, luôn là một luỹ thừa của 2. Chẳng hạn, nếu k = 3 thì num_buckets=8. Trong hệ nhị phân, số 8 viết là 1000. Trừ đi 1, ta được số 7, viết là 0111. Lấy num_buckets trừ 1, ta luôn được một số có k chữ số 1 ở cuối và toàn chữ số 0 ở phía trước. Tiếp theo ta thực hiện phép AND bit (đó là toán tử &). Với vectơ 1110110010100101, phép toán này như sau:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Mục đích của toàn bộ “phép ảo thuật” này là nhận được một số có toàn chữ số 0 ở phía trước, còn k bit cuối giống hệt giá trị băm h đã cho.
Tiếp theo ta tính bucket_hash, là giá trị băm ban đầu đã bỏ đi k bit cuối bằng cách dịch toàn bộ giá trị băm sang phải k bit. Phép dịch đơn giản là dịch mọi bit của số sang phải k vị trí và điền chữ số 0 vào bên trái. (Dịch bit sang phải 1 vị trí cũng giống như chia số cho 2 và bỏ phần dư.) Dịch vectơ 1110110010100101 sang phải 3 vị trí, ta được 0001110110010100. Vectơ này được lưu trong biến bucket_hash.
Tiếp theo ta đếm số chữ số 0 ở cuối vectơ này, và nếu giá trị đó lớn hơn giá trị lớn nhất hiện lưu trong mảng max_zeroes tại chỉ số bucket_index, ta ghi đè giá trị mới.
Cuối cùng chỉ còn tính số chữ số 0 trung bình trong mọi nhóm và tính số phần tử phân biệt trung bình trong mỗi nhóm (2 ** average_max_zeros). Vì có tất cả num_buckets nhóm, ta nhân giá trị này với số nhóm và được ước lượng cuối cùng của số phần tử phân biệt. Phù, cũng không đau đớn gì. Kết quả với một số tập dữ liệu chứa 250.000 giá trị phân biệt và k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Khôngggg, vẫn sai :-(. Nhưng đừng lo, ta đã khá gần rồi. Lưu ý rằng mọi kết quả đều lớn hơn kết quả đúng. Trong quá trình chạy thuật toán, các sai số tích tụ lại nên ước lượng lớn hơn hẳn kết quả đúng. Tuy nhiên, các sai số này khá ổn định và có thể ước lượng được sai số lớn đến đâu. Nhân ước lượng với một hằng số “lấy đại” 0,79402, ta được kết quả tốt hơn hẳn:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Tôi thử thêm với một đa tập hợp có lực lượng 1 triệu, kết quả:
Kết quả Sai số (tỉ số)
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Tuyệt! Sai số dưới 2,5%, một kết quả đáng nể. Thưa quý vị, đó chính là thuật toán LogLog. Cài đặt cuối cùng, kèm cả hằng số “lấy đại”, như sau:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Cách sửa thuật toán này để được HyperLogLog huyền thoại, tốt nhất trong các thuật toán, sẽ được trình bày lần sau. Còn bây giờ, ta xem thuật toán cần bao nhiêu bộ nhớ.
Bộ nhớ cần dùng
Thuật toán rất tiết kiệm bộ nhớ. Thứ duy nhất cần nhớ là mảng lưu các giá trị lớn nhất. Độ dài của mảng này phụ thuộc vào giá trị k, tức là số bit của vectơ dùng làm chỉ số nhóm. Với k đã cho, có tất cả 2k nhóm khác nhau, nên mảng các giá trị lớn nhất có độ dài 2k. Trong cài đặt, giá trị này được đặt tên là num_buckets.
Mỗi ô của mảng cần lớn đến đâu? Ta sẽ lưu vào đó độ dài các hậu tố toàn số 0. Có thể nói trước rằng giá trị băm 64 bit có lẽ đủ cho mọi đa tập hợp có thể nghĩ ra trên đời, nên mảng này phải lưu được các số từ 0 (vectơ toàn chữ số 1) đến 64 (vectơ toàn chữ số 0). Hơn nữa, nếu giả sử k luôn lớn hơn 0, thì chỉ cần lưu các số từ 0 đến 63. Để làm việc đó, xin thưa, chỉ cần 6 bit, vì 26 = 64.
Đúng vậy, ta chỉ cần một “mảng” mà mỗi ô có kích thước 6 bit. Có thể nói thêm rằng giá trị k=10 đủ để ước lượng khá tốt lực lượng lên đến cỡ hàng trăm triệu. Thuật toán với tham số như vậy tạo một mảng kích thước 210 = 1.024, mỗi ô chiếm 6 bit. Tổng cộng mảng chiếm 6.144 bit, tức là 768 byte. Chưa đến một kilobyte.
Và chỉ có thế.
Ta không cần lưu gì khác, các giá trị băm đã tính có thể bỏ đi ngay, chỉ cần biết số chữ số 0 ở cuối vectơ.
Lưu ý rằng nếu dùng hàm băm lớn hơn, chẳng hạn trả về 128 bit, bộ nhớ cần dùng cũng không thay đổi nhiều. Khi đó ta cần lưu các số từ 0 đến 127, chỉ cần 7 bit. Như vậy, bộ nhớ cần dùng chủ yếu phụ thuộc vào tham số k, tức là số nhóm.
LogLog đặc biệt phù hợp khi cần đếm các đa tập hợp có lực lượng thực sự lớn. Như đã thấy ở ví dụ đơn giản phía trên, LogLog xử lí không thật tốt các đa tập hợp có lực lượng nhỏ. Tuy nhiên, điều này cũng có thể khắc phục, chẳng hạn: nếu thấy đa tập hợp có lực lượng nhỏ, ta dùng một thuật toán khác để ước lượng, chẳng hạn Linear Counting đã mô tả trước đây. Điều này cũng sẽ được bàn đến lần sau.
Tài liệu tham khảo:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (mã nguồn LogLog ở đây ít nhiều lấy từ bài này)
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