วันเสาร์ที่ 22 เมษายน พ.ศ. 2560
บทที่ 8
Searching
การค้นหาข้อมูลแบบ
Introduction
to Searching
เป็นการค้นหาข้อมูลที่มีประสิทธิภาพนั้น ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค และการค้นหาข้อมูลแบบแฮชชิง
การใช้เทคนิคการค้นหาข้อมูลแบบใดต้องดูลักษณะของงาน ซึ่งจะช่วยให้เราสามารถตัดสินใจเลือกเทคนิคการค้นหาข้อมูลที่เหมาะสมได้
วิธีการค้นหาแบบลำดับ(Sequential
Search)
การค้นหาข้อมูลแบบลำดับ
เป็นการค้นหาในลักษณะแบบเชิงเส้น เป็นวิธีที่ง่ายที่สุด
เหมาะกับการประมวลผลข้อมูลที่มีจำนวนปริมาณข้อมูลไม่มากนัก
ขันตอนในการค้นหาแบบลำดับ
1.ให้ข้อมูลตัวแรกของข้อมูลที่นำมาค้นหา
เป็นข้อมูลพิจารณา
2.นำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบว่าเท่ากับข้อมูลที่พิจารณาหรือไม่
•
ถ้าเท่ากัน
แสดงว่าพบข้อมูลตัวที่ต้องการค้นหาในตำแหน่งของข้อมูลที่พิจารณา
ซึ่งถือว่าการค้สมบูรณ์
•
ถ้าไม่เท่ากัน
ให้นำข้อมูลลำดับถัดไปจากข้อมูลที่พิจารณาไปเป็นข้อมูลที่พิจารณา แล้วกลับไปทำข้อ
2
ตัวอย่างการทำ
จากข้อมูลต่อไปนี้ จงค้นหาข้อมูล 14
ด้วยวิธีการค้นหาข้อมูลแบบลำดับ
44, 17, 40, 32, 11, 14, 28, 24
Key =
14
รอบที่ 1 key # Data[0]
↑
14#44
รอบที่ 2 key#Data[1]
↑
14
รอบที่ 3 key#Data [2]
↑
14#40
รอบที่ 4 key#Data[3]
↑
14#32
รอบที่ 5 key#Data[4]
↑
14#11
รอบที่ 6 key#Data[5]
↑
14#14
การค้นหาข้อมูลแบบทวิภาค (Binary Search)
การค้นหาข้อมูลแบบทวิภาค จะใช้สำหรับค้นหาข้อมูลที่มีการจัดเรียงลำดับแล้วเท่านั้น เพราะจะมีการนำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบกับค่าที่อยู่ตำแหน่งกึ่งกลางของข้อมูลที่นำมาค้นหา ถ้าเท่ากัน แสดงว่าพบข้อมูล แต่ถ้าไม่เท่ากันก็แสดงว่าข้อมูลตัวที่ต้องการค้นหาอยู่ส่วนก่อนหน้า หรือส่วนหลังของตำแหน่งกึ่งกลาง
ตัวแปรที่เกี่ยวข้องอยู่
3 ตัวแปร คือ
1.
ตัวแปร First
หรือ
ตำแหน่งเริ่มต้น เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้น
2.
ตัวแปร Mid
หรือ
ตำแหน่งกึ่งกลาง ใช้สำหรับกำหนดตำแหน่งกึ่งกลาง
3.
ตัวแปร Last
หรือ
ตำแหน่งสุดท้าย ใช้กำหนดตำแหน่งสุดท้ายของลิสต์
ตัวอย่าง
จากข้อมูลต่อไปนี้
จงค้นหาข้อมูล 28 ด้วยวิธีค้นหาแบบทวิภาค
11,
14, 17, 24, 28, 32, 40, 44
Key = 28 รอบที่ 1 Mid =
(First + Last) / 2 = (0+7)/2= 3
First Mid First
Key > data[mid] เพราะฉะนั้น First = [4] และ Last = [7]
11,
14, 17, 24, 28, 32, 40, 44
Key = 28
รอบที่ 2 Mid =
(First + Last) / 2
= (4+7)/2
= 5
First Mid First
Key
> data[mid] เพราะฉะนั้น
First
= [4] และ
Last
= [7]
11,
14, 17, 24, 28, 32, 40, 44
Key = 28 รอบที่ 3 Mid =
(First + Last) / 2
= (4+4)/2
= 4
First
Mid
First
Key
< data[mid] เพราะฉะนั้นพบข้อมูลที่ดรรชนี
เท่ากับ 4
การค้นหาแบบทวิภาค
สามารถปรับให้อยู่ในรูปแบบโครงสร้างต้นไม้ได้ ซึ่งจะเรียกว่า Binary
Search tree ซึ่งมีคุณสมบัติดังนี้
1.ทรีย่อยทางซ้าย หรือโหนดทางซ้ายทุกตัวต้องมีค่าน้อยกว่ารูทโหนด
2.ทรีย่อยทางขวาหรือโหนดทางขวาทุกตัวต้องมีค่ามากกว่าหรือเท่ากับรูทโหนด
3.ทุก ๆ ทรีย่อย
ต้องเป็นไบนารีเสิร์ชทรี
การค้นหาข้อมูลแบบแฮชชิง
(Hashing Search)
การค้นหาข้อมูลแบบแฮชชิง
หมายถึง การค้นหาข้อมูลที่ถูกจัดเก็บในตารางแฮช (Hash
Table) โดยการนำคีย์ข้อมูล
(Key)
ที่ต้องการค้นหาไปผ่านกระบวนแฮช (Hash
Function) เพื่อให้ทราบตำแหน่งที่ใช้ในการเก็บข้อมูล
วิธีการค้นหาข้อมูลแบบแฮชชิงมีคือ
ตารางแฮช
คือ
ตารางที่ใช้ในการเก็บข้อมูล โดยจะนำคีย์ข้อมูลไปผ่านกระบวนการแฮช
เพื่อให้ได้ตำแหน่งที่จะใช้ในการจัดเก็บข้อมูลในตารางแฮช
กระบวนการแฮช
คือ
การแปลงค่าคีย์ข้อมูลให้กลายเป็นตำแหน่งที่ใช้ในการจัดเก็บข้อมูลในตารางแฮช
ซึ่งมีหลายวิธีด้วยกัน แต่วิธีที่นิยมใช้กันมาก คือ วิธีมอดุโลดิวิชั่น (Modulo
Division) ซึ่งเป็นวิธีที่นำค่าคีย์ข้อมูลมาหารแบบมอดุโล (Modulo
: %) ด้วยขนาดของตารางที่ใช้ในการเก็บข้อมูล
โดยเศษที่เหลือจากการหาร ก็คือ ตำแหน่งที่ใช้ในการเก็บข้อมูลนั่นเอง
ต้ัออย่าง
การเก็บข้อมูลในตารางแฮช
จะมีข้อเสีย คือ มีการชนกันของข้อมูล (Collision)
กล่าวคือ
คีย์ข้อมูลต่าง ๆ เมื่อนำมาผ่านกระบวนการแฮชแล้วได้ตำแหน่งข้อมูลเดียวกัน
