Streaming Algoritma dan Penapis Kembang - patung

Di tengah-tengah banyak algoritma penstriman adalah penapis Bloom. Dicipta hampir 50 tahun yang lalu oleh Burton H. Bloom, ketika ilmu sains masih muda, maksud asal pencipta algoritma ini adalah untuk perdagangan ruang (memori) dan / atau masa (kerumitan) terhadap apa yang dipanggilnya ralat yang dibenarkan. Kertas asalnya berjudul Ruang / Masa Perdagangan dalam Hash Coding dengan Kesalahan yang Dapat Dibenarkan.

Anda mungkin tertanya-tanya tentang ruang dan masa yang Bloom mempertimbangkan motivator untuk algoritmanya. Bayangkan anda perlu menentukan sama ada sesuatu elemen telah muncul dalam aliran menggunakan beberapa struktur data yang telah dibincangkan sebelumnya. Menemukan sesuatu dalam aliran bermakna pencatatan dan carian pantas, oleh itu jadual hash kelihatan sebagai pilihan yang ideal. Hash tables hanya perlu menambah elemen yang anda mahu rekod dan menyimpannya. Memulihkan elemen dari jadual hash adalah pantas kerana jadual hash menggunakan nilai yang dimanipulasi dengan mudah untuk mewakili elemen, dan bukan unsur itu sendiri (yang mungkin agak kompleks). Namun, menyimpan kedua-dua elemen dan indeks kepada elemen tersebut mempunyai batasan. Jika jadual hash menghadapi lebih banyak unsur daripada yang dapat dikendalikan, seperti elemen dalam aliran yang berterusan dan berpotensi terhingga, anda akan menamatkan masalah memori pada satu ketika.

Satu pertimbangan penting untuk penapis Bloom adalah bahawa positif palsu boleh berlaku, tetapi negatif palsu tidak boleh. Sebagai contoh, aliran data mungkin mengandungi data pemantauan masa nyata untuk loji kuasa. Apabila menggunakan penapis Bloom, analisis aliran data akan menunjukkan bahawa bacaan yang dijangka mungkin sebahagian daripada set bacaan yang dibenarkan, dengan beberapa kesalahan yang dibenarkan. Walau bagaimanapun, apabila ralat berlaku dalam sistem, analisis yang sama menunjukkan bahawa pembacaan bukan sebahagian daripada bacaan yang dibenarkan. Positif palsu tidak mungkin menyebabkan masalah, tetapi ketiadaan negatif palsu bermakna semua orang tetap selamat. Kerana potensi untuk positif palsu, penapis seperti penapis Bloom adalah struktur data probabilistik - mereka tidak memberikan jawapan tertentu tetapi mungkin.

Hashes, penyertaan individu dalam jadual hash, pantas kerana mereka bertindak seperti indeks buku. Anda menggunakan fungsi hash untuk menghasilkan hash; input adalah elemen yang mengandungi data yang rumit, dan output adalah nombor mudah yang bertindak sebagai indeks ke elemen itu. Fungsi hash adalah deterministik kerana ia menghasilkan nombor yang sama setiap kali anda memberi suapan input data tertentu.Anda menggunakan hash untuk mencari maklumat kompleks yang anda perlukan. Penapis mekar sangat berguna kerana mereka adalah cara yang berjimat untuk merakam kesan banyak elemen tanpa perlu menyimpannya sebagai jadual hash. Mereka bekerja dengan cara yang mudah dan menggunakan bahan berikut sebagai bahan utama:

• Sebuah vektor bit: Senarai elemen bit, di mana setiap bit dalam elemen boleh mempunyai nilai 0 atau 1. Senarai itu adalah panjang bilangan bit yang dipanggil m. Lebih besar m adalah, lebih baik, walaupun terdapat cara-cara untuk menentukan saiznya secara optimum.
• Satu siri fungsi hash: Setiap fungsi hash mewakili nilai yang berbeza. Fungsi hash dengan cepat dapat mengkritik data dan menghasilkan hasil yang diedarkan secara seragam, yang menghasilkan hasil yang sama dari minimum ke nilai output maksimum hash.