Cara Cari Bilangan Unsur dalam Stream Data - monyet

Walaupun penapis Bloom boleh menjejaki objek yang tiba dari strim, ia tidak dapat memberitahu berapa banyak objek di sana. Satu vektor bit diisi oleh yang boleh (bergantung kepada bilangan hash dan kebarangkalian perlanggaran) menyembunyikan bilangan sebenar objek yang telah dihidupkan di alamat yang sama.

Mengetahui nombor objek yang berbeza berguna dalam pelbagai situasi, seperti apabila anda ingin mengetahui berapa banyak pengguna yang berbeza telah melihat halaman laman web tertentu atau bilangan pertanyaan enjin carian yang berbeza. Menyimpan semua elemen dan mencari pendua di antara mereka tidak boleh bekerja dengan berjuta-juta elemen, terutama yang datang dari aliran. Apabila anda ingin mengetahui bilangan objek yang berbeza dalam strim, anda masih perlu bergantung pada fungsi hash, tetapi pendekatan itu melibatkan mengambil lakaran berangka.

Sketching bermaksud mengambil perkiraan, itu adalah nilai yang tidak jelas tetapi tidak benar sepenuhnya sebagai jawapan. Penghampiran boleh diterima kerana nilai sebenar tidak terlalu jauh daripadanya. Dalam algoritma pintar ini, HyperLogLog, yang berdasarkan kebarangkalian dan penghampiran, anda melihat ciri-ciri nombor yang dihasilkan dari strim. HyperLogLog berasal daripada kajian saintis komputer Nigel Martin dan Philippe Flajolet. Flajolet meningkatkan algoritma awal mereka, Flajolet-Martin (atau algoritma LogLog), ke dalam versi HyperLogLog yang lebih mantap, yang berfungsi seperti ini:

1. Hash menukarkan setiap elemen yang diterima daripada strim itu ke dalam satu nombor.
2. Algoritma tersebut menukar nombor ke dalam binari, asas 2 numerik asas yang digunakan oleh komputer.
3. Algoritma mengira bilangan nol awal dalam nombor perduaan dan trek bilangan maksimum yang dilihatnya, iaitu n.
4. Algoritma menganggarkan bilangan elemen berbeza yang diluluskan dalam aliran menggunakan n. Bilangan unsur yang berbeza adalah 2 ^ n.

Sebagai contoh, elemen pertama dalam rentetan adalah perkataan anjing. Algoritma ini mempunyai nilai integer dan menukarkannya kepada binari, dengan hasil 01101010. Hanya satu sifar muncul pada permulaan nombor tersebut, jadi algoritma merekodkannya sebagai bilangan maksimal sifir trailing yang dilihat. Algoritma kemudiannya melihat perkataan burung beo dan serigala, yang bersamaan binarinya adalah 11101011 dan 01101110, meninggalkan n tidak berubah. Walau bagaimanapun, apabila perkataan cat pass, output adalah 00101110, jadi n menjadi 2. Untuk menganggarkan bilangan elemen yang berbeza, algoritma mengira 2 ^ n, iaitu 2 ^ 2 = 4. Angka ini menunjukkan proses ini.

Mengira hanya sifar utama.

Kiat algoritma adalah bahawa jika hash anda menghasilkan hasil rawak, sama rata (seperti dalam penapis Bloom), dengan melihat perwakilan binari, anda boleh mengira kebarangkalian bahawa urutan nol muncul. Kerana kebarangkalian nombor binari tunggal menjadi 0 adalah satu dua, untuk mengira kebarangkalian urutan nol, anda hanya membiakkan kemungkinan kebarangkalian 1/2 sebanyak panjang jujukan nol:

• 50 peratus (1/2) kebarangkalian untuk angka yang bermula dengan 0
• 25 peratus (1/2 * 1/2) kebarangkalian untuk nombor bermula dengan 00
• 12. Kebarangkalian 5 peratus (1/2 * 1/2 * 1/2) untuk nombor yang bermula dengan 000
• (1/2) ^ k kebarangkalian untuk nombor bermula dengan k zeros (anda menggunakan kuasa untuk pengiraan lebih cepat dari banyak perkalian nombor yang sama)

Semakin sedikit bilangan yang dilihat oleh HyperLogLog, semakin besar ketidaktepatannya. Ketepatan meningkat apabila anda menggunakan pengiraan HyperLogLog berkali-kali dengan menggunakan fungsi hash yang berbeza dan purata bersama-sama jawapan dari setiap pengiraan, tetapi hashing banyak kali mengambil masa, dan aliran cepat. Sebagai alternatif, anda boleh menggunakan hash yang sama tetapi bahagikan aliran ke dalam kumpulan (seperti dengan memisahkan unsur-unsur ke dalam kumpulan ketika mereka tiba berdasarkan perintah kedatangan mereka) dan untuk setiap kumpulan, anda menjejaki bilangan maksimal sifir trailing. Pada akhirnya, anda mengira anggaran unsur yang berbeza bagi setiap kumpulan dan mengira purata aritmetik bagi semua anggaran. Pendekatan ini adalah purata stokastik dan menyediakan anggaran yang lebih tepat daripada menggunakan algoritma ke keseluruhan aliran.