Linear counting: Cara menganggar bilangan nilai unik

Bagaimanakah kita boleh mengira bilangan nilai unik dalam suatu set data jika data itu benar-benar banyak? Contohnya, kita mungkin mempunyai perkhidmatan yang mengukur bilangan pengguna unik di sebuah laman web yang besar, atau malah di seluruh domain .my/.com/.apa-apa sahaja.

Kaedah naif

Baiklah, tiada apa-apa yang sukar: kita hanya meneliti data dan menyimpan setiap nilai tepat sekali dalam struktur data yang sesuai. Dalam Python, kita boleh menulisnya lebih kurang begini (kod ini sengaja ditulis panjang lebar):

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

Kod ini berfungsi. Baiklah, tetapi bagaimana jika data itu ialah pengecam unik v4 sepanjang 36 aksara, dan bagaimana jika terdapat, misalnya, sepuluh juta ID unik? Program itu masih mengira nilai yang betul, tetapi berapakah ingatan yang digunakannya? Kita boleh cuba mengiranya. Untuk memudahkan, kita andaikan bahawa uuid memang disimpan sebagai rentetan 36 aksara. Satu uuid menggunakan 36 bait, jadi sepuluh juta ID menggunakan 360 MB.

Akuilah, jumlah itu tidak sedikit. Jika terdapat seratus juta ID unik, ingatan yang digunakan sudah mencecah gigabait. Itu pun kita hanya mengira ruang yang digunakan oleh data semata-mata. Tambahkan overhed yang digunakan oleh, misalnya, Python/JavaScript, dan anda boleh mencecah gigabait walaupun dengan sepuluh juta ID:

Anda tidak mahu keadaan ini. Bagaimanakah kita boleh mengatasinya?

Kita boleh cuba menyimpan ID itu sendiri dengan lebih cekap, atau menggunakan C dan bukannya Python, yang akan mengurangkan keperluan ingatan dengan ketara, tetapi hasilnya masih kurang memuaskan dan program itu masih menggunakan ruang yang sangat besar. Jadi, kita perlu bertanya: adakah kita benar-benar perlu tahu dengan tepat sama ada bilangan nilai unik itu ialah 9 563 618? Adakah apa-apa yang akan berlaku jika kita bekerja dengan bilangan 9 547 666? Jika jawapan anda ialah ya dan anda mahukan nilai tepat, terpulanglah. Jika tidak, mari kita lihat kaedah untuk menganggar bilangan nilai unik dalam set data dengan setepat mungkin, sepantas mungkin dan dengan keperluan ingatan yang minimum.

Fungsi cincang — penyelamat kita

Kita mempertimbangkan fungsi cincang (hash function) yang menerima rentetan sebagai input dan memulangkan nombor n-bit sebagai output. Jika anda lebih biasa dengan fungsi cincang yang “memulangkan rentetan”, bayangkan sahaja bahawa rentetan itu kemudiannya ditukarkan kepada nombor; tiada apa-apa yang rumit di situ. Bilangan bit menentukan saiz nombor itu. Fungsi 8-bit memulangkan nombor yang menggunakan lapan bit, dan lapan bit boleh menyimpan 2⁸ nilai yang berbeza, lazimnya integer dari 0 hingga 255. Seterusnya kita menggunakan fungsi cincang 24-bit. Fungsi sebegini memulangkan 2²⁴ nilai yang berbeza, iaitu 16 777 216.

Daripada menyimpan nilai itu sendiri, kita menyimpan nilai cincang 24-bit baginya. Untuk menyimpan sepuluh juta nilai cincang 24-bit, kita memerlukan 30 MB. Jumlah ini kira-kira satu per sepuluh daripada 360 MB tadi. Kodnya boleh kelihatan seperti berikut:

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

Fungsi hash ialah fungsi terbina dalam Python yang memulangkan integer, manakala fungsi nhash menunjukkan pelaksanaan naif bagi fungsi cincang n-bit. Tidak penting untuk memahami cara fungsi itu berfungsi kerana fungsi itu sebenarnya tidak berfungsi dengan betul — hasilnya tidak menggunakan 24 bit — tetapi hal itu tidak penting sekarang; yang saya mahu tunjukkan ialah prinsipnya.

Kemudian terdapat fungsi count_unique_using_nhash yang mengira nilai unik. Fungsi ini meneliti semua nilai, mengira nilai cincang setiap satu dan menyimpannya dalam pemboleh ubah found jika nilai itu belum ada di situ.

Masalah kaedah ini ialah fungsi cincang boleh memulangkan checksum yang sama bagi rentetan yang berbeza — perlanggaran (collision) boleh berlaku. Semakin banyak perlanggaran yang berlaku, semakin kurang tepat hasil yang kita peroleh. Fungsi count_unique_using_nhash hampir selalu memulangkan bilangan nilai unik yang lebih kecil daripada bilangan sebenar.

Fungsi cincang manakah yang patut dipilih? Hal ini tidaklah begitu penting, tetapi secara umumnya disyorkan salah satu varian MurmurHash.

Peta bit

Adakah anda memberi perhatian semasa belajar asas pengaturcaraan dalam bahasa C? Jika ya, anda tentu mengenali peta bit (bitmap). Bagaimanakah peta bit boleh digunakan di sini?

Kita gambarkan ideanya dengan tatasusunan. Sebenarnya kita tidak perlu menyimpan checksum yang dikira; kita boleh membina tatasusunan sepanjang 2²⁴ dan memulakan semua unsurnya dengan sifar. Kemudian, apabila kita menemui suatu checksum — yang merupakan nombor! — kita menulis digit satu dalam tatasusunan ini pada indeks checksum untuk menandakan bahawa checksum ini sudah ditemui. Bilangan unsur unik kemudiannya lebih kurang sama dengan bilangan digit satu dalam tatasusunan ini. Kodnya boleh kelihatan seperti berikut:

def count_unique_using_array(values):
    # senarai sepanjang 2^24 yang dimulakan dengan sifar sahaja
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Namun, penggunaan tatasusunan dalam kes ini sangat membazirkan ingatan kerana dalam setiap sel kita hanya perlu menyimpan sama ada satu atau sifar. Sebaliknya, kita boleh menggunakan tatasusunan bit. Sebagai penerangan, integer boleh disimpan, misalnya, dalam 32 bit. Jika kita menukarkan nombor 354 kepada asas dua, kita memperoleh 101100010. Oleh itu, nombor 354 disimpan dalam komputer sebagai integer 32-bit seperti berikut (kita abaikan butirannya, ya?):

00000000 00000000 00000001 01100010

Format ini agak menarik dan boleh kita manfaatkan, bukan? Dalam fungsi kita, kita hanya mahu menyimpan satu dan sifar, dan kita baru sahaja mendapati bahawa nombor biasa sebenarnya hanyalah longgokan sifar dan satu (seperti segala-galanya dalam komputer…). Ringkasnya, dengan pengendali bit, kita boleh menyimpan digit satu supaya digit itu benar-benar menggunakan satu bit sahaja.

Kembali kepada fungsi kita yang menggunakan tatasusunan. Jika kita menulisnya semula dengan tatasusunan bit, bagi fungsi cincang 24-bit kita hanya memerlukan tatasusunan bit bersaiz 2²⁴ bit, iaitu 2 MiB. Ini satu peningkatan yang besar!

Jika kita menggunakan fungsi cincang 32-bit yang mempunyai 2³² nilai output yang berbeza, iaitu 4 294 967 296, kita memerlukan tatasusunan bit bersaiz setengah gigabait. Jumlah ini tidak terlalu teruk memandangkan kita boleh mengira nilai unik sehingga berbilion-bilion.

Linear Counting

Saya telah menyebut bahawa apabila menggunakan fungsi cincang, kita hanya memperoleh anggaran bilangan nilai unik. Anggaran ini semakin kurang tepat apabila bilangan nilai unik menghampiri bilangan nilai output yang berbeza bagi fungsi cincang itu. Memang logik bahawa jika kita mempunyai set data yang mengandungi lima bilion nilai unik, kita tidak dapat mengiranya dengan fungsi cincang 24-bit.

Namun, anggaran yang dikira dengan fungsi cincang boleh dijadikan lebih tepat. Untuk itu digunakan idea yang mudah — semakin banyak nilai unik dalam set data, semakin besar kebarangkalian perlanggaran akan berlaku dari semasa ke semasa. (Perlanggaran = dua input berbeza memberikan output yang sama daripada fungsi cincang, iaitu checksum yang sama.) Sekarang kita akan mengira sedikit, jadi kita perkenalkan beberapa pemboleh ubah:

• Kita menggunakan fungsi cincang n-bit h.
• Oleh itu, bilangan semua output yang mungkin bagi fungsi h ialah 2n. Bilangan ini kita tandakan dengan huruf m, iaitu m=2n.
• Tatasusunan bit yang kita gunakan untuk menyimpan checksum yang telah ditemui ditandakan dengan huruf besar A. Panjang tatasusunan A ialah m.
• Selepas algoritma kita meneliti keseluruhan set data, sesetengah nilai dalam tatasusunan bit ialah sifar dan sesetengahnya ialah satu. Kita terutamanya berminat dengan nisbah “bilangan sifar dibahagi dengan panjang tatasusunan”, yang memberikan bahagian relatif sifar dalam tatasusunan bit. Pada mulanya nisbah ini sama dengan 1 kerana tatasusunan dimulakan dengan sifar sahaja. Jika separuh sifar dan separuh satu, nisbahnya sama dengan setengah, dan begitulah seterusnya. Nilai ini kita tandakan dengan Z dan dikira sebagai Z = bilangan sifar / m.

Pada ketika ini, semakin tinggi nilai Z, semakin yakin kita bahawa anggaran bilangan nilai unik kita tepat. Contohnya, jika kita meneliti set data yang kosong, tatasusunan bit hanya mengandungi sifar dan nilai Z sama dengan satu — jadi kita benar-benar pasti bahawa set data kita mengandungi unsur unik sebanyak bilangan digit satu dalam tatasusunan bit, iaitu sifar.

Jika nilai Z sama dengan 0.99, maksudnya satu perseratus daripada tatasusunan bit diisi dengan digit satu, dan 99% tatasusunan itu mengandungi sifar. Keadaan ini masih baik; berkemungkinan tidak banyak perlanggaran berlaku semasa pengiraan, dan pembetulan yang diperlukan mungkin tiada atau sangat kecil. Namun, jika nilai Z sama dengan 0.05, hanya 5% tatasusunan kekal sifar, dan berkemungkinan kita telah menemui sangat banyak perlanggaran semasa pengiraan — pembetulan yang besar diperlukan.

Bagaimanakah kita mengira pembetulan ini? Kita menggunakan logaritma, iaitu fungsi yang berbentuk seperti berikut:

Kita berminat dengan bahagian merah pada selang (0, 1]. Jika kita meletakkan nilai Z pada paksi-x, semakin tinggi nilai Z, semakin hampir nilai y dengan sifar. Sebaliknya — semakin kecil Z, semakin kecil nilai y. Anggaran akhir dikira dengan mendarabkan nombor ini dengan -m. Perhatikan bahawa bagi nilai Z yang cukup kecil, kita memperoleh nombor yang lebih kecil daripada -1, dan jika nilai ini didarab dengan -m, kita memperoleh anggaran yang lebih besar daripada m: kita menganggarkan bahawa bilangan nilai unik lebih besar daripada bilangan semua checksum yang mungkin dihasilkan oleh fungsi cincang h.

Rumus lengkap untuk mengira bilangan nilai unik p kelihatan seperti berikut:

$$p=-m\cdot \ln Z$$

Pelaksanaannya (tanpa tatasusunan bit, hanya dengan tatasusunan biasa) boleh kelihatan seperti berikut:

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 di sini ialah logaritma jati dengan asas 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)

Dalam fungsi linear_counting, kita mula-mula mengira anggaran pertama dengan algoritma sebelum ini yang menggunakan fungsi cincang n-bit. Kemudian kita mengira bahagian sifar dalam tatasusunan dan membuat pembetulan mengikut rumus. Logaritma dalam kod ialah logaritma jati. Pemboleh ubah nonunique_values mengandungi number_of_unique_values rentetan unik, jadi dalam contoh ini senarai nonunique_values mengandungi sepuluh ribu nilai unik. Kod pelik pada baris keenam memastikan bahawa tatasusunan itu mengandungi nilai berulang: kita hanya menyambungkan senarai nilai yang sama pada hujung senarai, jadi setiap nilai muncul dua kali. Kemudian kita mula mengira. Idealnya, fungsi itu menunjukkan bahawa senarai mengandungi sepuluh ribu nilai unik. Outputnya:

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

Oleh sebab senarai nonunique_values dijana secara berbeza setiap kali, hasilnya akan berbeza bagi setiap panggilan. Kita menggunakan fungsi cincang 16-bit. Kita lihat bahawa anggaran pertama daripada fungsi count_unique_using_array ialah 9289 nilai unik dalam senarai. Melalui pembetulan, anggaran ini menjadi lebih tepat, iaitu 10 017, dan hasil ini sudah agak baik: anggaran kita hanya 0.17% lebih besar, sedangkan sebelum itu anggarannya 7.11% lebih kecil — dan itu agak banyak.

Jika kita mengambil fungsi cincang yang “lebih besar”, misalnya 24-bit, kita memperoleh hasil yang lebih tepat:

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

Anggaran asal sudah memadai, dan pembetulan memberikan tepat sepuluh ribu. Sebagai contoh lain, kita boleh mencuba sejuta ID unik, iaitu number_of_unique_values = 1000000. Dengan fungsi cincang 24-bit, kita memperoleh hasil berikut:

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

Boleh tahan. Lagipun, jika kita melaksanakannya sebagai tatasusunan bit, tatasusunan itu hanya menggunakan dua megabait seperti yang disebut tadi (+ apa yang digunakan oleh bahasa pengaturcaraan). Bagi saya, ini agak bagus. But we can do better! Much better. Tetapi itu dalam bahagian seterusnya.

Sementara itu, anda boleh membaca artikel A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Atau anda boleh terus ke bahagian seterusnya dalam siri ini: algoritma min-value.