ตัวกรองของบลูม

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

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

 

ภาพตัวอย่าง ตัวกรองของบลูม ในภาพมี x y และ z อยู่ในเซตของข้อมูล ลูกศรแต่ละสีชี้ตำแหน่งของช่องที่ x y z ลอดผ่าน จะเห็นว่าลูกศรของ w ชี้ไปยังช่องที่มีเลข 1 1 0 ตามลำดับ ซึ่งหมายความว่า w ไม่ได้อยู่ในเซตของข้อมูล เพราะตัวกรอง 3 ช่องที่ w ไหลผ่านมีบางอันเป็น 0(คือยังไม่เคยมีข้อมูลไหลผ่าน) สำหรับภาพตัวอย่างนี้ใช้ฟังก์ชันแฮช 3 ฟังก์ชัน และใช้ตัวกรอง 18 ช่อง

การทำงานจะคล้ายกับการกรอง โดยตะแกรงที่ใช้กรองจะมีอยู่หลายช่อง ในที่นี้ขอเรียกว่าช่องหมายเลข 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 ยังไม่ได้ถูกเพิ่มเข้ามา ถ้าเกิดเหตุการณ์แบบนี้ก็จะผิด ดังนั้น ถ้าค้นแล้วเจอไม่ได้แปลว่ามีข้อมูลนั้นอยู่จริง ๆ ต้องไปตรวจสอบอีกทีว่ามีอยู่จริง ๆ หรือไม่ แต่ถ้าค้นแล้วไม่เจอ สามารถสรุปได้ทันทีว่าไม่เจอ

เพื่อให้ง่ายต่อการทำความเข้าใจกระบวนการเพิ่มข้อมูล และการค้นข้อมูล แนะนำให้ดูวิดีโอ

ประสิทธิภาพ

• การเพิ่มข้อมูล ใช้เวลาคงตัว O(1) เนื่องจากใช้ฟังก์ชันแฮช

• การลบข้อมูล ใช้เวลา O(n) เพราะต้องหยิบข้อมูลทุกตัวมาผ่านตัวกรองอีกรอบ

• การค้นข้อมูล ถ้าค้นแล้วเจอ ก็ต้องไปตรวจสอบดูอีกทีว่ามีอยู่จริง ๆ หรือไม่ ทำให้เสียเวลา O(n) หรือ O(log n) (แล้วแต่ชนิดของ

โครงสร้างข้อมูล) แต่ถ้าค้นแล้วไม่เจอ สามารถสรุปได้ทันทีว่าไม่เจอ O(1)

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

อ้างอิง

1. Donald Knuth. "[[The Art of Computer Programming]], Errata for Volume 3 (2nd ed.)". URL–wikilink conflict (help)