Prinsip filter mekar sangat sederhana: Ini adalah hash string ke kunci integer, dan kemudian pilih urutan bit yang sangat panjang, yang dimulai dengan 0, dan ubah 0 pada posisi ini menjadi 1 di kunci; Lain kali sebuah string masuk, tombol nilai setelah hash, dan jika nilai pada bit ini juga 1, itu berarti string ada.
Jika Anda mengikuti metode di atas, itu tidak akan berbeda dari algoritma hash, dan masih ada duplikasi algoritma hash.
Filter Bloom hash string ke beberapa tombol, jadi saya hanya akan mengikuti buku.
Pertama -tama buat konstanta biner 1,6 miliar, dan kemudian atur semua 1,6 miliar bit biner ke nol. Untuk setiap string, 8 generator acak yang berbeda (F1, F2, ..., F8) digunakan untuk menghasilkan 8 sidik jari informasi (F1, F2, ..., F8). Kemudian, generator bilangan acak G digunakan untuk memetakan delapan sidik jari ini menjadi 8 bilangan alami G1, G2, ..., G8 dalam 1 hingga 1,6 miliar. Sekarang ubah semua bit biner di 8 posisi ini menjadi 1. Dengan cara ini filter mekar dibangun.
Jadi bagaimana cara mendeteksi apakah string sudah ada?
Sekarang gunakan 8 generator nomor acak (F1, F2, ..., F8) untuk menghasilkan 8 informasi sidik jari S1, S2, ..., S8 untuk string ini, dan kemudian sesuai dengan 8 informasi ini dengan 8 bit biner dari filter mekar, yaitu T1, T2, ..., T8. Jika string ada, maka jelas bit biner yang sesuai dengan T1, T2, ..., T8 harus 1. Ini adalah cara menentukan apakah string sudah ada.
Bahkan, filter Bloom adalah perpanjangan dari algoritma hash. Karena pada dasarnya adalah hash, pasti akan ada kekurangan. Dengan kata lain, pasti akan ada kesalahan penilaian. Sebuah string belum muncul, tetapi penilaian filter Bloom telah muncul. Meskipun kemungkinannya sangat kecil, memang ada.
Jadi bagaimana cara mengurangi probabilitas ini? Pertama -tama, dapat dibayangkan bahwa jika 8 informasi sidik jari diperpanjang hingga 16 kesalahan, probabilitas pasti akan dikurangi, tetapi juga harus dipertimbangkan bahwa dengan cara ini, jumlah string yang dapat disimpan oleh filter mekar juga dikurangi 1 kali; Selain itu, pilih fungsi hash yang bagus, dan ada banyak jenis metode hash untuk string, termasuk fungsi hash yang sangat bagus.
Filter perunggu terutama digunakan untuk menyaring URL berbahaya. Semua URL berbahaya dibangun di atas filter perunggu, dan kemudian pengguna diakses oleh URL. Jika berada dalam URL jahat, pengguna akan diberi tahu. Dengan cara ini, kita juga dapat menetapkan daftar putih untuk beberapa URL yang sering memiliki kesalahan dalam penilaian, dan kemudian mencocokkan URL yang dinilai ada dan URL di daftar putih. Jika mereka berada di daftar putih, mereka akan dibebaskan. Tentu saja, daftar putih ini tidak bisa terlalu besar, juga tidak terlalu besar, dan probabilitas kesalahan filter mekar sangat kecil. Pembaca yang tertarik dapat memeriksa tingkat kesalahan filter Bloom.
Berikut ini adalah kode sumber filter Bloom versi Java:
impor java.util.bitset; /** * * @author xkey */ public class BloomFilter { private static final int DEFAULT_SIZE = 2 << 24;//Bit length of the Bloom filter private static final int[] seeds = {3,5,7, 11, 13, 31, 37, 61};//The prime number here can be selected to reduce the error rate very well private static BitSet bits = new BitSet(DEFAULT_SIZE); private static SimpleHash [] func = new SimpleHash [seeds.length]; public static void addValue (nilai string) {for (SimpleHash f: func) // hash nilai string menjadi 8 atau lebih bilangan bulat, dan kemudian ubah menjadi 1 pada bit bit bitteger ini.set (f.hash (nilai), true); } public static void add (nilai string) {if (value! = null) addValue (value); } public static boolean berisi (nilai string) {if (value == null) return false; ret boolean = true; Untuk (SimpleHash F: Func) // Faktanya, tidak perlu menjalankan semuanya di sini. Just ret == false sekali, maka string tidak akan dimasukkan. ret = ret && bits.get (f.hash (value)); Return Ret; } public static void main (string [] args) {string value = "www.vevb.com"; untuk (int i = 0; i <seeds.length; i ++) {func [i] = new SimpleHash (default_size, seed [i]); } add (value); System.out.println (berisi (nilai)); }} class SimpleHash {// Hal ini setara dengan struktur dalam C ++ private int cap; benih int pribadi; Public SimpleHash (int cap, int seed) {this.cap = cap; this.seed = seed; } public int hash (nilai string) {// hash stand, sangat penting untuk memilih fungsi hash yang baik int result = 0; int len = value.length (); untuk (int i = 0; i <len; i ++) {result = seed * result+value.charat (i); } return (cap - 1) & hasil; }} Ringkasan: Bloom Filter adalah inovasi dalam algoritma hashing, dan juga menghabiskan sangat sedikit ruang dan memiliki tingkat kesalahan yang rendah. Singkatnya, ide inovatif ini layak dipelajari dan merupakan penggunaan tipe data seperti bit.
Metode implementasi Java dari Bloom Filter adalah semua konten yang telah saya bagikan dengan Anda. Saya harap Anda dapat memberi Anda referensi dan saya harap Anda dapat mendukung wulin.com lebih lanjut.