บทที่ 8
Introduction
to Searching
การค้นหาข้อมูล
เป็นกระบวนการที่สำคัญในการประมวลผลข้อมูลด้วยคอมพิวเตอร์
เนื่องจากจำนวนปริมาณข้อมูลที่มีมากขึ้นและหลากหลายในปัจจุบัน ซึ่งต้องมีวิธีการจัดการที่สามารถได้ข้อมูลที่ต้องการได้อย่างรวดเร็ว
ในชีวิตประจำวันเรามีความเกี่ยวข้องกับการค้นหาข้อมูลอยู่ตลอด
เช่น การค้นหาข้อมูลผ่านเครือข่ายอินเตอร์เน็ต การค้นหาข้อมูลของเส้นทางที่สั้นที่สุดสำหรับการเดินทาง
การค้นหาข้อมูลรูปภาพที่เหมือนกัน เป็นต้น
การค้นหาข้อมูลที่มีประสิทธิภาพนั้น
ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี
เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค และการค้นหาข้อมูลแบบแฮชชิง
การใช้เทคนิคการค้นหาข้อมูลแบบใดต้องดูลักษณะของงาน
ซึ่งจะช่วยให้เราสามารถตัดสินใจเลือกเทคนิคการค้นหาข้อมูลที่เหมาะสมได้
การค้นหาข้อมูลแบบลำดับ (Sequential Search)
เป็นการค้นหาข้อมูลตั้งแต่ตัวแรก
เรื่อยไปจนกว่าจะพบข้อมูลตัวที่ต้องการค้นหา หรือถ้าค้นหาจนถึงข้อมูลตัวสุดท้ายแล้วยังไม่พบข้อมูลที่ต้องการค้นหา
แสดงว่าไม่มีข้อมูลที่ต้องการค้นหา ดังนั้น การค้นหาข้อมูลแบบลำดับ
จึงใช้สำหรับค้นหาข้อมูลที่มีจำนวนไม่มากนัก
และข้อมูลไม่จำเป็นต้องผ่านการเรียงลำดับ
การค้นหาข้อมูลแบบลำดับ
เป็นการค้นหาในลักษณะแบบเชิงเส้น เป็นวิธีที่ง่ายที่สุด
เหมาะกับการประมวลผลข้อมูลที่มีจำนวนปริมาณข้อมูลไม่มากนัก
ขั้นตอนการค้นหาข้อมูลแบบลำดับ มีดังนี้
- ให้ข้อมูลตัวแรกของข้อมูลที่นำมาค้นหา
เป็นข้อมูลพิจารณา
- นำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบว่าเท่ากับข้อมูลที่พิจารณาหรือไม่
• ถ้าเท่ากัน
แสดงว่าพบข้อมูลตัวที่ต้องการค้นหาในตำแหน่งของข้อมูลที่พิจารณา
ซึ่งถือว่าการค้นหาสมบูรณ์
• ถ้าไม่เท่ากัน
ให้นำข้อมูลลำดับถัดไปจากข้อมูลที่พิจารณาไปเป็นข้อมูลที่พิจารณา แล้วกลับไปทำข้อ
2
การค้นหาข้อมูลแบบทวิภาค (Binary Search)
วิธีการค้นหาข้อมูลแบบทวิภาค
จะใช้สำหรับค้นหาข้อมูลที่มีการจัดเรียงลำดับแล้วเท่านั้น
เพราะจะมีการนำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบกับค่าที่อยู่ตำแหน่งกึ่งกลางของข้อมูลที่นำมาค้นหา
ถ้าเท่ากัน แสดงว่าพบข้อมูล
แต่ถ้าไม่เท่ากันก็แสดงว่าข้อมูลตัวที่ต้องการค้นหาอยู่ส่วนก่อนหน้า
หรือส่วนหลังของตำแหน่งกึ่งกลาง
มีตัวแปรที่เกี่ยวข้องอยู่ 3 ตัวแปร คือ
1. ตัวแปร First
หรือ ตำแหน่งเริ่มต้น เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้น
2. ตัวแปร Mid
หรือ ตำแหน่งกึ่งกลาง ใช้สำหรับกำหนดตำแหน่งกึ่งกลาง
3. ตัวแปร Last
หรือ ตำแหน่งสุดท้าย ใช้กำหนดตำแหน่งสุดท้ายของลิสต์
- หาตำแหน่งกึ่งกลางของข้อมูล
เพื่อแบ่งข้อมูลออกเป็นสองส่วน
ตำแหน่งกึ่งกลาง = (ตำแหน่งแรก + ตำแหน่งสุดท้าย) / 2
- นำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบว่าเท่ากับค่าของตำแหน่งกึ่งกลางหรือไม่
• ถ้าเท่ากัน แสดงว่า
พบข้อมูลที่ต้องการค้นหาในตำแหน่งกึ่งกลาง ซึ่งถือว่าการ ค้นหาเสร็จสมบูรณ์
• ถ้าไม่เท่ากัน
ให้เปรียบเทียบค่าที่ต้องการค้นหามีค่ามากกว่าค่าในตำแหน่งกึ่งกลางหรือไม่
•
ถ้ามากกว่า ให้ข้อมูลที่นำมาค้นหา
คือข้อมูลทางด้านขวาของตำแหน่งกึ่งกลาง
•
ถ้ามากกว่า ให้ข้อมูลที่นำมาค้นหา
คือข้อมูลทางด้านขวาของตำแหน่งกึ่งกลาง
ตำแหน่งแรก = ตำแหน่งกึ่งกลาง
+ 1
•
ถ้าน้อยกว่า ให้ข้อมูลที่นำมาค้นหา
คือข้อมูลทางด้านซ้ายของตำแหน่งกึ่งกลาง
ตำแหน่งสุดท้าย = ตำแหน่งกึ่งกลาง
- 1
การค้นหาแบบทวิภาค
สามารถปรับให้อยู่ในรูปแบบโครงสร้างต้นไม้ได้ ซึ่งจะเรียกว่า Binary Search tree ซึ่งมีคุณสมบัติดังนี้
1.
ทรีย่อยทางซ้าย หรือโหนดทางซ้ายทุกตัวต้องมีค่าน้อยกว่ารูทโหนด
2.
ทรีย่อยทางขวาหรือโหนดทางขวาทุกตัวต้องมีค่ามากกว่าหรือเท่ากับรูทโหนด
3.
ทุก ๆ ทรีย่อย ต้องเป็นไบนารีเสิร์ชทรี
การค้นหา เริ่มต้นจะเปรียบเทียบข้อมูลทางซ้าย
แต่ถ้าข้อมูลนั้นมีค่ามากกว่าหรือเท่ากับโหนดก็ให้วิ่งไปเปรียบเทียบข้อมูลทางขวา
หากวิ่งไปถึงใบหรือลีฟโหนดแล้วไม่พบ แสดงว่าไม่มีข้อมูลนั้นอยู่
การค้นหาข้อมูลแบบแฮชชิง (Hashing Search)
การค้นหาข้อมูลแบบแฮชชิง
หมายถึง การค้นหาข้อมูลที่ถูกจัดเก็บในตารางแฮช (Hash Table) โดยการนำคีย์ข้อมูล
(Key) ที่ต้องการค้นหาไปผ่านกระบวนแฮช
(Hash Function) เพื่อให้ทราบตำแหน่งที่ใช้ในการเก็บข้อมูล
ตารางแฮช
คือ ตารางที่ใช้ในการเก็บข้อมูล โดยจะนำคีย์ข้อมูลไปผ่านกระบวนการแฮช
เพื่อให้ได้ตำแหน่งที่จะใช้ในการจัดเก็บข้อมูลในตารางแฮช
กระบวนการแฮช
คือ
การแปลงค่าคีย์ข้อมูลให้กลายเป็นตำแหน่งที่ใช้ในการจัดเก็บข้อมูลในตารางแฮช
ซึ่งมีหลายวิธีด้วยกัน แต่วิธีที่นิยมใช้กันมาก คือ วิธีมอดุโลดิวิชั่น (Modulo Division) ซึ่งเป็นวิธีที่นำค่าคีย์ข้อมูลมาหารแบบมอดุโล
(Modulo : %) ด้วยขนาดของตารางที่ใช้ในการเก็บข้อมูล
โดยเศษที่เหลือจากการหาร ก็คือ ตำแหน่งที่ใช้ในการเก็บข้อมูลนั่นเอง
ตำแหน่งข้อมูล = คีย์ข้อมูล % ขนาดของตาราง
การเก็บข้อมูลในตารางแฮช จะมีข้อเสีย คือ
มีการชนกันของข้อมูล (Collision) กล่าวคือ คีย์ข้อมูลต่าง ๆ เมื่อนำมาผ่านกระบวนการแฮชแล้วได้ตำแหน่งข้อมูลเดียวกัน
y Search)
Introduction
to Searching
ไม่มีความคิดเห็น:
แสดงความคิดเห็น