LogLog: Cara menganggar bilangan nilai unik
Selepas bahagian sebelum ini tentang Linear Counting dan Min Value, akhirnya kita sampai kepada algoritma berkebarangkalian yang hampir terbaik untuk menganggar bilangan nilai unik dalam suatu set data, iaitu LogLog. Yang lebih baik daripadanya hanyalah adiknya, HyperLogLog, yang dibina berdasarkan LogLog, tetapi itu akan dibincangkan dalam bahagian seterusnya.
Mari kita ulang semula masalahnya. Input kita ialah suatu set data atau multiset, contohnya tatasusunan atau penjana ID. Sesetengah nilai dalam tatasusunan ini muncul beberapa kali, dan kita mahu mengira bilangan nilai unik dalam tatasusunan itu. Bilangan ini kita panggil kekardinalan. Kita menjangkakan bahawa kekardinalan ini sangat besar; jika tidak, kita boleh menggunakan algoritma konvensional.
Idea algoritma LogLog
Bayangkan kita mempunyai satu set vektor binari. Jangan risau, contohnya 0001011001001100 ialah vektor binari dengan panjang 16. Katakan kita mempunyai vektor binari dengan panjang 32, dan jumlahnya sejuta, semuanya dijana secara rawak sepenuhnya. Berapakah bilangan vektor yang berakhir dengan digit sifar?
Sudah tentu kita tidak dapat mengetahuinya dengan tepat, tetapi jika vektor itu benar-benar dijana secara rawak, lebih kurang separuh daripadanya sepatutnya berakhir dengan sifar, iaitu 500 ribu. Berapakah vektor yang berakhir dengan 00? Satu perempat. Dengan 000? Satu perlapan. Dan begitulah seterusnya. Hal ini boleh digambarkan lebih kurang seperti berikut:
corak vektor bahagian daripada semua vektor
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12.5%
...xxx0000 6.25%
... ...
Jika kita mencari akhiran (suffix, iaitu rentetan yang menjadi penghujung rentetan lain — lawan bagi awalan) dengan panjang d, kita menjangkakan akan menemui v vektor yang berakhir dengan akhiran ini. Nilai v dikira sebagai:
dengan N ialah bilangan semua vektor dalam set itu. Akhiran dengan panjang 3 (contohnya …010) sepatutnya muncul dalam 1/2^3 N = 1/8 N vektor, iaitu 12.5% daripada semua vektor.
Sekarang mari kita lakukan sedikit helah minda. Katakan kita mempunyai multiset yang terdiri daripada 1024 vektor unik. Berapakah bilangan vektor yang sepatutnya berakhir dengan akhiran 0000000000 (sepuluh sifar)? Kita gantikan ke dalam rumus dan memperoleh
Wah, satu! Dalam seribu vektor binari yang dijana secara rawak, sepatutnya terdapat tepat satu vektor yang berakhir dengan sepuluh sifar. Bagaimanakah maklumat ini boleh digunakan untuk menganggar bilangan unsur unik? Kita boleh berfikir secara terbalik. Bagaimana jika kita meneliti semua vektor binari dalam input dan mendapati bahawa set itu mengandungi hanya satu vektor yang berakhir dengan sepuluh sifar? Maka kita boleh menganggarkan bahawa set itu mengandungi 1024 vektor!
Mengitlakkan dan membina algoritma
Matlamatnya ialah mencari akhiran yang terkandung dalam satu vektor sahaja, dan akhiran itu sependek mungkin. Namun, hal ini sangat sukar dilakukan kerana untuk benar-benar menemui vektor sebegini, kita perlu menyimpan semua akhiran, dan kita tidak mahu berbuat demikian kerana terlalu banyak ingatan akan digunakan. Sebaliknya, kita berpuas hati dengan mencari jujukan sifar yang paling panjang di hujung vektor.
Jadi, kita meneliti semua vektor, mengira bilangan sifar di hujung setiap vektor, dan menyimpan nilai maksimum dalam satu pemboleh ubah. Selepas meneliti semua vektor, kita mengetahui panjang akhiran terpanjang yang terdiri daripada sifar sahaja. Panjang ini ditandakan dengan huruf d. Sekarang kita ubah rumus tadi untuk menjadikan N sebagai perkara rumus, supaya N menjadi output algoritma, bukan input. Pada masa yang sama, v boleh digantikan dengan satu kerana kita menjangkakan akan menemui tepat satu vektor sebegini, iaitu kita menjangkakan v=1.
Jadi, jika kita menemui panjang d bagi akhiran sifar yang terpanjang, kita menganggar kekardinalan dengan rumus N=2d.
Bagaimanakah kita memperoleh vektor binari rawak?
Dengan vektor binari rawak, algoritma kita sudah berfungsi, tetapi bagaimanakah kaedah ini digunakan pada data sebenar? Seperti biasa, di sini juga kita menggunakan fungsi cincang yang sesuai. Jika input kita ialah set data, contohnya ID (rentetan), kita mencincangnya terlebih dahulu. Output fungsi cincang n-bit ialah n bit yang, dari sudut praktikal, kelihatan seperti vektor binari yang dijana secara rawak.
Pada ketika ini kita boleh menulis algoritma kita:
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
Fungsi trailing_zeroes memulangkan bilangan sifar di hujung suatu nombor. Bagaimanakah fungsi ini melakukannya? Jika anda tidak memahaminya daripada kod, lebih baik jangan tanya. Dan sejauh manakah kejayaan fungsi ini? Bagi set yang mengandungi seratus ribu unsur unik, fungsi itu memberikan anggaran 524 288.
Hmm…
Hasil itu memang tidak begitu baik, bukan? Tetapi tidak mengapa! Kita cuba memperbaiki algoritma ini dengan cara yang sama seperti Min Value sebelum ini. Kita membahagikan data input kepada beberapa kumpulan yang tidak bertindih, mengira akhiran sifar maksimum bagi setiap kumpulan, dan akhirnya mengira min panjang akhiran sifar itu dan menggunakannya untuk menganggar bilangan nilai unik.
Contohnya, kita boleh menetapkan bahawa dua bit terakhir setiap vektor menentukan nombor kumpulan vektor itu. Enam vektor berikut
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
boleh dibahagikan kepada empat kumpulan mengikut penghujungnya:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Seterusnya kita mengira panjang akhiran sifar yang terpanjang dalam setiap vektor, tetapi kita melangkau bit yang digunakan sebagai nombor kumpulan. “Akhiran” sifar ditandakan dengan warna hijau:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Di bahagian bawah tertera panjang akhiran sifar yang terpanjang bagi setiap kumpulan. Daripada panjang ini kita boleh mengira min aritmetik, iaitu 2.75. Kita gantikan nilai ini ke dalam rumus dan memperoleh
Nilai ini ialah min bilangan unsur unik dalam setiap kumpulan. Sudah tentu nilai ini langsung tidak betul, tetapi jangan risau, bagi set yang kecil algoritma LogLog memberikan hasil yang teruk.
Untuk menganggar kekardinalan keseluruhan set, kita masih perlu mendarabkan nilai ini dengan bilangan kumpulan: 6.727 · 4 = 26.908. Algoritma ini mengira bahawa set itu mengandungi lebih kurang 27 nilai unik. Sebenarnya hanya ada enam, jadi anggaran ini langsung tersasar, tetapi hal itu memang tidak penting sekarang.
Pelaksanaan algoritma
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
Parameter k menentukan bilangan bit yang diambil sebagai indeks kumpulan. Parameter ini menentukan ketepatan algoritma — semakin tinggi k, semakin tinggi ketepatannya. Pemboleh ubah bucket_index menyimpan nombor kumpulan. Bagaimanakah “sihir” di sebelah kanan tanda sama dengan itu berfungsi?
Pemboleh ubah num_buckets menyimpan bilangan kumpulan, yang sentiasa merupakan kuasa bagi dua. Contohnya, jika k = 3, maka num_buckets=8. Nombor 8 dalam asas dua ialah 1000. Jika kita menolak satu, kita memperoleh nombor 7, iaitu 0111. Selepas menolak satu daripada num_buckets, kita sentiasa memperoleh nombor yang mempunyai k digit satu di hujung dan sifar sahaja sebelumnya. Kemudian kita melakukan operasi AND bit demi bit (iaitu pengendali &). Bagi vektor 1110110010100101, operasi ini kelihatan seperti berikut:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Tujuan “sihir” ini ialah memperoleh nombor yang bermula dengan sifar sahaja dan k bit terakhirnya sama dengan nilai cincang h.
Seterusnya kita mengira bucket_hash, iaitu nilai cincang asal yang k bit terakhirnya dibuang dengan menganjakkan keseluruhan nilai cincang sebanyak k bit ke kanan. Anjakan ini hanya menggerakkan semua bit dalam nombor sebanyak k bit ke kanan, dan nombor itu diisi dengan sifar dari kiri. (Anjakan bit ke kanan sebanyak satu sama seperti membahagikan nombor dengan dua dan membuang bakinya.) Daripada vektor 1110110010100101, selepas anjakan sebanyak tiga kita memperoleh 0001110110010100. Vektor ini disimpan dalam pemboleh ubah bucket_hash.
Kemudian kita mengira bilangan sifar di hujung vektor ini, dan jika nilai ini lebih besar daripada nilai maksimum semasa yang disimpan dalam tatasusunan max_zeroes pada indeks bucket_index, kita menggantikan nilai itu.
Akhirnya kita hanya mengira min bilangan sifar bagi semua kumpulan dan mengira min bilangan unsur unik dalam setiap kumpulan (2 ** average_max_zeros). Oleh sebab terdapat num_buckets kumpulan kesemuanya, kita mendarabkan nilai ini dengan bilangan kumpulan dan memperoleh anggaran akhir bilangan unsur unik. Fuh, tidaklah sesakit mana. Hasil bagi beberapa set data yang mengandungi 250 000 nilai unik dan k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Tidaaak, masih salah :-(. Namun, kita sudah agak hampir, jangan risau. Perhatikan bahawa semua hasil lebih besar daripada hasil yang betul. Sepanjang algoritma berjalan, pelbagai ralat terkumpul, dan oleh itu anggarannya jelas lebih besar daripada hasil yang betul. Namun, ralat ini agak tetap, dan saiznya boleh dianggarkan. Jika anggaran itu didarab dengan pemalar pembetulan 0.79402, kita memperoleh hasil yang jauh lebih baik:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Saya juga mencuba multiset dengan kekardinalan sejuta, dan hasilnya:
Hasil Ralat
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Bagus sekali! Ralatnya di bawah 2.5%, dan itu prestasi yang baik. Tuan-tuan dan puan-puan, inilah algoritma LogLog. Pelaksanaan akhir dengan pemalar pembetulan itu kelihatan seperti berikut:
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
Cara mengubah suai algoritma ini untuk memperoleh HyperLogLog yang terkenal dan terbaik itu akan dibincangkan dalam bahagian seterusnya. Buat masa ini, mari kita lihat keperluan ingatan algoritma ini.
Keperluan ingatan
Algoritma ini sangat cekap dari segi ingatan yang digunakan. Satu-satunya perkara yang perlu kita ingat ialah tatasusunan yang menyimpan nilai maksimum. Panjang tatasusunan ini bergantung pada nilai k, iaitu bilangan bit daripada vektor yang diambil sebagai indeks kumpulan. Bagi nilai k tertentu, terdapat 2k kumpulan yang berbeza, jadi panjang tatasusunan nilai maksimum ialah 2k. Dalam pelaksanaan, nilai ini dinamakan num_buckets.
Berapakah saiz satu sel tatasusunan? Kita menyimpan panjang akhiran sifar di dalamnya. Saya boleh memberitahu anda terlebih dahulu bahawa nilai cincang 64-bit mungkin mencukupi bagi semua multiset yang dapat dibayangkan di dunia ini, jadi tatasusunan ini mesti dapat menyimpan nombor dari 0 (vektor yang terdiri daripada digit satu sahaja) hingga 64 (vektor yang terdiri daripada sifar sahaja). Tambahan pula, jika kita menganggap bahawa k sentiasa lebih besar daripada sifar, kita hanya perlu menyimpan nombor dari 0 hingga 63. Untuk itu, cukup 6 bit sahaja kerana 26 = 64.
Ya, kita hanya memerlukan “tatasusunan” yang setiap selnya bersaiz 6 bit. Saya juga boleh memberitahu anda bahawa nilai k=10 sudah cukup untuk menganggar kekardinalan dengan agak baik sehingga ratusan juta. Algoritma dengan tetapan ini membina tatasusunan bersaiz 210 = 1024, dan setiap sel menggunakan 6 bit. Secara keseluruhan, tatasusunan ini menggunakan 6144 bit, iaitu 768 bait. Kurang daripada satu kilobait.
Itu sahaja.
Kita tidak perlu menyimpan apa-apa lagi; nilai cincang yang dikira boleh terus dibuang, dan kita hanya perlu mengetahui bilangan sifar di hujung vektor.
Perhatikan bahawa jika anda menggunakan fungsi cincang yang lebih besar, misalnya yang memulangkan 128 bit, keperluan ingatan tidak banyak berubah. Kita perlu menyimpan nombor dari 0 hingga 127, dan untuk itu cukup 7 bit. Jadi, keperluan ingatan terutamanya ditentukan oleh parameter k, iaitu bilangan kumpulan.
LogLog paling sesuai apabila kita perlu mengira multiset yang kekardinalannya benar-benar besar. Seperti yang dilihat dalam contoh mudah di atas, LogLog kurang berkesan bagi multiset yang kekardinalannya kecil. Masalah ini boleh diatasi, misalnya, dengan menggunakan algoritma lain untuk anggaran apabila kita mendapati bahawa multiset itu mempunyai kekardinalan yang rendah, contohnya Linear Counting yang telah diterangkan sebelum ini. Hal ini juga akan dibincangkan dalam bahagian seterusnya.
Sumber:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (kod LogLog lebih kurang diambil dari sini)
Kandungan: Linear counting: Cara menganggar bilangan nilai unik, Min Value: Cara menganggar bilangan nilai unik, LogLog: Cara menganggar bilangan nilai unik, HyperLogLog: Cara menganggar bilangan nilai unik dengan sangat tepat