การ เข้าใจ และ การ นํา สบู่ มา ใช้: การ คํานวณ, การ ใช้ กรณี, และ ข้อ จํากัด

ตัวกรองบลูมเป็นโครงสร้างข้อมูลแบบความน่าจะเป็น ที่ใช้ทดสอบว่าธาตุนั้นเป็นสมาชิกของเซตหรือไม่. มันมีประสิทธิภาพในด้านพื้นที่และความเร็ว, ทําให้เหมาะสมกับโปรแกรมที่โปรแกรมใช้ query สมาชิกอย่างรวดเร็วต้องใช้บวกเท็จที่ยอมรับได้บางส่วน

วิธี ที่ บลูม กรอง งาน

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

การคํานวณสําหรับตัวกรองบลูม

ความน่าจะเป็นบวกเท็จขึ้นอยู่กับขนาดของอาร์เรย์บิต (m), จํานวนสมาชิกที่แทรกเข้า (n), และจํานวนฟังก์ชันแฮช (k). ความน่าจะเป็น (p) ของจํานวนบวกเท็จสามารถประมาณได้:

[FLT: 0]] [p ⁇ (1– e^{] - kn/m}]^{. k[FLTT:4] [FLTT:5].}

ค่าบวกแบบโอปติเม็นต์สําหรับ k และ m สามารถลดค่าบวกเท็จสําหรับค่า n ที่กําหนดได้ โดยทั่วไปแล้ว k จะถูกเลือกเป็น:

[FLT: 0]. k= (m/n) * ln 2

ใช้ตัวพิมพ์ของตัวกรองบลู

ตัวกรองบลูมถูกใช้ในสาขาต่างๆ รวมถึง:

• ระบบฐานข้อมูลสําหรับการทดสอบสมาชิกอย่างรวดเร็ว
• การทําแคชกับหน้าเว็บเพื่อลดการค้นหาบนดิสก์
• ระบบที่แยกแยกไว้สําหรับการจับคู่ข้อมูล
• ความปลอดภัยในเครือข่ายสําหรับการกรองสแปม

จํากัดตัวกรองบลู

แม้ ว่า จะ มี ประสิทธิภาพ แต่ บลูม ตัวกรอง ก็ มี ขีด จํากัด.