Apa keuntungan menggunakan filter mekar?

Dari Wikipedia:

Filter Bloom memiliki keunggulan ruang yang kuat dibandingkan struktur data lainnya untuk mewakili kumpulan, seperti pohon pencarian biner yang menyeimbangkan diri, percobaan, tabel hash, atau array sederhana atau daftar entri yang ditautkan. Sebagian besar memerlukan penyimpanan setidaknya item data itu sendiri, yang dapat memerlukan sejumlah kecil bit, untuk bilangan bulat kecil, hingga jumlah bit yang berubah-ubah, seperti untuk string (percobaan adalah pengecualian, karena mereka dapat berbagi penyimpanan antar elemen dengan awalan yang sama). Struktur tertaut memerlukan ruang linier tambahan untuk penunjuk. Sebaliknya, filter Bloom dengan kesalahan 1% dan nilai k optimal hanya memerlukan sekitar 9,6 bit per elemen — berapa pun ukuran elemennya. Keuntungan ini sebagian berasal dari kekompakannya, yang diwarisi dari susunan, dan sebagian lagi dari sifat probabilistiknya. Jika tingkat positif palsu 1% tampaknya terlalu tinggi, setiap kali kita menambahkan sekitar 4,8 bit per elemen, kita menguranginya sepuluh kali lipat.

Cukup jelas bagi saya.

Filter mekar tidak menyimpan elemen itu sendiri, ini adalah poin krusialnya. Anda tidak menggunakan filter mekar untuk menguji apakah suatu elemen ada, Anda menggunakannya untuk menguji apakah elemen tersebut pasti tidak ada, karena ini menjamin tidak ada negatif palsu. Ini memungkinkan Anda tidak melakukan pekerjaan ekstra untuk elemen yang tidak ada dalam satu set (seperti disk IO untuk mencarinya).

Dan semuanya dalam ruang yang jauh lebih sedikit daripada sesuatu seperti tabel hash (yang kemungkinan besar akan ada sebagian di disk untuk kumpulan data besar). Meskipun Anda dapat menggunakan filter mekar bersama dengan struktur seperti tabel hash, setelah Anda yakin elemen tersebut memiliki peluang untuk ada.

Jadi contoh pola penggunaannya mungkin:

Anda memiliki banyak data di disk -- Anda memutuskan batas kesalahan apa yang Anda inginkan (misalnya 1%), yang menentukan nilai m. Kemudian k optimal ditentukan (dari rumus yang diberikan di artikel). Anda mengisi filter dari data terikat disk ini satu kali.

Sekarang Anda memiliki filter di RAM. Saat Anda perlu memproses beberapa elemen, Anda menanyakan filter Anda untuk melihat apakah elemen tersebut memiliki peluang untuk ada di kumpulan data Anda. Jika tidak, tidak ada pekerjaan tambahan yang dilakukan. Tidak ada disk yang terbaca, dll. (Yang harus Anda lakukan jika itu adalah hash atau pohon, dll).

Jika tidak, jika filter mengatakan "Ya, ada di sana", ada kemungkinan 1% bahwa itu salah, jadi Anda melakukan upaya yang diperlukan untuk mengetahuinya. 99% dari waktu, hal itu benar-benar akan ada di sana, jadi pekerjaan ini tidak sia-sia.

Alex telah menjelaskannya dengan cukup baik. Bagi yang masih belum begitu paham, semoga contoh ini dapat membantu Anda memahami:

Katakanlah saya bekerja untuk Google, di tim Chrome, dan saya ingin menambahkan fitur ke browser yang memberi tahu pengguna jika url yang dia masukkan adalah URL berbahaya. Jadi saya memiliki kumpulan data sekitar 1 juta URL berbahaya, ukuran file ini sekitar 25 MB. Karena ukurannya cukup besar (besar dibandingkan ukuran browser itu sendiri), saya menyimpan data ini di server jauh.

Kasus 1 : Saya menggunakan fungsi hash dengan tabel hash. Saya memutuskan fungsi hashing yang efisien, dan menjalankan 1 juta url melalui fungsi hashing untuk mendapatkan kunci hash. Saya kemudian membuat tabel hash (array), di mana kunci hash akan memberi saya indeks untuk menempatkan URL itu. Jadi sekarang setelah saya melakukan hashing dan mengisi tabel hashing, saya memeriksa ukurannya. Saya telah menyimpan 1 juta URL di tabel hash beserta kuncinya. Jadi ukurannya minimal 25 MB. Tabel hash ini, karena ukurannya akan disimpan di server jauh. Saat pengguna datang dan memasukkan URL di bilah alamat, saya perlu memeriksa apakah itu berbahaya. Jadi saya menjalankan URL melalui fungsi hash (browser itu sendiri dapat melakukan ini) dan saya mendapatkan kunci hash untuk URL itu. Saya sekarang harus membuat permintaan ke server jauh saya dengan kunci hash itu, untuk memeriksa apakah URL tertentu di tabel hash saya dengan kunci tertentu itu, sama dengan yang dimasukkan pengguna. Jika ya maka itu berbahaya dan jika tidak maka itu tidak berbahaya. Jadi, setiap kali pengguna memasukkan URL, permintaan ke server jarak jauh harus dibuat untuk memeriksa apakah URL tersebut berbahaya. Ini akan memakan banyak waktu dan membuat browser saya lambat.

Kasus 2 : Saya menggunakan filter mekar. Seluruh daftar 1 juta URL dijalankan melalui filter mekar menggunakan beberapa fungsi hash dan masing-masing posisi ditandai sebagai 1, dalam sejumlah besar angka 0. Katakanlah kita menginginkan tingkat positif palsu sebesar 1%, menggunakan kalkulator filter mekar (http://hur.st/bloomfilter?n=1000000&p=0.01) , kami mendapatkan ukuran filter mekar yang diperlukan hanya 1,13 MB. Ukuran kecil ini diharapkan karena, meskipun ukuran array sangat besar, kita hanya menyimpan 1 atau 0 dan bukan URL seperti pada tabel hash. Array ini dapat diperlakukan sebagai array bit. Artinya, karena kita hanya mempunyai dua nilai 1 dan 0, kita dapat mengatur bit individual, bukan byte. Ini akan mengurangi ruang yang dibutuhkan sebanyak 8 kali lipat. Filter mekar 1,13 MB ini, karena ukurannya yang kecil, dapat disimpan di web browser itu sendiri!! Jadi ketika pengguna datang dan memasukkan URL, kami cukup menerapkan fungsi hash yang diperlukan (di browser itu sendiri), dan memeriksa semua posisi di filter mekar (yang disimpan di browser). Nilai 0 di salah satu posisi memberi tahu kita bahwa URL ini PASTI TIDAK ada dalam daftar URL berbahaya dan pengguna dapat melanjutkan dengan bebas. Jadi kami tidak melakukan panggilan ke server dan karenanya menghemat waktu. Nilai 1 memberi tahu kita bahwa URL tersebut MUNGKIN ada dalam daftar URL berbahaya. Dalam kasus ini kita membuat panggilan ke server jarak jauh dan di sana kita dapat menggunakan beberapa fungsi hash lain dengan beberapa tabel hash seperti pada kasus pertama untuk mengambil dan memeriksa apakah URL tersebut benar-benar ada. Karena sering kali, URL tidak mungkin berbahaya, filter mekar kecil di browser akan mendeteksinya dan karenanya menghemat waktu dengan menghindari panggilan ke server jarak jauh. Hanya dalam beberapa kasus, jika filter mekar memberi tahu kita bahwa URL tersebut MUNGKIN berbahaya, hanya dalam kasus tersebut kita membuat panggilan ke server. 'MUNGKIN' itu 99% benar.

Jadi dengan menggunakan filter mekar kecil di browser, kita menghemat banyak waktu karena tidak perlu melakukan panggilan server untuk setiap URL yang dimasukkan.

Kita dapat melihat bahwa tabel hash dengan fungsi hash tunggal digunakan untuk tujuan yang berbeda dari filter mekar. Semoga ini menghilangkan keraguan Anda :)

sunting:

Saya telah menerapkan filter mekar untuk tugas pengujian URL berbahaya dengan Python. Kodenya dapat ditemukan di sini - https://github.com/tarunsharma1/Bloom-Filter kodenya sangat sederhana untuk dipahami dan penjelasan rinci disediakan di file readme.

Saya akan mulai dengan penjelasan tentang apa itu filter mekar, apa yang bisa dan tidak bisa dilakukan, mengapa kita membutuhkannya, menunjukkan deskripsi intuitif cara kerjanya dan kemudian memberikan beberapa contoh kapan filter tersebut berguna.

Jadi filter mekar standar adalah struktur data probabilistik yang dapat^*:

• menambahkan elemen ke satu set
• periksa apakah suatu elemen ada di set dengan memberi tahu definitely not in the set atau possibly in the set

possibly in the set inilah yang menyebabkan disebut probabilistik. Menggunakan kata-kata cerdas berarti positif palsu mungkin terjadi (ada kasus di mana ia salah mengira bahwa elemennya positif) tetapi negatif palsu tidak mungkin dilakukan.

Namun tidak bisa ^*:

• menghapus item dari set
• memberi Anda daftar semua elemen yang saat ini ada di set Anda

^*_{Kumpulan bisa/tidak bisa ini untuk filter mekar dasar. Karena ini adalah struktur data berguna yang telah dibuat sejak lama, orang menemukan cara tambahkan dengan fitur yang berguna.}

Tapi tunggu dulu: kita sudah mengetahui struktur data yang bisa menjawab semua ini tanpa 'kemungkinan' yang samar-samar dan juga tanpa semua batasan (tidak bisa menghapus, tidak bisa menampilkan semua). Dan itu disebut set. Dan inilah keuntungan utama dari filter mekar: filter ini efisien ruang dan konstan.

Artinya tidak peduli berapa banyak elemen yang kita simpan di sana, ruangnya akan tetap sama. Ya, filter mekar dengan elemen 10^6 (filter mekar yang tidak berguna) akan memakan jumlah ruang yang sama dengan filter mekar dengan elemen 10^20 dan ruang yang sama dengan filter mekar dengan elemen 0. Jadi berapa banyak ruang yang dibutuhkan? Terserah Anda untuk memutuskan (tetapi ada trade-nya: semakin banyak elemen yang Anda miliki, semakin Anda tidak yakin dengan jawaban possible in the set Anda.

Hal keren lainnya adalah ruangnya konstan. Saat Anda menyimpan data ke suatu kumpulan, Anda harus benar-benar menyimpan data ini. Jadi jika Anda menyimpan this long string in the set Anda setidaknya harus menggunakan ruang 27 byte. Namun untuk kesalahan 1% dan nilai optimal k ^**, Anda memerlukan ~ 9,6 bit ( ‹ 2 byte) per elemen apa pun (apakah itu int pendek atau teks berdinding besar) .

Properti lainnya adalah bahwa semua operasi memakan waktu konstan, yang sama sekali tidak sama dengan waktu konstan diamortisasi dalam kasus himpunan (ingat bahwa jika himpunan tersebut bertabrakan, himpunan tersebut dapat memburuk dalam waktu O(n)).

^**_{k adalah nilai fungsi hash yang digunakan dalam filter mekar}

Saya tidak akan menjelaskan cara kerja filter mekar (artikel wikipedia menjelaskan semuanya dengan sangat baik). Di sini saya hanya akan menjelaskan secara singkat dasar-dasarnya.

• Anda memulai array bit kosong dengan panjang m
• Anda memilih k fungsi hash yang berbeda (semakin independen semakin baik)
• jika Anda ingin menambahkan elemen, hitung semua k hash dari nilai ini dan setel bit yang sesuai ke 1
• jika Anda ingin memeriksa apakah elemen ada, Anda juga menghitung semua k hash dan jika setidaknya salah satu dari mereka tidak disetel, pastinya tidak ada di set. Kalau tidak, itu bisa di set.

Bahkan uraian ini cukup untuk memahami mengapa kami tidak dapat memastikannya (Anda bisa mendapatkan semua bit yang ditetapkan dari berbagai nilai lainnya). Berikut adalah visualisasi yang sangat bagus tentang cara kerjanya.

Jadi kapan filter mekar bisa berguna? Jawaban singkatnya adalah di mana saja di mana positif palsu dapat diterima dan di mana Anda ingin memeriksa apakah ada sesuatu yang ada di set, namun bahkan jika tidak, ini bisa menjadi garis pertahanan pertama untuk menyingkirkan biaya mahal panggilan ke verifikator.

Berikut daftar uraian yang lebih konkrit:

• contoh standar situs web dan browser berbahaya dijelaskan di hampir semua tempat tempat orang membicarakan filter mekar
• apakah kata sandinya lemah: alih-alih memiliki sekumpulan besar semua kemungkinan kata sandi yang lemah, Anda dapat memeriksa apakah kata sandi tersebut benar-benar tidak lemah dengan filter mekar yang jauh lebih kecil
• jika Anda memiliki daftar artikel dan daftar pengguna, Anda dapat menggunakan filter mekar untuk menampilkan artikel pengguna yang belum mereka baca. Menariknya Anda hanya dapat memiliki satu filter (Anda memeriksa apakah kombinasi user_id + article_id ada)
• bitcoin menggunakan filter mekar untuk sinkronisasi dompet
• Server web Akamai menggunakan filter Bloom untuk mencegah "one-hit-wonders" disimpan dalam cache disknya. One-hit-wonders adalah objek web yang diminta oleh pengguna sekali saja, sesuatu yang menurut Akamai diterapkan pada hampir tiga perempat infrastruktur cache mereka. Menggunakan filter Bloom untuk mendeteksi permintaan kedua untuk objek web dan menyimpan cache objek tersebut hanya pada permintaan kedua mencegah keajaiban satu pukulan memasuki cache disk, secara signifikan mengurangi beban kerja disk dan meningkatkan tingkat hit cache disk (diambil dari contoh di filter mekar artikel di wiki)

Filter Bloom cukup berguna dalam bioinformatika. Mereka bisa lebih hemat ruang dibandingkan dengan menggunakan hash biasa, terutama ketika ukuran string yang Anda kerjakan bisa ratusan juta huruf dengan alfabet yang sangat kecil yaitu {A,G,T,C} . Mereka biasanya digunakan untuk menilai apakah k-mer tertentu ada atau tidak ada dalam genom. Ada contoh yang digunakan untuk sesuatu yang relevan di sini.

Sunting:

Beberapa fungsi hash digunakan untuk meminimalkan kesalahan positif. Harapannya adalah bahwa di antara semua fungsi k-hash, setiap nilai akan memiliki tanda tangan unik dalam bit-array dibandingkan dengan setiap nilai lainnya yang mungkin. Namun, positif palsu memang ada, namun dapat diminimalkan hingga tingkat yang dapat dikelola. Dengan menggunakan teknik ini, Anda akan melakukan hashing pada elemen secara independen berdasarkan ukurannya. Saat Anda mencarinya, Anda menggunakan setiap fungsi hash dan memeriksa untuk memastikan nilai bitnya semuanya 1.

Bandingkan dengan genom manusia, dimana peningkatan ukuran elemen akan meningkatkan ukuran tabel hash secara signifikan (Ukuran tabel adalah 4*4^k). Ini dengan asumsi Anda menyandikan elemen menggunakan 2 bit/huruf.

Jika filter Bloom mengembalikan bahwa suatu item adalah anggota himpunan, ada kemungkinan positif palsu tertentu. Jika hanya satu fungsi hash yang digunakan untuk menunjukkan keanggotaan dalam himpunan, kemungkinan positif palsu akan lebih tinggi dibandingkan menggunakan beberapa fungsi hash.