อ่านบทความนี้ใน Facebook
“…สมมุติว่าคุณกำลังเล่นเกมต่อคำ ที่ห้ามพูดคำซ้ำกับคำที่ทุกคนเคยพูดมาแล้วทั้งหมด”
เนื่องจากว่าคุณอยากที่จะชนะมาก หนึ่งในวิธีการก็คือคุณต้องจำคำทั้งหมดเอาไว้ในหัว แต่แน่นอนว่าการจำคำที่ทุกคนเคยพูดออกมาทั้งหมดไม่ใช่เรื่องง่าย
…แต่โชคดีว่าคุณเป็น “เซียนหมากรุก” ที่สามารถจำตำแหน่งหมากบนกระดานในหัวได้อย่างแม่นยำ คุณจะใช้ประโยชน์จากความสามารถของคุณอย่างไร?
หนึ่งในวิธีการที่ทำได้ก็คือ “การสร้าง function ไว ๆ ที่เปลี่ยนคำใด ๆ ก็ตามให้กลายเป็นตำแหน่งของกระดานหมากรุกขึ้นมาสัก 2 function ครับ”
ยกตัวอย่างเช่นเรากำหนด algorithm ของ function A ไว้ว่า “ให้หยิบเอาอักษรหน้าสุดของคำมาเปลี่ยนเป็นตัวอักษร A-H จากนั้นเอาความยาวของคำมาเปลี่ยนให้เป็นเลข 1-8”
…และกำหนด algorithm B ไว้ว่า “ให้หยิบเอาอักษรสองตัวสุดท้ายมาเปลี่ยนเป็น A-H และ 1-8 ตามลำดับ”
ยกตัวอย่างเช่นคำว่า “cat” เราก็สามารถแปลงเป็นตำแหน่งในกระดานได้ 2 ตำแหน่งดังนี้ function A เปลี่ยนเป็น “C3” ในขณะที่ function B เปลี่ยนเป็น “A5” จากนั้นก็วางหมากไว้ 2 ตัวเอาไว้ในกระดานในหัว
สิ่งที่เราต้องทำก็คือเวลาใครทายคำใด ๆ ก็ตามเราก็จะเปลี่ยนคำดังกล่าวเป็นตำแหน่ง 2 ตำแหน่งในกระดาน
คราวนี้พอถึงเวลาที่เราจะต้องทายคำใหม่ เราก็แปลงคำเป็นตำแหน่งและเช็คว่าตำแหน่งนั้นมีหมากวางอยู่ไหม ถ้ามีแสดงว่าคำนั้น “เราอาจจะเคยพูดไปแล้ว ให้เปลี่ยนคำใหม่” แต่ถ้าไม่มี “เราก็พูดคำนั้น และวางหมากใหม่ลงไปในกระดาน” นั่นเอง
วิธีการจัดเก็บข้อมูลแบบนี้เราเรียกว่า “bloom filter” ครับ เป็น probabilistic data structures ตัวหนึ่ง โดย function A กับ B ก็คือ “hash function” และตารางหมากรุกก็คือ “bit array” นั่นเอง (เก็บ 0 และ 1)
จะเห็นว่าด้วยวิธีการนี้จากที่เราต้องจำคำทั้งหมด จะเหลือแค่จำกระดานหมากรุกเพียงกระดานเดียวเท่านั้น ซึ่งลดพื้นที่ที่เราต้องใช้เก็บข้อมูลได้เยอะมาก
อย่างไรก็ตาม สมมุติว่าถ้าเราจะทายคำว่า “countryseat” เราจะเปลี่ยนเป็นตำแหน่งได้ “C3” และ “A5” ซึ่งแบบเดียวกับคำว่า “cat”!!
จะเห็นได้ว่าตำแหน่งนั้นมีโอกาสที่จะซ้ำกันได้ โดยเฉพาะเวลาที่เราทายคำไปเยอะ ๆ แล้วกระดานเริ่มจะเต็ม นั่นหมายความว่าเราจะไม่มีทางพูดได้อย่างมั่นใจว่า “คำนี้เคยทายไปแล้ว!”
…เราสามารถสรุปได้แค่ว่า “คำนี้อาจจะเคยทายไปแล้วมั้ง” (maybe) กับ “ไม่เคย” (no) เท่านั้น
นั่นเป็นเหตุว่าทำไมเราถึงเรียก data structure ดังกล่าวว่า probabilistic data structures เพราะคำตอบที่ได้มามีโอกาสที่จะเป็น “false positive” นั่นเอง
นอกจากนี้การ parameters อย่างเช่นจำนวน hash functions หรือขนาดของ bit array ก็เป็นสิ่งที่เราต้องปรับให้เหมาะสมกับปัญหาที่เราจะแก้ต่อไป (เช่นถ้ามีอะไรต้องจำเยอะอาจจะต้องเปลี่ยนจากกระดานหมากรุก เป็นกระดานหมากล้อม)
