ต วกรองของบล ม อ งกฤษ Bloom Filter ถ กค ดข นโดย ในป พ ศ 2513 เป นว ธ หน งในการตรวจสอบข อม ลท อย ในเซตว าม ข อม ลท เราสนใ

ตัวกรองของบลูม (อังกฤษ: 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 ได้

อ้างอิง

Donald Knuth. . stanford.edu (2nd ed.). คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2012-03-06. สืบค้นเมื่อ 2011-09-24.
ภาคภูมิ ยิ้มสุขอนันต์ (14 กุมภาพันธ์ 2011). BloomFilter – โดยทาง YouTube.

บทความคอมพิวเตอร์ อุปกรณ์ต่าง ๆ หรือเครือข่ายนี้ยังเป็น คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล

[1] Donald Knuth. . stanford.edu (2nd ed.). คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2012-03-06. สืบค้นเมื่อ 2011-09-24.

[2] ภาคภูมิ ยิ้มสุขอนันต์ (14 กุมภาพันธ์ 2011). BloomFilter – โดยทาง YouTube.