บลูมฟิลเตอร์

ตัวกรองบลูมเป็นโครงสร้างข้อมูลความน่าจะเป็นที่ออกแบบมาเพื่อทดสอบอย่างมีประสิทธิภาพว่าองค์ประกอบเป็นส่วนหนึ่งของชุดหรือไม่ มันถูกคิดค้นโดย Burton Howard Bloom ในปี 1970 และได้กลายเป็นเครื่องมือพื้นฐานในวิทยาการคอมพิวเตอร์เนื่องจากความสามารถในการจัดการชุดข้อมูลขนาดใหญ่โดยใช้หน่วยความจำน้อยที่สุด แตกต่างจากโครงสร้างข้อมูลแบบดั้งเดิม เช่น ตารางแฮชหรือแผนผังการค้นหาแบบไบนารี ตัวกรองบลูมสามารถให้คำตอบที่ชัดเจนเมื่อองค์ประกอบไม่อยู่ในชุด แต่จะมีเพียงคำตอบที่น่าจะเป็นเท่านั้นเมื่อมีองค์ประกอบอยู่ ซึ่งหมายความว่าแม้ว่าผลบวกลวงจะเป็นไปได้ แต่ผลลบลวงก็ทำไม่ได้

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

ข้อดีอย่างหนึ่งที่สำคัญของฟิลเตอร์บานคือประสิทธิภาพการใช้พื้นที่ พวกเขาต้องการหน่วยความจำน้อยกว่ามากเมื่อเทียบกับโครงสร้างข้อมูลอื่นๆ สำหรับงานเดียวกัน โดยเฉพาะอย่างยิ่งเมื่อจำนวนองค์ประกอบเพิ่มขึ้น ตัวอย่างเช่น จำเป็นต้องมีน้อยกว่า 10 บิตต่อองค์ประกอบเพื่อให้ได้ความน่าจะเป็นบวกลวง 1% โดยไม่คำนึงถึงจำนวนขององค์ประกอบในชุด ทำให้ตัวกรองบานมีประโยชน์อย่างยิ่งในแอปพลิเคชันที่การใช้หน่วยความจำเป็นปัญหาสำคัญ เช่น เราเตอร์เครือข่าย ระบบฐานข้อมูล และระบบแบบกระจาย

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

ในการใช้งานจริง ตัวกรองบานพบว่ามีการใช้งานอย่างแพร่หลายในโดเมนต่างๆ ตัวอย่างเช่น ใน Bitcoin จะใช้เพื่อปรับปรุงความเป็นส่วนตัวในไคลเอนต์ Siimple Payment Verification (SPV) โดยอนุญาตให้ผู้ใช้สืบค้นธุรกรรมโดยไม่ต้องเปิดเผยที่อยู่ของตน เครือข่ายการจัดส่งเนื้อหา เช่น Akamai ใช้ตัวกรอง Bloom เพื่อจัดการพื้นที่จัดเก็บแคชอย่างมีประสิทธิภาพ ลดภาระงานบนเซิร์ฟเวอร์โดยหลีกเลี่ยงการเรียกข้อมูลที่ไม่จำเป็น แม้จะมีลักษณะและข้อจำกัดที่น่าจะเป็นไปได้ แต่ตัวกรองบลูมยังคงเป็นเครื่องมืออันล้ำค่าในการออกแบบระบบที่มีประสิทธิภาพและปรับขนาดได้