ตัวกรองบลูม

ตัวกรอง Bloom ถูกกำหนดให้เป็นโครงสร้างข้อมูลที่ออกแบบมาเพื่อระบุการมีอยู่ขององค์ประกอบในชุดในลักษณะที่รวดเร็วและมีประสิทธิภาพในหน่วยความจำ

โครงสร้างข้อมูลเฉพาะชื่อโครงสร้างข้อมูลความน่าจะเป็น ถูกนำมาใช้เป็นตัวกรองบาน โครงสร้างข้อมูลนี้ช่วยให้เราระบุได้ว่าองค์ประกอบหนึ่งมีอยู่หรือขาดหายไปในชุด

Bit Vector ถูกนำมาใช้เป็นโครงสร้างข้อมูลพื้นฐาน นี่เป็นเรื่องเล็กๆ ที่เราจะใช้เพื่ออธิบาย

แต่ละเซลล์ว่างในตารางนั้นระบุบิตและตัวเลขที่อยู่ด้านล่างดัชนีหรือตำแหน่งของเซลล์นั้น ในการผนวกองค์ประกอบเข้ากับตัวกรอง Bloom เราเพียงแค่แฮชมันสองสามครั้งและตั้งค่าบิตในเวกเตอร์บิตที่ตำแหน่งหรือดัชนีของแฮชเหล่านั้นเป็น 1

การใช้งาน Bloom Filter อย่างละเอียดจะกล่าวถึงในตอนต่อไป

ตัวกรอง Bloom รองรับการทำงาน 2 อย่าง โดยในตอนแรกจะผนวกวัตถุและติดตามวัตถุ และถัดไปตรวจสอบว่ามีการดูวัตถุมาก่อนหรือไม่

การผนวกวัตถุเข้ากับตัวกรอง Bloom

• เราคำนวณค่าแฮชสำหรับอ็อบเจ็กต์ที่จะผนวก;
• เราใช้ค่าแฮชเหล่านี้เพื่อตั้งค่าบิตบางตัวในสถานะตัวกรองบลูม (ค่าแฮชคือตำแหน่งของบิตที่จะตั้งค่า)

ตรวจสอบว่าตัวกรอง Bloom มีวัตถุหรือไม่ -

• เราคำนวณค่าแฮชสำหรับอ็อบเจ็กต์ที่จะผนวก;
• ต่อไปเราจะตรวจสอบว่าบิตที่จัดทำดัชนีโดยค่าแฮชเหล่านี้ได้รับการตั้งค่าในสถานะตัวกรอง Bloom หรือไม่

เราต้องจำไว้ว่าค่าแฮชสำหรับออบเจกต์ไม่ได้ถูกผนวกเข้ากับสถานะตัวกรองบลูมโดยตรง แต่ละฟังก์ชันแฮชจะกำหนดบิตที่จะตั้งค่าหรือตรวจสอบ ตัวอย่างเช่น หากใช้ฟังก์ชันแฮชเพียงฟังก์ชันเดียว จะมีการตรวจสอบหรือตรวจสอบเพียงบิตเดียวเท่านั้น