เมนูนำทาง
ตัวกรองของบลูม
การทำงานจะคล้ายกับการกรอง โดยตะแกรงที่ใช้กรองจะมีอยู่หลายช่อง ในที่นี้ขอเรียกว่าช่องหมายเลข 1,2,3,...,10 โดยการตรวจสอบว่าข้อมูลตัวนั้นจะไหลผ่านตัวกรองช่องไหน เราจะใช้ฟังก์ชันแฮชซึ่งใช้เวลาในการทำงานคงตัว ดังนั้นการค้นหาจึงใช้เวลาคงตัว O(1) และตัวกรองแต่ละช่องจะมีขนาดเพียง 1 บิต(บันทึกแค่ว่าเคยมีข้อมูลไหลผ่านรึยัง? ถ้าเคยเป็น 1 ไม่เคยเป็น 0)
เราจะนำข้อมูลนั้นไปผ่านเครื่องกรอง แล้วทำการบันทึกไว้ว่าช่องไหนที่ข้อมูลนั้นไหลผ่าน เช่น ถ้าเราเพิ่ม A แล้วพบว่า A ไหลผ่านช่องหมายเลข 1,2,5 ได้ ก็บันทึกไว้ว่าช่องหมายเลข1,2,5 เคยมีข้อมูลไหลผ่านแล้ว
ถ้ามีการลบข้อมูลออก เราจะไม่สามารถแก้ข้อมูลที่ตัวกรองได้ เพราะตัวกรอง 1 ช่องอาจมีข้อมูลไหลผ่านหลายตัว ไม่รู้ว่าตัวไหนบ้าง(จริง ๆ แล้วเราสามารถแก้ข้อมูลของตัวกรองได้ โดยการหยิบข้อมูลทุกตัวมาเข้าเครื่องกรองใหม่อีกรอบ โดยหยิบมาทีละตัว แต่เสียเวลานานมาก) ดังนั้นวิธีนี้จึงไม่เหมาะกับการใช้งานที่มีการลบข้อมูลออกบ่อย ๆ
เราจะนำข้อมูลนั้นไปผ่านเครื่องกรอง แล้วตรวจสอบว่าช่องที่ข้อมูลนี้สามารถไหลผ่านได้ เคยถูกข้อมูลตัวอื่นไหลผ่านมาก่อนรึเปล่า? ถ้ายังไม่เคย ก็จะรู้ได้ทันทีว่าข้อมูลที่เรากำลังค้นนั้น ไม่ได้อยู่ในที่เก็บข้อมูลของเรา เช่น ถ้าเราค้น B แล้วพบว่าไหลผ่านช่องหมายเลข 2,5,7 ได้ เราก็ไปตรวจสอบช่องหมายเลข 2,5,7 ว่าเคยมีข้อมูลไหลผ่านรึยัง? ถ้ามีอันใดอันหนึ่งไม่เคยมีข้อมูลไหลผ่าน ก็ตอบได้เลยว่า "ค้นไม่เจอ" แต่ถ้าทุกช่องที่ B ไหลผ่านเคยมีข้อมูลไหลผ่านมาแล้วก็แปลว่า "ค้นเจอ"
แต่ความจริงไม่ได้สวยหรูขนาดนั้น เพราะวิธีนี้อาจเกิดข้อผิดพลาดขึ้นได้ เช่น ถ้าเราเพิ่ม A(ผ่านช่องหมายเลข 1,2,5) และเพิ่ม B(ผ่านช่องหมายเลข 3,4,7)จากนั้นค้นหา C(ผ่านช่องหมายเลข 3,4,5)จะพบว่า ตัวกรองทั้ง 3 ช่องเคยถูกลอดผ่านแล้ว แต่ C ยังไม่ได้ถูกเพิ่มเข้ามา ถ้าเกิดเหตุการณ์แบบนี้ก็จะผิด ดังนั้น ถ้าค้นแล้วเจอไม่ได้แปลว่ามีข้อมูลนั้นอยู่จริง ๆ ต้องไปตรวจสอบอีกทีว่ามีอยู่จริง ๆ หรือไม่ แต่ถ้าค้นแล้วไม่เจอ สามารถสรุปได้ทันทีว่าไม่เจอ
เพื่อให้ง่ายต่อการทำความเข้าใจกระบวนการเพิ่มข้อมูล และการค้นข้อมูล แนะนำให้ดูวิดีโอเมนูนำทาง
ตัวกรองของบลูมใกล้เคียง
แหล่งที่มา
WikiPedia: ตัวกรองของบลูม