ผู้ใช้:Momepukku/ทดลองเขียน

ตัวกรองของบลูม (อังกฤษ: Bloom Filter) ถูกคิดขึ้นโดย เบอร์ตัน ฮาเวิร์ด บลูม ในปี พ.ศ. 2513 เป็นวิธีหนึ่งในการตรวจสอบข้อมูลที่อยู่ในเซตว่ามีข้อมูลที่เราสนใจอยู่ในนั้นหรือไม่ ซึ่งวิธีนี้จะหาคำตอบได้ด้วยเวลาคงตัวO(1) กล่าวคือ เวลาที่ใช้ในการตรวจสอบไม่ขึ้นกับจำนวนข้อมูล แต่ถ้าผลการตรวจสอบออกมาเป็นจริง(มีข้อมูลตัวที่เราสนใจอยู่ในเซต) อาจจะเป็นคำตอบที่ผิด แต่ถ้าผลการตรวจสอบออกมาเป็นเท็จ(ไม่มีข้อมูลตัวนั้นอยู่ในเซต) จะเป็นคำตอบที่ถูกต้องอย่างแน่นอน

กระบวนการทำงาน

การทำงานจะคล้ายกับการกรอง โดยตะแกรงที่ใช้กรองจะมีอยู่หลายอัน ในที่นี้ขอเรียกว่าตัวกรองหมายเลข 1,2,3,...,10 โดยการตรวจสอบว่าข้อมูลตัวนั้นลอดผ่านตัวกรองตัวไหนได้ เราจะใช้ฟังก์ชันแฮชซึ่งใช้เวลาคงตัว ดังนั้นการค้นหาจึงใช้เวลาคงตัว O(1) และตัวกรองแต่ละอันจะมีขนาดเพียง 1 บิต(เก็บแค่ว่าเคยถูกลอดผ่านรึยัง? ถ้าเคยเป็น 1 ไม่เคยเป็น 0)

การเพิ่มข้อมูล

เราจะนำข้อมูลนั้นไปผ่านเครื่องกรอง แล้วทำการบันทึกไว้ว่าตัวกรองอันไหนที่ข้อมูลนั้นลอดผ่านได้

เช่น ถ้าเราเพิ่ม A แล้วพบว่า A ลอดผ่านตัวกรองหมายเลข 1,2,5 ได้ ก็บันทึกไว้ว่าตัวกรองหมายเลข1,2,5 เคยมีข้อมูลลอดผ่านแล้ว

การค้นข้อมูล

เราจะนำข้อมูลนั้นไปผ่านเครื่องกรอง แล้วตรวจสอบว่าตัวกรองที่ข้อมูลนี้สามารถลอดผ่านได้ เคยถูกข้อมูลตัวอื่นลอดผ่านมาก่อนรึเปล่า? ถ้ายังไม่เคย ก็จะรู้ได้ทันทีว่าข้อมูลที่เรากำลังค้นนั้น ไม่ได้อยู่ในที่เก็บข้อมูลของเรา เช่น ถ้าเราค้น B แล้วพบว่าลอดผ่านตัวกรองหมายเลข 2,5,7 ได้ เราก็ไปตรวจสอบตัวกรองหมายเลข 2,5,7 ว่าเคยมีข้อมูลลอดผ่านรึยัง? ถ้ามีอันใดอันหนึ่งไม่เคยถูกลอดผ่าน ก็ตอบได้เลยว่า "ค้นไม่เจอ"