Saya membaca tentang filter mekar dan mereka tampak konyol. Apa pun yang dapat Anda capai dengan filter mekar, Anda dapat menyelesaikannya dalam ruang yang lebih sedikit, lebih efisien, menggunakan satu fungsi hash daripada beberapa, atau begitulah kelihatannya. Mengapa Anda menggunakan filter mekar dan apa manfaatnya?
algorithm
data-structures
bloom-filter
sakit kepala
sumber
sumber
Jawaban:
Dari Wikipedia :
Cukup jelas bagi saya.
Filter mekar tidak menyimpan elemen itu sendiri, ini adalah poin krusial. Anda tidak menggunakan filter mekar untuk menguji apakah suatu elemen ada, Anda menggunakannya untuk menguji apakah itu pasti tidak ada, karena itu menjamin tidak ada negatif palsu. Ini memungkinkan Anda tidak melakukan pekerjaan tambahan untuk elemen yang tidak ada dalam satu set (seperti disk IO untuk mencarinya).
Dan semua dalam ruang yang jauh lebih sedikit daripada sesuatu seperti tabel hash (yang kemungkinan akan sebagian ada di disk untuk kumpulan data besar). Meskipun Anda dapat menggunakan filter mekar dalam hubungannya dengan struktur seperti tabel hash, setelah Anda yakin bahwa elemen tersebut memiliki peluang untuk hadir.
Jadi contoh pola penggunaan mungkin:
Anda memiliki banyak data, di disk - Anda memutuskan batas kesalahan yang Anda inginkan (misalnya 1%), yang menentukan nilai m . Kemudian k optimal ditentukan (dari rumus yang diberikan dalam artikel). Anda mengisi filter Anda dari data terikat disk ini sekali.
Sekarang Anda memiliki filter di RAM. Saat Anda perlu memproses beberapa elemen, Anda menanyakan filter Anda untuk melihat apakah ada 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 tree, dll).
Jika tidak, jika filter mengatakan "Ya, ada di sana", ada 1% kemungkinan kesalahannya, jadi Anda melakukan pekerjaan yang diperlukan untuk mengetahuinya. 99% waktu, itu benar-benar akan ada, jadi pekerjaan itu tidak sia-sia.
sumber
Alex telah menjelaskannya dengan cukup baik. Bagi mereka yang masih kurang memahaminya, semoga contoh ini akan 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 25MB. Karena ukurannya cukup besar (besar dibandingkan dengan 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 semua 1 juta url melalui fungsi hashing untuk mendapatkan kunci hash. Saya kemudian membuat tabel hash (sebuah array), di mana kunci hash akan memberi saya indeks untuk menempatkan URL itu. Jadi sekarang setelah saya melakukan hash dan mengisi tabel hashing, saya memeriksa ukurannya. Saya telah menyimpan semua 1 juta URL di tabel hash bersama dengan 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. Sekarang saya harus membuat permintaan ke server jarak jauh saya dengan kunci hash itu, untuk memeriksa apakah URL tertentu dalam 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 jauh harus dibuat untuk memeriksa apakah itu URL berbahaya. Ini akan memakan banyak waktu dan dengan demikian membuat browser saya lambat.
Kasus 2: Saya menggunakan filter mekar. Seluruh daftar 1 juta URL dijalankan melalui filter bloom menggunakan beberapa fungsi hash dan masing-masing posisinya ditandai sebagai 1, dalam deretan besar 0. Katakanlah kita menginginkan rasio positif palsu 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 larik sangat besar, kita hanya menyimpan 1 atau 0 dan bukan URL seperti pada tabel hash. Larik ini dapat diperlakukan sebagai larik bit. Artinya, karena kita hanya memiliki dua nilai 1 dan 0, kita dapat mengatur bit individual sebagai ganti byte. Ini akan mengurangi ruang yang diambil sebanyak 8 kali. Filter bloom 1,13 MB ini, karena ukurannya yang kecil, dapat disimpan di browser web itu sendiri !! Jadi, saat pengguna datang dan memasukkan URL, kami cukup menerapkan fungsi hash yang diperlukan (di browser itu sendiri), dan memeriksa semua posisi di filter bloom (yang disimpan di browser). Nilai 0 di salah satu posisi memberi tahu kami bahwa URL ini JELAS 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 MUNGKIN ada dalam daftar URL berbahaya. Dalam kasus ini kami membuat panggilan ke server jarak jauh dan di sana kami dapat menggunakan beberapa fungsi hash lainnya dengan beberapa tabel hash seperti pada kasus pertama untuk mengambil dan memeriksa apakah URL benar-benar ada. Karena sebagian besar waktu, URL tidak mungkin berbahaya, filter bloom kecil di browser mengetahui hal itu dan karenanya menghemat waktu dengan menghindari panggilan ke server jarak jauh. Hanya dalam beberapa kasus, jika filter bloom memberi tahu kami bahwa URL MUNGKIN berbahaya, hanya dalam kasus tersebut kami melakukan panggilan ke server. 'MIGHT' itu 99% benar. Dalam kasus ini kami membuat panggilan ke server jarak jauh dan di sana kami dapat menggunakan beberapa fungsi hash lainnya dengan beberapa tabel hash seperti pada kasus pertama untuk mengambil dan memeriksa apakah URL benar-benar ada. Karena sebagian besar waktu, URL tidak mungkin berbahaya, filter bloom kecil di browser mengetahui hal itu dan karenanya menghemat waktu dengan menghindari panggilan ke server jarak jauh. Hanya dalam beberapa kasus, jika filter bloom memberi tahu kami bahwa URL MUNGKIN berbahaya, hanya dalam kasus tersebut kami melakukan panggilan ke server. 'MIGHT' itu 99% benar. Dalam kasus ini kami membuat panggilan ke server jarak jauh dan di sana kami dapat menggunakan beberapa fungsi hash lainnya dengan beberapa tabel hash seperti pada kasus pertama untuk mengambil dan memeriksa apakah URL benar-benar ada. Karena sebagian besar waktu, URL tidak mungkin berbahaya, filter bloom kecil di browser mengetahui hal itu dan karenanya menghemat waktu dengan menghindari panggilan ke server jarak jauh. Hanya dalam beberapa kasus, jika filter bloom memberi tahu kami bahwa URL MUNGKIN berbahaya, hanya dalam kasus tersebut kami melakukan panggilan ke server. 'MIGHT' itu 99% benar. filter mekar kecil di browser mengetahui hal itu dan karenanya menghemat waktu dengan menghindari panggilan ke server jauh. Hanya dalam beberapa kasus, jika filter bloom memberi tahu kami bahwa URL MUNGKIN berbahaya, hanya dalam kasus tersebut kami melakukan panggilan ke server. 'MIGHT' itu 99% benar. filter mekar kecil di browser mengetahui hal itu dan karenanya menghemat waktu dengan menghindari panggilan ke server jauh. Hanya dalam beberapa kasus, jika filter bloom memberi tahu kami bahwa URL MUNGKIN berbahaya, hanya dalam kasus tersebut kami melakukan panggilan ke server. 'MIGHT' itu 99% benar.
Jadi dengan menggunakan filter mekar kecil di browser, kami telah menghemat banyak waktu karena kami 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 sama sekali dari filter mekar. Semoga ini menghilangkan keraguan Anda :)
edit :
Saya telah menerapkan filter mekar untuk tugas pengujian URL berbahaya dengan Python. Kode tersebut dapat ditemukan di sini - https://github.com/tarunsharma1/Bloom-Filter Kode ini sangat mudah dipahami dan penjelasan rinci disediakan di file readme.
sumber
HashSet<String>
akan menggunakan 16 byte per elemen elemen dalam skenario kasus terbaik di mana hashtable benar-benar penuh: 4 byte dipetakan dari "keranjang" ke entri dalam tabel entri (sebuah array-dikemas tunggal-tertaut list), 4 byte untuk kode hash yang di-cache, 4 byte untuk penunjuk "berikutnya", 4 byte untuk penunjuk ke kunci. Dan itu belum termasuk ukuran senar. Dalam kasus terburuknya adalah 40 byte: setengah entri tidak digunakan dan 20 byte per entri setelahString
penunjuk diperluas menjadi 8 byte untuk arsitektur 64-bit.Saya akan mulai dengan penjelasan tentang apa itu filter bloom, apa yang bisa dan tidak bisa dilakukan, mengapa kita membutuhkannya, menunjukkan deskripsi intuitif cara kerjanya dan kemudian memberikan beberapa contoh ketika mereka bisa berguna.
Jadi filter bloom standar adalah struktur data probabilistik yang dapat * :
definitely not in the set
ataupossibly in the set
Inilah
possibly in the set
mengapa ini disebut probabilistik. Menggunakan kata-kata cerdas itu berarti positif palsu mungkin terjadi (ada kasus di mana ia berpikir secara keliru bahwa elemen itu positif) tetapi negatif palsu tidak mungkin.Tapi tidak bisa * :
* Set kaleng / tidak bisa untuk filter mekar dasar. Karena ini adalah struktur data berguna yang dibuat sejak lama, orang menemukan cara menambahkannya dengan fitur bermanfaat lainnya .
Tapi tunggu dulu: kita sudah tahu struktur data yang bisa menjawab semua ini tanpa 'mungkin' yang kabur dan juga tanpa semua batasan (tidak bisa menghapus, tidak bisa menampilkan semua). Dan itu disebut satu set . Dan inilah keuntungan utama dari filter mekar: hemat ruang dan ruang konstan .
Artinya tidak peduli berapa banyak elemen yang kita simpan di sana, ruangnya akan tetap sama. Ya, filter mekar dengan
10^6
elemen (filter mekar tidak berguna) akan mengambil ruang yang sama seperti filter mekar dengan10^20
elemen dan ruang yang sama seperti filter mekar dengan0
elemen. Jadi berapa banyak ruang yang dibutuhkan? Terserah Anda untuk memutuskan (tetapi ada pertukaran: semakin banyak elemen yang Anda miliki semakin Anda tidak yakin denganpossible in the set
jawaban Anda .Hal keren lainnya adalah bahwa itu adalah konstanta ruang. Saat Anda menyimpan data ke satu set, Anda harus benar-benar menyimpan data ini. Jadi jika Anda menyimpan
this long string in the set
setidaknya Anda harus menggunakan ruang 27 byte. Tetapi untuk kesalahan 1% dan nilai optimal k ** , Anda memerlukan ~ 9,6 bit (<2 byte) per elemen apa pun (apakah itu int pendek atau dinding teks besar).Properti lainnya adalah bahwa semua operasi mengambil waktu konstan, yang sama sekali tidak sama dengan waktu konstan diamortisasi dalam kasus himpunan (ingat bahwa jika himpunan memiliki tabrakan, itu dapat memburuk dalam
O(n)
waktu).** k adalah nilai fungsi hash yang digunakan di filter bloom
Saya tidak akan menjelaskan bagaimana filter mekar bekerja (artikel wikipedia melakukan pekerjaan yang sangat baik menjelaskan semuanya). Di sini saya hanya akan memberi tahu dasar-dasarnya secara singkat.
m
k
fungsi hash yang berbeda (semakin mandiri semakin baik)k
hash dari nilai ini dan menyetel bit yang sesuai ke 1k
hash dan jika setidaknya salah satu dari mereka tidak disetel, itu pasti tidak ada di set. Kalau tidak, itu bisa di set.Bahkan uraian ini cukup untuk memahami mengapa kita tidak bisa memastikan (Anda bisa mendapatkan semua bit yang ditetapkan dari berbagai nilai lain). Ini adalah visualisasi yang sangat bagus tentang cara kerjanya .
Jadi kapan filter mekar bisa bermanfaat? Jawaban singkatnya ada di mana - mana di mana positif palsu dapat diterima dan di mana Anda ingin memeriksa apakah ada sesuatu di set , tetapi bahkan jika tidak, itu bisa menjadi garis pertahanan pertama untuk mengesampingkan panggilan mahal ke penguji.
Berikut adalah daftar deskripsi yang lebih konkret:
sumber
Filter Bloom cukup berguna dalam bioinformatika. Mereka bisa lebih hemat ruang dibandingkan dengan menggunakan hash biasa, terutama bila 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 satu contoh yang digunakan untuk sesuatu yang relevan di sini .
EDIT:
Beberapa fungsi hash digunakan untuk meminimalkan positif palsu. Harapannya adalah bahwa di antara semua fungsi k-hash, setiap nilai akan memiliki tanda tangan unik dalam bit-array dibandingkan dengan setiap nilai lain yang memungkinkan. Namun, positif palsu memang ada, tetapi dapat diminimalkan ke tingkat yang dapat dikelola. Dengan menggunakan teknik ini, Anda mencirikan elemen secara independen dari ukurannya. Saat Anda mencarinya, Anda menggunakan setiap fungsi hash dan memeriksa untuk memastikan nilai bitnya semuanya 1.
Bandingkan ini dengan genom manusia, di mana peningkatan ukuran elemen meningkatkan ukuran tabel hash secara signifikan (Ukuran tabel adalah 4 * 4 k ). Ini dengan asumsi Anda menyandikan elemen menggunakan 2 bit / huruf.
sumber
Jika filter Bloom mengembalikan bahwa suatu item adalah anggota set, ada kemungkinan tertentu untuk false positive. Jika hanya satu fungsi hash yang digunakan untuk menunjukkan keanggotaan dalam set, probabilitas positif palsu akan lebih tinggi daripada menggunakan beberapa fungsi hash.
sumber