่การค้นหาข้อมูล Seaeching

บทที่ 7 
การค้นหาข้อมูล (Searching)

 เทคนิคการค้นหาข้อมูล มักเป็นโจทย์ท้าทายความสามารถให้กับนักวิทยาการคอม
พิวเตอร์ ให้มีการพัฒนาอัลกอริทึมเพื่อใช้กับการค้นหาข้อมูลได้ด้วยระยะเวลาอันสั้น ซึ่งการค้น
หาข้อมูลเป็นกระบวนการที่ใช้สำหรับค้นหาตำแหน่งข้อมูลที่ต้องการค้นหาภายในลิสต์ อัลกอริทึม
เพื่อการค้นหาขั้นพื้นฐาน ซึ่งประกอบด้วย 3 วิธีด้วยกันคือ

1.    Sequential Search
        1.1  Sentinel Search
        1.2  Probability Search
        1.3  Ordered List Search
2.     Binary Search
3.     Hashing Search

.

1 การค้นหาแบบลำดับ (Sequential  Search)

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

1. พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Successful Search)
2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)

                  พิจารณาจากรูปที่ 91 โดยในที่นี้ได้กำหนดค่า Target ที่ต้องการค้นหาคือ 14 และทำ
การค้นหาตั้งแต่ตำแหน่งแรกคือตำแหน่งที่ 1 (ดรรชนี 0) และจะค้นหาไปเรื่อย ๆ จนกระทั่งพบค่า
ที่ต้องการซึ่งก็คือตำแหน่งที่ 4 (ดรรชนี 3)  สำหรับตัวอย่างดังรูปที่ 9.1 นี้ เป็นตัวอย่างการค้นหา
ข้อมูลในลิสต์แล้วพบ
                  ในขณะที่รูปที่ 9.2 นั้น จะเป็นตัวอย่างกรณีค้นหาข้อมูลในลิสต์แล้วไม่พบ จากตัวอย่าง
ดังรูปได้มีการค้นหาค่า Target ซึ่งในที่นี้คือค่า 72 โดยได้ทำการค้นหาข้อมูลตั้งแต่ตำแหน่งแรก
จนกระทั่งถึงตำแหน่งสุดท้ายปรากฏว่าผลลัพธ์ที่ได้คือ ค้นหาข้อมูลภายในลิสต์ไม่พบ

       

 2 การค้นหาข้อมูลแบบเซนทิเนล (Sentinel Search)

                  หากมีการตรวจสอบเงื่อนไขของอัลกอริทึม Sentinel Search ในอัลกอริทึมที่ 9.1
ตรงหมายเลขลำดับชุดคำสั่งที่ 2 แล้ว จะเห็นได้ว่า ภายในลูปนั้นจะมีการตรวจสอบเงื่อนไขถึง 2
เงื่อนไขด้วยกัน ซึ่ง Donald E.Knuth ได้บัญญัติไว้ว่า “หากภายในลูปของโปรแกรมได้มีการ
ทดสอบเงื่อนไขมากกว่า 2 เงื่อนไขขึ้นไปให้พยายามลดการทดสอบเงื่อนไขลงเหลือเพียงหนึ่ง
เงื่อนไข” ดังนั้นด้วยเทคนิคของเซนทิเนล  จึงได้ทำการเพิ่มสมาชิกพิเศษ (Sentinel  Entry)
ซึ่งก็คือค่า Target ที่ไว้ตรงตำแหน่งถัดจากลำดับจากลำดับสุดท้ายของอาร์เรย์ (Last+1) เพื่อ
ใช้ควบคุมการทดสอบเงื่อนไขการวนรอบให้เหลือเพียงเงื่อนไขเดียวโดยซูโดโค้ดสำหรับการ
ค้นหาข้อมูลแบบSentinel Search

3 การค้นหาข้อมูลแบบพรอบาบิลิตี้ (Probability  Search)

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

 4 การค้นหาข้อมูลแบบออร์เดอร์ลิสต์ (Ordered List Search)

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

 5 การค้นหาข้อมูลแบบไบนารี (Binary Search)

                   การค้นหาข้อมูลแบบลำดับ  ถึงแม้จะเป็นวิธีที่เรียบง่ายไม่ซับซ้อนแต่วิธีก็เหมาะสม
กับข้อมูลที่ต้องการค้นหาที่มีปริมาณไม่มาก  เพราะว่าหากข้อมูลมีปริมาณมาก ก็ต้องเสียเวลา
ไปกับการค้นหามากขึ้นตามลำดับโดยเฉพาะตำแหน่งข้อมูลที่ต้องการค้นหานั้นอยู่ที่ท้ายลิสต์
ตัวอย่างเช่น  สมมติว่าอาร์เรย์หนึ่งมีจำนวน 1,000 สมาชิก ก็จะต้องดำเนินการเปรียบเทียบค่า
ถึง 1,000 ครั้ง ในกรณีเลวร้ายสุด ซึ่งก็คือการค้นหาข้อมูลไม่พบ หรือตำแหน่งข้อมูลที่พบอยู่ ณ
ตำแหน่งสุดท้ายพอดี

 1. ตัวแปร begin เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้นของลิสต์

2. ตัวแปร mid เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งกึ่งกลางของลิสต์
3. ตัวแปรend เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งท้ายสุดของลิสต์

Mid = [ (begin + end) / 2]

                    โดยสมมติว่ามีชุดตัวเลขที่เรียงลำดับแล้วภายในลิสต์ดังนี้ คือ {4, 7, 8, 10, 14, 21,
22,36, 62, 77, 81, 91} และค่า Target ที่ต้องการค้นหาคือค่า 22
                    เริมต้นจากการคำนวณหาตำแหน่งกึ่งกลาง ซึ่งจะได้เท่ากับ (0+11)/2=5(ให้ตัดเศษ
ทิ้ง)ดังนี้ตำแหน่งดรรชนี 5 ภายในอาร์เรย์จึงเป็นจุดกึ่งกลางที่ใช้สำหรับแบ่งกลุ่ม

                   ให้ดำเนินการนำค่า Target ไปเปรียบเทียบกับค่ากึ่งกลาง (22>21)ผลปรากฏว่าค่า
Target มีค่ามากกว่า ดังนั้นให้ละทิ้งข้อมูลที่ต้องค้นหาตั้งแต่ตำแหน่งที่ 0 ถึง 5 เป็นต้นไปเนื่องจาก
ลิสต์ส่วนดังกล่าวมีค่าน้อยกว่าค่า Target ดังนั้นจึงไม่มีความจำเป็นที่จะต้องนำมาใช้เพื่อการค้นหา
อีกต่อไปในรอบที่สอง ให้ทำการหาค่ากึ่งกลางของลิสต์ส่วนครึ่งหลัง ผลที่ได้คือตำแหน่งดรรชนี 8
ซึ่งคำนวณได้จากสูตร(6+11)/2=8 และหลังจากนั้นให้นำค่า Target มีค่าน้อยกว่า ดังนั้นให้ละทิ้ง
ข้อมูลลิสต์ส่วนครึ่งหลังตั้งแต่ตำแหน่งที่ 8 ถึง 11ออกไป

 6 การค้นหาข้อมูลแบบแฮชชิง ( Hashing  Search )

                  การค้นหาข้อมูลแบบแฮชชิงจัดเป็นวิธีการค้นหาข้อมูลที่มีประสิทธิภาพวิธีหนึ่ง โดยวิธี
นี้สามารถเข้าถึงตำแหน่งข้อมูลได้โดยตรง กล่าวคือ สามารถค้นหาตำแหน่งข้อมูลที่ต้องการได้ภาย
ในครั้งเดียว ดังนั้นประสิทธิภาพการค้นหาข้อมูลแบบแฮชชิงนั้นจึงเป็นค่าคงที่ ซึ่งก็คือ O(1)การค้น
หาข้อมูลแบบแฮชชิงนั้นจะมีคีย์เพื่อใช้เป็นตัวค้นหา ซึ่งจะนำคีน์ไปผ่านฟังก์ชันแฮชเพื่อให้ได้มาซึ่ง
ตำแหน่งของข้อมูล โดยตำแหน่งที่ได้เรียกว่า Home Address  นั้นหมายความว่า คีย์จะถูกแปลง
เป็นตำแหน่งแอดเดรสของข้อมูลที่เก็บค่าข้อมูลนั้น(key-to-address) ดังนั้นแฮชชิงจึงสามารถ
เข้าถึงตำแหน่งข้อมูลด้วยคีย์ได้ทันทีนั่นเอง พิจารณาจากรูปที่ 9.4ซึ่งเป็นรูปแสดงการนำคีย์มา
ผ่านฟังก์ชันแฮชเพื่อจะได้ตำแหน่งแอดแดรสในขณะที่รูปที่ 9.5 เป็นหลักการของแฮชชิงเพื่อแสดง
ถึงคีย์เมื่อผ่านฟังก์ชันแฮชแล้ว ก็จะได้แอดเดรสที่สามารถชี้ไปยังตำแหน่งข้อมูลในตารางแฮชภาย
ในหน่วยความจำได้ทันที

7 แนวทางการแก้ไขเมื่อมีการชนกันของคีย์   (Collision  Resolution)

                  ข้อเสียประการหนึ่งของการใช้วิธีแฮชชิงก็คือ ความเป็นไปได้ของเหตุการณ์การชน
กันของคีย์ ซึ่งเหตุการณ์ดังกล่าวสามารถเกิดขึ้นได้เสมอ และเหตุการณ์การเกิดการชนของคีย์
จะมากหรือน้อยจะขึ้นอยู่กับขนาดของตารางแฮชด้วยและรวมถึงฟังก์ชันแฮชที่ได้รับการออกแบบ
ให้มีความสามารถในการกระจายคีย์ได้อย่างสม่ำเสมอหรือไม่แต่อย่างไรก็ตาม ถึงแม้จะมีการชน
ของคีย์ แต่ก็มีวิธีการแก้ปัญหาเมื่อเกิดการชนกัน โดยประกอบด้วยวิธีหลัก ๆ 3 วิธีด้วยกันคือ วิธี
Open Addressing, Linked Listและ Buckets พิจารณาจากรูปที่ 9.7 จะเห็นได้ว่า วิธี Open
Addressing จะประกอบด้วยหลายวิธีด้วยกัน แต่อย่างไรก็ตามสำหรับวิธี Open Addressing
ในที่นี้ขอกล่าวเพียงวิธี Linear Probe เท่านั้น

  จากการศึกษาเกี่ยวกับการค้นหาข้อมูลด้วยวิธีแอชชิง จะเห็นถึงปัญหาที่เกิดขึ้นได้
จากวิธีนี้ก็คือการชนกันของคีย์ แต่ก็มีแนวทางในการแก้ไขปัญหาที่หลากหลาย ดังนั้นในการทำ
งานจริง เราสามารถนำหลายๆ วิธีข้างต้นมาประยุกต์ใช้งานร่วมกันได้ ตัวอย่างเช่น ฐานข้อมูลที่
สร้างด้วยวิธีการแฮชแบบ Bucketถ้า Bucket เต็มก็สามารถใช้วิธี Linear Probe เข้ามาแก้ไข
หรืออาจใช้วิธีลิงก์ลิสต์ก็ได้เป็นต้น

ุ