Min Value: cara menaksir banyaknya nilai unik

Dalam artikel sebelumnya tentang Linear Counting, kita sudah membahas algoritma dasar untuk menghitung dan menaksir banyaknya nilai unik dalam suatu kumpulan data. Hari ini kita akan membahas algoritma probabilistik lain yang dapat menaksir banyaknya nilai unik dengan akurasi yang cukup baik dan kebutuhan memori yang kecil.

Min Value

Dalam artikel ini, kita hanya bekerja dengan bilangan real dari interval satuan (0, 1). Bayangkan himpunan bilangan dari interval ini yang tersebar merata, misalnya himpunan bilangan {0,25; 0,5; 0,75}. Bilangan-bilangan yang bersebelahan selalu berjarak tepat 0,25 satu sama lain (juga dari nol dan dari satu). Bagaimana hal ini membantu kita menghitung banyaknya elemen unik?

Jika saya katakan bahwa kita punya himpunan bilangan dari interval satuan yang tersebar merata seperti itu, dan jarak antarbilangannya tepat 0,2 — dapatkah kamu menghitung berapa banyak anggota himpunan tersebut? Tentu saja, himpunannya adalah {0,2; 0,4; 0,6; 0,8}, dan kardinalitasnya sama dengan empat. Jika inputnya berupa bilangan dari interval satuan yang tersebar merata dan kita tahu jarak antarbilangan yang bersebelahan, kita dapat dengan mudah menghitung banyaknya anggota.

Jarak antarbilangan yang bersebelahan ternyata sama dengan anggota terkecil himpunan — jarak antaranggota yang bersebelahan dalam himpunan {0,25; 0,5; 0,75} adalah 0,25, dan seterusnya. Jadi, untuk menghitung banyaknya bilangan yang tersebar merata, kita cukup mencari anggota terkecilnya. Setelah itu, banyaknya anggota p dapat dihitung dengan rumus sederhana:

$$p=\frac{1}{m}-1$$

dengan m adalah anggota terkecil tersebut.

Hashing lagi…

Baiklah, tetapi bagaimana memanfaatkannya jika inputnya berupa string atau nilai lain yang tidak memenuhi syarat tersebar merata di interval satuan? Sekali lagi, kita gunakan fungsi hash andalan kita, yang untuk input apa pun dapat mengembalikan bilangan rasional dari interval satuan. Fungsi hash seperti ini mudah dibuat.

Dengan cara ini, dari data kita memperoleh bilangan rasional. Namun, bagaimana agar bilangan-bilangan tersebut tersebar merata? Hal itu memang tidak bisa dijamin, tetapi kita bisa memakai cara lain. Dari sudut pandang kita, fungsi hash berperilaku cukup “acak”. Untuk kata-kata yang sangat mirip, seperti “halo”, “halp”, dan “halq”, fungsi hash kemungkinan besar mengembalikan checksum yang sangat berbeda. Dengan kata lain, jika kita melakukan hashing seribu nilai berbeda ke interval satuan, sangat kecil kemungkinannya sebagian besar bilangan tersebut, misalnya, lebih kecil daripada setengah. Sebaliknya, sangat mungkin bilangan-bilangan tersebut tersebar kurang lebih merata. Makin banyak data yang kita hash, makin merata sebarannya.

Dari ide ini, kita memperoleh algoritma sederhana: telusuri data input, hash setiap elemen ke interval satuan, dan ingat elemen terkecilnya. Banyaknya elemen unik kita taksir dengan rumus sebelumnya. Implementasinya dalam Python:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Fungsi unit_interval_hash mengembalikan bilangan desimal dari interval (0, 1]. Fungsi count_unique_using_minimum mula-mula mengubah semua nilai input menjadi bilangan seperti itu, mencari nilai minimumnya, lalu mengembalikan 1 / minimum - 1. Perhatikan bahwa sama sekali tidak penting berapa banyak nilai yang sama dalam kumpulan data — untuk dua nilai yang sama, fungsi hash mengembalikan bilangan rasional yang sama, sehingga minimum yang dihasilkan tidak berubah. Karena itu, dengan algoritma ini kita menghitung banyaknya elemen yang unik.

Bagaimana hasilnya? (Setiap baris berisi kardinalitas hasil taksiran, sedangkan kardinalitas yang benar adalah 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Hmm, kurang bagus, ya? Algoritma ini menelusuri sepuluh kumpulan ID yang berbeda, masing-masing berisi sepuluh ribu nilai unik. Taksiran yang dihasilkan sebagian besar meleset cukup jauh. Jika dirata-ratakan, kita memperoleh nilai 18.352. Masih cukup jauh meleset, tetapi lihat kebutuhan memorinya — konstan! Untuk mencari minimum, kamu cukup menyimpan satu variabel di memori, yaitu minimum saat ini, dan selesai. Jadi, ya, taksirannya buruk, tetapi biayanya hampir nol.

Perbaikan

Terlihat bahwa masalah utama algoritma ini adalah ketidakstabilan — sekali waktu algoritma mengembalikan taksiran yang cukup baik (9.362), di lain waktu taksirannya meleset jauh (65.536). Bagaimana jalan keluarnya? Kita dapat membagi data input menjadi beberapa bagian, menghitung banyaknya elemen unik untuk setiap bagian, lalu merata-ratakan semuanya. Pembagiannya bisa berdasarkan karakter pertama ID kita. Jadi, kita hitung secara terpisah banyaknya nilai unik untuk ID yang diawali huruf “a”, lalu untuk ID yang diawali huruf “b”, dan seterusnya. Kodenya:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Perubahannya ada pada fungsi count_unique_using_minimum. Dalam variabel min_values, kita menyimpan minimum untuk setiap kelompok. Pada akhirnya, semua minimum kita jumlahkan, lalu kita bagi dengan banyaknya nilai yang tersimpan — hasilnya adalah rata-rata minimum. Dengan ekspresi 1/average_minimum, kita memperoleh rata-rata banyaknya nilai unik di setiap kelompok — nilai ini kemudian kita kalikan dengan banyaknya kelompok, sehingga diperoleh taksiran banyaknya nilai unik dalam kumpulan data yang diberikan. Bagaimana hasil cara yang sudah dimodifikasi ini?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Hmm, masih belum bagus, tetapi jelas lebih baik. Algoritmanya lebih stabil. Kita dapat mencoba mengubah fungsinya sehingga kelompok tidak dibentuk berdasarkan karakter pertama, tetapi misalnya berdasarkan dua karakter pertama ID, seperti ini:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Hasilnya menjadi seperti ini:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nah, ini sudah tidak terlalu buruk, bukan? Jika kita mencoba seratus ribu nilai unik, dua karakter pertama, dan n = 24, kita memperoleh hasil berikut:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Lumayan. Tetapi tenang saja, masih ada algoritma yang lebih baik.

Lalu, berapa kebutuhan memorinya? Kita harus menyimpan minimum untuk setiap kelompok, tidak lebih. Jika ID kita berformat heksadesimal, artinya kita harus mengingat paling banyak 16^x minimum, dengan x banyaknya karakter yang kita gunakan untuk membentuk kunci kelompok. Satu minimum adalah satu bilangan rasional, yaitu bertipe double atau float.

Catatan terakhir: kita bisa membagi input menjadi beberapa kelompok karena input kita berupa ID yang berperilaku seperti string acak. Jika inputnya bukan string acak, melainkan data dengan format tertentu, pembagiannya harus dilakukan dengan cara lain. Misalnya, jika setiap ID diawali prefiks userid-, pembagian kelompok berdasarkan karakter pertama tentu tidak akan berhasil, bukan?