หลักการของตัวกรอง Bloom นั้นง่ายมาก: มันคือการแฮชสตริงลงในคีย์จำนวนเต็มจากนั้นเลือกลำดับบิตที่ยาวมากซึ่งเริ่มต้นด้วย 0 และเปลี่ยน 0 ที่ตำแหน่งนี้เป็น 1 ในคีย์ ครั้งต่อไปที่สตริงเข้ามาคีย์ค่าหลังจากแฮชและหากค่าของบิตนี้เป็น 1 ก็หมายความว่าสตริงมีอยู่
หากคุณทำตามวิธีการข้างต้นมันจะไม่แตกต่างจากอัลกอริทึมแฮชและยังคงมีการทำซ้ำของอัลกอริทึมแฮช
ตัวกรองบลูมแฮชสตริงเป็นหลายปุ่มดังนั้นฉันจะติดตามหนังสือ
ก่อนอื่นสร้างค่าคงที่ไบนารี 1.6 พันล้านจากนั้นตั้งค่าบิตไบนารีทั้งหมด 1.6 พันล้านเป็นศูนย์ สำหรับแต่ละสตริงจะใช้เครื่องกำเนิดไฟฟ้าแบบสุ่ม 8 ตัว (F1, F2, ... , F8) เพื่อสร้างลายนิ้วมือข้อมูล 8 ครั้ง (F1, F2, ... , F8) จากนั้นตัวสร้างตัวเลขสุ่ม G จะใช้ในการแมปข้อมูลลายนิ้วมือทั้งแปดนี้เป็น 8 หมายเลขธรรมชาติ G1, G2, ... , G8 ใน 1 ถึง 1.6 พันล้าน ตอนนี้เปลี่ยนบิตไบนารีทั้งหมดใน 8 ตำแหน่งเหล่านี้เป็น 1 วิธีนี้จะสร้างตัวกรองบาน
ดังนั้นจะตรวจพบได้อย่างไรว่ามีสตริงอยู่แล้วหรือไม่?
ตอนนี้ใช้เครื่องกำเนิดหมายเลขสุ่ม 8 ตัว (F1, F2, ... , F8) เพื่อสร้าง 8 ลายนิ้วมือข้อมูล S1, S2, ... , S8 สำหรับสตริงนี้จากนั้นจึงสอดคล้องกับลายนิ้วมือข้อมูล 8 ตัวเหล่านี้กับบิตไบนารี 8 ตัวของตัวกรอง Bloom คือ T1, T2, ... , T8 หากสตริงมีอยู่แล้วจะเห็นได้ชัดว่าบิตไบนารีที่สอดคล้องกับ T1, T2, ... , T8 ควรเป็น 1 นี่คือวิธีการตรวจสอบว่ามีสตริงอยู่แล้วหรือไม่
ในความเป็นจริงตัวกรอง Bloom เป็นส่วนขยายของอัลกอริทึมแฮช เนื่องจากมันเป็นแฮชเป็นหลักจึงมีข้อบกพร่องอย่างแน่นอน กล่าวอีกนัยหนึ่งจะมีการพิจารณาผิดอย่างแน่นอน สตริงไม่ปรากฏขึ้น แต่การตัดสินของตัวกรอง Bloom ได้ปรากฏขึ้น แม้ว่าความเป็นไปได้จะเล็กมาก แต่ก็มีอยู่
ดังนั้นจะลดความน่าจะเป็นนี้ได้อย่างไร? ก่อนอื่นเลยสามารถจินตนาการได้ว่าหากมีการขยายลายนิ้วมือ 8 ข้อมูลไปยังข้อผิดพลาด 16 ข้อความน่าจะเป็นจะลดลงอย่างแน่นอน แต่ก็ควรพิจารณาว่าด้วยวิธีนี้จำนวนสตริงที่ตัวกรองบานสามารถลดลงได้ 1 ครั้ง นอกจากนี้เลือกฟังก์ชั่นแฮชที่ดีและมีวิธีแฮชหลายประเภทสำหรับสตริงรวมถึงฟังก์ชั่นแฮชที่ดีมาก
ตัวกรองสีบรอนซ์ส่วนใหญ่ใช้เพื่อกรอง URL ที่เป็นอันตราย URL ที่เป็นอันตรายทั้งหมดถูกสร้างขึ้นบนตัวกรองสีบรอนซ์จากนั้นผู้ใช้จะเข้าถึง URL หากอยู่ใน URL ที่เป็นอันตรายผู้ใช้จะได้รับแจ้ง ด้วยวิธีนี้เรายังสามารถตั้งค่าการอนุญาตสำหรับ URL บางอย่างที่มักจะมีข้อผิดพลาดในการตัดสินและจากนั้นจับคู่ URL ที่ถูกตัดสินว่ามีอยู่และ URL ในผู้ที่อนุญาต หากพวกเขาอยู่ใน Whitelist พวกเขาจะได้รับการปล่อยตัว แน่นอนว่าผู้ที่อนุญาตผู้ใช้งานนี้ไม่สามารถใหญ่เกินไปและมันใหญ่เกินไปและความน่าจะเป็นของข้อผิดพลาดตัวกรองบานมีขนาดเล็กมาก ผู้อ่านที่สนใจสามารถตรวจสอบอัตราความผิดพลาดของตัวกรอง Bloom
ต่อไปนี้เป็นซอร์สโค้ดของตัวกรอง Bloom เวอร์ชัน Java:
นำเข้า java.util.bitset; /** * * @author xkey */คลาสสาธารณะ Bloomfilter {ส่วนตัวคงที่ int final default_size = 2 << 24; // ความยาวบิตของตัวกรองบลูเตอร์ส่วนตัวคงที่ int สุดท้าย [] seeds = {3,5,7, 11, 13, 31, 37, 61}; private static simplehash [] func = new simplehash [seeds.length]; โมฆะคงที่สาธารณะ addValue (ค่าสตริง) {สำหรับ (simplehash f: func) // แฮชค่าสตริงเป็น 8 หรือมากกว่าจำนวนเต็มจากนั้นเปลี่ยนเป็น 1 บนบิตของจำนวนเต็มเหล่านี้ bits.set (f.hash (ค่า) จริง); } โมฆะคงที่สาธารณะเพิ่ม (ค่าสตริง) {ถ้า (ค่า! = null) addValue (ค่า); } บูลีนคงที่สาธารณะมี (ค่าสตริง) {ถ้า (value == null) ส่งคืน false; บูลีน ret = true; สำหรับ (SimpleHash F: func) // ในความเป็นจริงไม่จำเป็นต้องเรียกใช้ทั้งหมดที่นี่ เพียงแค่ ret == เท็จหนึ่งครั้งจากนั้นสตริงจะไม่รวมอยู่ ret = ret && bits.get (f.hash (ค่า)); return ret; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {ค่าสตริง = "www.vevb.com"; สำหรับ (int i = 0; i <seeds.length; i ++) {func [i] = new simplehash (default_size, เมล็ด [i]); } เพิ่ม (ค่า); System.out.println (มี (ค่า)); }} คลาส SimpleHash {// สิ่งนี้เทียบเท่ากับโครงสร้างใน C ++ Private Int Cap; เมล็ดพันธุ์ int ส่วนตัว; Public SimpleHash (int cap, int seed) {this.cap = cap; this.eed = เมล็ด; } int public int hash (ค่าสตริง) {// stand hash มันเป็นสิ่งสำคัญมากที่จะเลือกฟังก์ชันแฮชที่ดี int result = 0; int len = value.length (); สำหรับ (int i = 0; i <len; i ++) {result = seed * result+value.charat (i); } return (cap - 1) & ผลลัพธ์; - สรุป: Bloom Filter เป็นนวัตกรรมในอัลกอริทึมการแฮชและยังใช้พื้นที่น้อยมากและมีอัตราความผิดพลาดต่ำ ในระยะสั้นความคิดที่เป็นนวัตกรรมนี้คุ้มค่ากับการเรียนรู้และเป็นการใช้ประเภทข้อมูลเช่นบิต
วิธีการใช้งาน Java ของตัวกรอง Bloom เป็นเนื้อหาทั้งหมดที่ฉันแบ่งปันกับคุณ ฉันหวังว่าคุณจะให้ข้อมูลอ้างอิงและฉันหวังว่าคุณจะสนับสนุน wulin.com มากขึ้น