Linear counting: cara menaksir banyaknya nilai unik

Bagaimana kita menghitung banyaknya nilai unik dalam suatu kumpulan data jika datanya benar-benar sangat banyak? Misalnya, kita punya layanan yang mengukur banyaknya pengguna unik pada suatu situs web besar, atau bahkan pada seluruh domain .id/.com/.whatever, atau semacamnya.

Cara naif

Oke, sebenarnya tidak ada yang perlu dipusingkan: kita cukup menelusuri data dan menyimpan setiap nilai tepat satu kali dalam struktur data yang sesuai. Dalam Python, kodenya kira-kira seperti ini (kodenya sengaja dibuat bertele-tele):

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

Berhasil. Baiklah, tetapi bagaimana jika datanya berupa pengenal unik v4 sepanjang 36 karakter dan banyaknya ID unik tersebut, misalnya, sepuluh juta? Hmm… program tetap menghitung nilai yang benar, tetapi berapa banyak memori yang dipakai? Kita bisa mencoba menghitungnya. Supaya sederhana, kita asumsikan bahwa uuid memang disimpan sebagai string 36 karakter. Satu uuid memakai 36 byte, sehingga sepuluh juta ID memakai 360 MB.

Harus diakui, itu tidak sedikit. Jika banyaknya ID unik seratus juta, memori yang terpakai sudah mencapai orde gigabyte. Itu pun kita baru menghitung memori untuk datanya saja. Tambahkan overhead yang dipakai, misalnya, oleh Python/JavaScript, dan dengan sepuluh juta ID pun kamu bisa sampai ke orde gigabyte:

Kamu tentu tidak menginginkannya. Bagaimana jalan keluarnya?

Kita bisa mencoba menyimpan ID-ID tersebut dengan lebih efisien, atau menggunakan bahasa C alih-alih Python sehingga kebutuhan memori turun drastis. Namun, hasilnya tetap belum memuaskan, dan program seperti itu tetap memakai ruang yang luar biasa besar. Tinggal satu pertanyaan: apakah kita benar-benar perlu tahu persis bahwa banyaknya nilai unik adalah 9.563.618? Apakah akan terjadi sesuatu jika kita bekerja dengan angka 9.547.666? Jika jawabanmu “ya” dan kamu ingin hasil yang persis, silakan saja. Jika tidak, mari kita lihat cara-cara untuk menaksir banyaknya nilai unik dalam suatu kumpulan data seakurat mungkin, secepat mungkin, dan dengan kebutuhan memori seminimal mungkin.

Fungsi hash — penyelamat kita

Kita akan menggunakan fungsi hash yang menerima string sebagai input dan mengembalikan bilangan n-bit sebagai output. Jika kamu lebih terbiasa dengan fungsi hash yang “mengembalikan string”, bayangkan saja bahwa string tersebut kemudian diubah lagi menjadi bilangan; tidak ada yang rumit di situ. Banyaknya bit menentukan seberapa besar bilangan tersebut. Fungsi 8-bit mengembalikan bilangan yang memakai delapan bit, dan delapan bit dapat menyimpan 2⁸ nilai yang berbeda, biasanya bilangan bulat dari 0 sampai 255. Selanjutnya, kita akan bekerja dengan fungsi hash 24-bit. Fungsi seperti ini mengembalikan 2²⁴ nilai yang berbeda, yaitu 16.777.216.

Alih-alih menyimpan nilai-nilainya, kita akan menyimpan nilai hash 24-bit dari nilai-nilai tersebut. Untuk menyimpan sepuluh juta nilai hash 24-bit, kita memerlukan 30 MB. Ini sepuluh kali lebih baik daripada 360 MB sebelumnya. Kodenya bisa seperti ini:

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 adalah fungsi bawaan Python yang mengembalikan bilangan bulat, sedangkan fungsi nhash menunjukkan implementasi naif fungsi hash n-bit. Cara kerjanya tidak penting untuk dipahami, karena fungsi ini memang tidak bekerja dengan benar — hasilnya tidak memakai 24 bit. Namun, hal itu tidak penting sekarang; yang ingin saya tunjukkan adalah prinsipnya.

Berikutnya adalah fungsi count_unique_using_nhash, yang menghitung nilai-nilai unik. Fungsi ini menelusuri semua nilai, menghitung nilai hash-nya, lalu menyimpannya ke variabel found jika nilai tersebut belum ada di sana.

Masalah cara ini adalah bahwa fungsi hash dapat mengembalikan checksum yang sama untuk string yang berbeda — bisa terjadi tabrakan (collision). Makin banyak tabrakan yang terjadi, makin tidak akurat hasil yang kita peroleh. Fungsi count_unique_using_nhash hampir selalu mengembalikan banyak nilai unik yang lebih kecil daripada yang sebenarnya.

Lalu, fungsi hash apa yang sebaiknya dipilih? Sebenarnya tidak terlalu penting, tetapi secara umum dianjurkan salah satu varian MurmurHash.

Bitmap

Apakah kamu memperhatikan pelajaran dasar pemrograman dalam bahasa C? Jika ya, kamu tentu mengenal bitmap. Bagaimana bitmap dapat dimanfaatkan?

Idenya akan kita gambarkan dengan larik (array). Kita sebenarnya tidak perlu menyimpan checksum yang sudah dihitung. Kita dapat membuat larik dengan panjang 2²⁴ dan menginisialisasi semua elemennya dengan nol. Kemudian, setiap kali kita menemukan suatu checksum — yang merupakan bilangan! — kita tuliskan angka satu ke larik ini pada indeks checksum. Dengan begitu, kita menandai bahwa checksum ini sudah ditemukan. Banyaknya elemen unik kemudian kira-kira sama dengan banyaknya angka satu dalam larik ini. Kodenya bisa seperti ini:

def count_unique_using_array(values):
    # daftar sepanjang 2^24 yang diinisialisasi dengan nol semua
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Namun, dalam hal ini penggunaan larik sangat boros memori, karena di setiap sel kita hanya perlu menyimpan angka satu atau nol. Sebagai gantinya, kita dapat menggunakan larik bit (bit array). Sebagai gambaran, bilangan bulat (integer) dapat disimpan, misalnya, dalam 32 bit. Jika bilangan 354 kita ubah ke sistem biner, kita memperoleh 101100010. Jadi, di komputer bilangan 354 sebagai integer 32-bit disimpan (detailnya kita abaikan saja, ya?) seperti ini:

00000000 00000000 00000001 01100010

Format ini cukup menyenangkan dan bisa kita manfaatkan, bukan? Dalam fungsi kita, yang ingin kita simpan hanyalah angka satu dan nol, dan barusan kita lihat bahwa bilangan biasa sebenarnya tidak lain adalah tumpukan angka nol dan satu (seperti segala sesuatu di komputer…). Singkatnya, dengan operator bitwise kita dapat menyimpan angka satu sehingga benar-benar hanya memakai satu bit.

Kita kembali ke fungsi kita yang memakai larik. Jika fungsi tersebut kita tulis ulang dengan larik bit, untuk fungsi hash 24-bit kita cukup memerlukan larik bit berukuran 2²⁴ bit, yaitu 2 MiB. Peningkatan yang lumayan!

Dengan fungsi hash 32-bit, yang memiliki 2³² nilai output yang berbeda, yaitu 4.294.967.296, kita memerlukan larik bit berukuran setengah giga. Itu tidak terlalu buruk, mengingat dengan cara ini kita dapat menghitung nilai unik hingga orde miliaran.

Linear Counting

Saya sudah menyebutkan bahwa dengan fungsi hash kita hanya memperoleh taksiran banyaknya nilai unik. Taksiran ini makin tidak akurat jika banyaknya nilai unik makin mendekati banyaknya nilai output berbeda dari fungsi hash. Wajar saja bahwa kumpulan data yang memuat lima miliar nilai unik tidak dapat dihitung dengan fungsi hash 24-bit.

Namun, taksiran yang kita hitung dengan fungsi hash dapat diperbaiki lagi. Idenya sederhana — makin banyak nilai unik dalam kumpulan data, makin besar peluang terjadinya tabrakan seiring waktu. (Tabrakan = dua input berbeda memiliki output fungsi hash yang sama, yaitu checksum yang sama.) Sekarang kita akan sedikit berhitung, jadi kita perkenalkan beberapa variabel:

• Kita bekerja dengan fungsi hash h yang berukuran n bit.
• Banyaknya semua output yang mungkin dari fungsi h sama dengan 2n. Banyaknya ini kita lambangkan dengan huruf m, jadi m=2n.
• Larik bit yang kita gunakan untuk mencatat checksum yang sudah ditemukan kita lambangkan dengan huruf kapital A. Larik A memiliki panjang m.
• Setelah algoritma kita menelusuri seluruh kumpulan data, sebagian nilai dalam larik bit akan bernilai nol dan sebagian bernilai satu. Yang terutama menarik bagi kita adalah rasio “banyaknya nol dibagi panjang larik”, yang menyatakan proporsi relatif nol dalam larik bit. Pada awalnya, rasio ini sama dengan 1, karena larik diinisialisasi dengan nol semua. Jika perbandingannya separuh-separuh, rasionya sama dengan setengah, dan seterusnya. Nilai ini kita lambangkan dengan Z dan kita hitung sebagai Z = banyaknya nol / m.

Pada titik ini berlaku: makin tinggi nilai Z, makin yakin kita bahwa taksiran banyaknya nilai unik akurat. Misalnya, jika kita menelusuri kumpulan data kosong, larik bit tetap berisi nol semua dan nilai Z sama dengan satu — kita benar-benar yakin bahwa kumpulan data kita memuat elemen unik sebanyak angka satu dalam larik bit, yaitu nol.

Jika nilai Z sama dengan 0,99, artinya larik bit terisi angka satu sebanyak seperseratus. 99% larik berisi nol. Ini masih baik; kemungkinan besar selama perhitungan tidak terjadi banyak tabrakan, dan mungkin tidak diperlukan koreksi sama sekali atau hanya sedikit. Namun, jika nilai Z sama dengan 0,05, hanya 5% larik yang tetap bernilai nol, dan kemungkinan besar selama perhitungan kita menemui sangat banyak tabrakan — diperlukan koreksi yang besar.

Lalu, bagaimana menghitung koreksi ini? Kita gunakan logaritma, yaitu fungsi dengan bentuk seperti ini:

Yang menarik bagi kita adalah bagian merah pada interval (0, 1]. Jika nilai Z kita tempatkan pada sumbu x, makin tinggi Z, makin dekat nilai y ke nol. Sebaliknya, makin kecil Z, makin kecil nilai y. Taksiran akhirnya kita hitung dengan mengalikan bilangan ini dengan -m. Perhatikan bahwa untuk nilai Z yang cukup kecil, kita memperoleh bilangan yang bahkan lebih kecil daripada -1, dan jika nilai ini kita kalikan dengan -m, kita memperoleh taksiran yang lebih besar daripada m: kita menaksir bahwa banyaknya nilai unik lebih besar daripada banyaknya semua checksum yang mungkin keluar dari fungsi hash h.

Rumus lengkap untuk menghitung banyaknya nilai unik p adalah sebagai berikut:

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

Implementasinya (tanpa larik bit, hanya dengan larik biasa) bisa seperti ini:

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 adalah logaritma natural dengan basis 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 terlebih dahulu menghitung taksiran pertama dengan algoritma sebelumnya, yang memakai fungsi hash n-bit. Kemudian kita hitung proporsi nol dalam larik dan melakukan koreksi sesuai rumus. Logaritma dalam kode adalah logaritma natural. Variabel nonunique_values memuat string unik sebanyak number_of_unique_values, jadi dalam contoh ini daftar nonunique_values memuat sepuluh ribu nilai unik. Kode aneh pada baris keenam membuat larik berisi banyak nilai yang sama: kita cukup menyambungkan daftar nilai yang sama ke akhir daftar, sehingga setiap nilai muncul dua kali dalam larik. Setelah itu, kita mulai menghitung. Idealnya, fungsi mengembalikan hasil bahwa daftar memuat sepuluh ribu nilai unik. Outputnya:

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

Karena daftar nonunique_values selalu dibangkitkan ulang, hasilnya akan berbeda pada setiap pemanggilan. Kita menggunakan fungsi hash 16-bit. Terlihat bahwa taksiran pertama dari fungsi count_unique_using_array adalah 9.289 nilai unik. Dengan koreksi, taksiran ini kita perbaiki menjadi 10.017, yang sudah cukup bagus: taksiran kita hanya kelebihan 0,17%, sedangkan sebelumnya kekurangan 7,11% — itu cukup banyak.

Jika kita menggunakan fungsi hash yang “lebih besar”, misalnya 24-bit, kita memperoleh hasil yang lebih akurat:

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

Taksiran awalnya saja sudah oke, dan koreksinya menghasilkan tepat sepuluh ribu. Sebagai contoh, kita dapat mencoba satu juta ID unik, yaitu number_of_unique_values = 1000000. Dengan fungsi hash 24-bit, kita memperoleh hasil berikut:

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

Lumayan. Padahal, jika diimplementasikan dengan larik bit, larik tersebut hanya memakan dua megabyte yang tadi disebutkan (ditambah memori yang dipakai bahasa pemrogramannya). Menurut saya, ini cukup bagus. But we can do better! Much better. Tetapi itu di bagian berikutnya.

Sementara itu, kamu dapat membaca artikel A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Atau kamu dapat melanjutkan ke bagian berikutnya dari seri ini: algoritma min-value.