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

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

## กระบวนการทำงาน
thumb|360px|ภาพตัวอย่าง ตัวกรองของบลูม ในภาพมี 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 ได้

## อ้างอิง

หมวดหมู่:การแฮช