การค้นหาข้อมูล
ในบทนี้เป็นการกล่าวถึงเทคนิคในการค้นหาค่าของข้อมูล (Searching) ที่เป็นโครงสร้างซึ่งเป็นเทคนิคที่นำมาใช้กับแฟ้มข้อมูล และเมื่อพิจารณาถึงการรวบรวมเรคคอร์ด แต่ละเรคคอร์ดจะมีคีย์ที่นำมาใช้แยกแยะความแตกต่างจากเรคคอร์ดอื่น ๆ คีย์อาจประกอบด้วยฟิลด์เดียวหรือหลายฟิลด์ ค่าของคีย์อาจจะสร้างความเป็นหนึ่งเดียวให้กับเรคคอร์ดหรือเป็นแบบให้มีค่าซ้ำกันได้หลายเรคคอร์ด แต่คำนึงถึงลำดับก่อนหลังเมื่อถูกเพิ่มเข้ามา การค้นหาข้อมูลจึงเป็นกระบวนการหาตำแหน่งของเรคคอร์ดที่ต้องการตามค่าของคีย์ โดยมีอัลกอริทึมการค้นหาเป็นเทคนิคในการค้นหาเรคคอร์ดตามค่าของคีย์ซึ่งเป็นค่าที่ได้รับเข้ามาเพื่อค้นหา ในการค้นหาจะสิ้นสุดลงเมื่อพบเรคคอร์ดที่มีค่าคีย์ตรงกันหรือไม่พบ อัลกอริทึมที่นำมาใช้มีหลายแบบแต่ที่กล่าวถึง คือ
- การค้นหาแบบลำดับ (Sequential Search)
- การค้นหาแบบแบ่งครึ่ง (Binary Search)
- การค้นหาแบบสอดแทรก (Interpolation Search)
- การค้นหาข้อความ (Text Searching)
การค้นหาแบบลำดับ
การค้นหาแบบลำดับหรือการค้นหาแบบเชิงเส้น (Linear Search) มีรูปแบบที่เข้าใจง่าย เป็นการค้นหาที่จัดการกับรายการที่รวบรวมเรคคอร์ดในแบบเชิงเส้น ซึ่งสามารถจะใช้ในรูปแบบของอาร์เรย์ในรูปที่ 12.1 หรือใช้เป็นลิ้งค์ลิสต์ (Linked List)
| 5 |
90 |
70 |
68 |
93 |
73 |
24 |
91 |
84 |
9 |
66 |
3 |
72 |
81 |
15 |
63 |
รูปที่ 12.1 การค้นหาค่าของคีย์ในรูปแบบของอาร์เรย์
โดยอัลกอริทึมพื้นฐานจะเริ่มที่ตอนต้นของรายการและเปรียบเทียบค่าของคีย์ผ่านไปทีละเรคคอร์ดตามลำดับ จนกระทั่งพบค่าคีย์ของเรคคอร์ดที่ต้องการหรือไม่พบเมื่อสิ้นสุดที่ท้ายรายการ เช่น ต้องการหาค่า 72 จะต้องเปรียบเทียบค่าจากการเริ่มต้นที่ 5, 90, 70, 68, …, 3 และ 72 จึงพบว่ามีเรคคอร์ดที่ต้องการในรายการ หรือต้องการหาค่า 45 จะต้องเปรียบเทียบตั้งแค่ค่าแรก คือ 5 จนถึงค่าสุดท้ายคือ 63 จึงพบว่าไม่มีเรคคอร์ดที่ต้องการอยู่ในรายการได้อัลกอริทึมการค้นหาแบบลำดับดังในตารางที่ 12.1
ตารางที่ 12.1 อัลกอริทึมการค้นหาแบบลำดับ
1. ทำขั้นตอน 2 ซ้ำ ตั้งแต่ i = 0 จนถึง i = n-1
2. ถ้าค่า ai ในอาร์เรย์เท่ากับค่า k ที่ค้นหา ให้ส่งค่า i คืนกลับมา
3. ไม่พบส่งค่า -1 คืนกลับมา
และเขียนเป็นฟังก์ชันการค้นหาแบบลำดับได้เป็นตารางที่ 12.2
ตารางที่ 12.2 ฟังก์ชันการค้นหาแบบลำดับ
int sequentialSearch (int key[],int size, int value){
int i=0;
for(; ii] !=value; i++);
if(i<size)
return I;
return -1;
}
หลังจากที่ฟังก์ชันทำงานจบจะส่งค่าคืนกลับมาให้ ถ้าพบค่าที่ต้องการหาจะส่งตำแหน่งของคีย์ที่อยู่ในรายการกลับมาให้ แต่ถ้าไม่พบค่าที่ต้องการจะส่งค่า -1 กลับมาให้ สำหรับกรณีให้ค่าของคีย์ซ้ำกันได้ การค้นหาเรคคอร์ดจะต้องทำการเปรียบเทียบกับคีย์ของเรคคอร์ดทั้งหมดที่มีอยู่ในรายการ
อัลกอริทึมในการค้นหาแบบลำดับมีการเปรียบค่ากันที่อยู่ในออเดอร์ของ N (Order of N) โดยมีสัญลักษณ์เป็น O(n) เป็นตัวเลขของการเปรียบเทียบค่าของฟังก์ชันเชิงเส้นตามจำนวนเรคคอร์ดที่มี ถ้าจำนวนเรคคอร์ดมีมากขึ้นเป็นสองเท่า การค้นหาก็เพิ่มขึ้นเป็นสองเท่า ดังนั้นจึงไม่เหมาะที่จะใช้กับแฟ้มข้อมูลที่มีจำนวนเรคคอร์ดใหญ่มาก เช่น การหารายชื่อในสมุดโทรศัพท์
การปรับปรุงประสิทธิภาพการค้นหาแบบลำดับ
การค้นหาแบบลำดับจะมีประสิทธิภาพในการหาเรคคอร์ดที่ต้องการโดยกรณีเฉลี่ยเท่ากับ N/2 และค่าของคีย์ในแฟ้มข้อมูลไม่มีการจัดเรียงลำดับ จึงไม่เหมาะสมกับจำนวนเรคคอร์ดมาก ๆ จึงต้องมีการปรับปรุงประสิทธิภาพการค้นหาแบบลำดับโดยให้เรคคอร์ดที่ถูกค้นหาบ่อย ๆ นำไปไว้ในตอนต้นของรายการ ซึ่งมีอัลกอริทึมหลายแบบที่นำมาใช้และเพิ่มเข้าไปในอัลกอริทึมการค้นหาแบบลำดับ และมีที่นิยมนำมาใช้ คือ
1. ย้ายไว้ด้านหน้า (Move to the Front)
หลังจากที่ค้นหาคีย์ที่ต้องการพบ ก็ทำการย้ายเรคคอร์ดที่มีคีย์นั้นไปไว้ด้านหน้าของรายการ ส่วนเรคคอร์ดอื่นที่อยู่ก่อนหน้าจะขยับถอยหลังไปตามลำดับ ลักษณะการทำงานเป็นแบบ Locality Reference และเป็นแบบเดียวกับ LRU (Least Recently Used) ที่ใช้ในระบบปฏิบัติการ วิธีการนี้เหมาะกับรายการที่เป็นลิ้งค์ลิสต์มากกว่าอาร์เรย์ซึ่งไม่ต้องขยับเรคคอร์ดถอยหลัง และไม่ควรนำมาใช้กับรายการที่เรียงลำดับอยู่แล้ว อัลกอริทึมการค้นหาแบบลำดับมีการเปลี่ยนแปลงเพิ่มเติมในส่วนที่พบค่าของคีย์ได้เป็น ดังนี้
If(i<size){
Tmp=key[i];
for( ; i >0;i–)
key[i] =key[i-1];
key[0] =tmp;
return 0;
}
- การสลับตำแหน่ง (Transposition)
หลังจากที่ค้นหาคีย์ที่ต้องการพบ ก็ทำการย้ายเรคคอร์ดที่มีคีย์นั้นสลับกับเรคคอร์ดที่อยู่ก่อนหน้าหนึ่งตำแหน่ง นำมาใช้กับเรคคอร์ดที่ถูกค้นหาบ่อยและค่อย ๆ ขยับไปด้านหน้าตามช่วงระยะเวลา อัลกอริทึมมีการเปลี่ยนแปลงเพิ่มเติมในส่วนที่พบค่าของคีย์ได้เป็น ดังนี้
If (I <size){
Tmp=key[i];
For (; I > 0; i–)
Key[i]=[i];
Key[0]=tem;
Return 0;
}
- นับจำนวนการค้นหา (Counting)
เป็นการกำหนดจำนวนการถูกค้นหาให้แต่ละเรคคอร์ด จากนั้นทำการย้ายไปยังตำแหน่งตามลำดับของจำนวนการค้นหาจากมากไปน้อย แฟ้มข้อมูลที่ได้จะจัดเรียงลำดับเรคคอร์ดตามจำนวนค้นหาไม่ใช่ค่าของคีย์ หรือกำหนดจำนวนเป็นค่าความน่าจะเป็นให้แต่ละเรคคอร์ดและเรียงลำดับจากค่ามากไปน้อย สำหรับการค้นหาโดยใช้วิธีนี้จะต้องมีการจัดเก็บค่าจำนวนที่ถูกค้นหาหรือค่าความน่าจะเป็นให้แต่ละเรคคอร์ดเพิ่มเข้ามา
แฮชชิ่ง
การค้นหาแบบลำดับและแบบแบ่งครึ่งจะค้นหาโดยใช้การเปรียบเทียบ ในกรณีเฉลี่ยของการค้นหาแบบลำดับมีการเปรียบเทียบค่าเท่ากับ O(n) ขณะที่การค้นหาแบบแบ่งครึ่งเท่ากับ O(log2 n) และบางสถานการณ์อัลกอริทึมทั้งสองจะทำงานช้า เพื่อให้มีความรวดเร็วจึงนำโครงสร้างข้อมูลตารางแฮช (Hash Table) มาใช้ในการค้นหาตำแหน่งของเรคคอร์ดที่ต้องการได้โดยตรง ซึ่งจะใช้ฟังก์ชันแทนการค้นหาตามลำดับและเปรียบเทียบ ดังนั้น เวลาที่ต้องใช้ค้นหาค่าในตารางแฮชจะเท่ากับ O(1) ซึ่งเป็นค่าคงที่และไม่ขึ้นกับจำนวนค่าว่ามีมากเท่าไร
สมมุติให้มี 25 เรคคอร์ดและค่าของคีย์เป็นตัวเลขในช่วงระหว่าง 0 ถึง 999 เก็บไว้ในตารางแฮชซึ่งกำหนดเป็นอาร์เรย์ Table มีดัชนี 0..999 โดยให้แต่ละสมาชิกมีค่าเริ่มต้นเท่ากับ -1 ถ้าให้ค่าของคีย์ที่ i เป็นดัชนี การเก็บค่าจะไว้ที่ Table[i] และตรวจสอบหาค่าของคีย์ Number ว่าอยู่ในตารางแฮชหรือไม่โดยใช้ Table[Number] = Number ในการทำงานจะใช้ฟังก์ชัน h และกำหนดเป็น h(i) = i เพื่อหาตำแหน่งค่าของคีย์ในตารางแฮช เรียกว่า แฮชฟังก์ชัน (Hash Function) แฮชฟังก์ชันจะทำการแมพ (Map) ค่าของคีย์ไปยังตำแหน่งในตารางแฮชในลักษณะหนึ่งต่อหนึ่ง ซึ่งเวลาที่ใช้ค้นหาเพียงครั้งเดียวและได้ตำแหน่งเดียว จากลักษณะดังกล่าวจะมีข้อเสียในเรื่องใช้พื้นที่สิ้นเปลือง เนื่องจากต้องสำรองพื้นที่ไว้เก็บ 100 ค่าในตารางแฮชในขณะที่ใช้พื้นที่เก็บเพียง 25 ค่า
มีความเป็นไปได้ที่จะเก็บทั้ง 25 ค่าในตารางแฮชที่ใช้พื้นที่เพียง 25 ตำแหน่งเพื่อให้เกิดประโยชน์โดยกำหนดอาร์เรย์ Table มีดัชนี 0..24 และกำหนดให้แฮชฟังก์ชันเป็น h(i) = i mod 25 ซึ่งทำการแมพค่าของคีย์ในช่วง 0 ถึง 999 ให้อยู่ในช่วง 0 ถึง 24 ดังในรูปที่ 12.6 เช่น เก็บค่าของคีย์ 52 อยู่ในตำแหน่งที่ 2 (52 mod 25) และเก็บค่า 129, 500, 273, 49 อยู่ในตำแหน่งที่ 4, 0, 23, 24 ตามลำดับ
|
Table[0] Table[23] 500 |
|
-1 |
|
52 |
|
-1 |
|
129 |
|
-1 |
|
. |
|
273 |
|
49 |
รูปที่ 12.6 การใช้แฮชฟังก์ชันเก็บค่าลงในตารางแฮช
อย่างไรก็ตามจะมีปัญหาเกิดขึ้นจากการแมพค่าของคีย์ไปยังตำแหน่งในตารางแฮชไม่เป็นแบบหนึ่งต่อหนึ่ง ทำให้ค่าของคีย์หลายค่าได้ตำแหน่งเดียวกันในตารางแฮช เรียกว่า การชนกัน (Collision) เช่น เก็บค่าของคีย์ 77 จะได้ตำแหน่งที่ 2 ซึ่งมีค่า 52 เก็บอยู่แล้ว หรือค่าอื่น ๆ คือ 2, 27, 102 อย่างไรก็ตามการใช้แฮชฟังก์ชันแบบหลังยังคงเหมาะสมกว่าการใช้แบบแรกที่ต้องเสียพื้นที่ไม่ได้ใช้งานและมีวิธีการแบบต่าง ๆ ที่นำมาช่วยแก้ไขปัญหาการชนกันสำหรับแฮชฟังก์ชันก็ต้องมีวีการกระจายค่าเพื่อให้เกิดการชนกันน้อยที่สุดโดยใช้วิธีการแบบต่าง ๆ ซึ่งจะกล่าวถึง คือ
- การหารเหลือเศษ (Division-remainder)
- ค่ากลาง-ยกกำลังสอง (Mid-square)
- การพับทบกัน (Folding)
การหารเหลือเศษ
การใช้แฮชฟังก์ชันที่รู้จักกันดีและเป็นหลักการง่าย ๆ คือการหารเหลือเศษ ดังในตัวอย่างที่ผ่านมา เป็นการนำค่าของคีย์มาหารด้วยค่าตัวเลขหนึ่ง จากนั้นนำค่าที่เป็นเศษเหลือมาใช้เป็นตำแหน่งในตารางแฮช และต้องรับรองว่าค่าที่ได้เป็นตำแหน่งที่อยู่ในตาราง ดังนั้น ตัวหารจึงใช้เป็นขนาดของตารางแฮชได้เป็น ดังนี้
h(K) = K mod TableSize
นอกจากนี้อาจกำหนดตัวหารเป็นค่าอื่นเพื่อให้มีความเหมาะสมและช่วยแก้ไขปัญหาชนกัน คือ ใช้ตัวหารที่เป็นเลข Prime Number หรือใช้เลขที่ไม่ใช่ Prime Number ก็ทำงานได้เท่ากันแต่ต้องไม่เป็นเลข Prime Number ที่ค่าน้อยกว่า 20 มีอยู่ และหารใช้เลขคู่เป็นตัวหารจะทำให้การดำเนินการแย่ลง เช่น แฟ้มข้อมูลหนึ่งมี 4,000 เรคคอร์ด พื้นที่ในตารางแฮชต้องมีอย่างน้อย 5,000 ตำแหน่งสำหรับโหลดแฟกเตอร์ (Load Factor) 80 เปอร์เซ็นต์ (4000/5000) ดังนั้น ตัวหารจะอยู่ประมาณ 5,000 และไม่เป็นเลข Prime Number ที่น้อยกว่า 20 ก็คือ 5,003 และได้แฮชฟังก์ชันเป็น K mod 5003 ดังในรูปที่ 12.7
|
คีย์ |
ตำแหน่งในตารางแฮช |
|
123456789 ชนกัน 555555555 |
2762 2086 2763 2424   04734184 0473 0474 4606 3613 |
รูปที่ 12.7 ตัวอย่างแฮชฟังก์ชันที่มีตัวหารเท่ากับ 5003
ค่าตรงกลางยกกำลังสอง
เป็นการนำค่าของคีย์ยกกำลังสอง จากนั้นนำค่าที่อยู่ช่วงตรงกลางออกมาได้เป็นตำแหน่งในตารางแฮช ถ้าตำแหน่งในตารางเป็นเลขจำนวน n หลักก็ดึงค่าช่วงตรงกลางออกมา n ตัวที่ห่างจากซ้ายขวาเท่ากัน ดังในรูปที่ 12.8
|
คีย์ |
ค่ายกกำลังสอง |
ตำแหน่งในตารางแฮช |
|
123456789 |
15241578750190521 ชนกัน 308641974691358025 |
8750 5789 8997 4691   00000719 3313 3713 0000 1600 |
รูปที่ 12.8 ตัวอย่างแฮชฟังก์ชันที่ใช้ค่าตรงกลาง-ยกกำลังสอง
จากการจัดเก็บ 4,000 เรคคอร์ดในตัวอย่างที่กล่าวมาใช้ตำแหน่งเป็นเลข 4 หลัก ดังนั้นจะได้พื้นที่ในตารางแฮชเท่ากับ 10,000 ค่าและมีโหลดแฟกเตอร์เท่ากับ 0.4 (4000/10000๗ การนำค่าตรงกลาง-ยกกำลังสองมาใช้ขนาดของตารางแฮชที่ได้จะเป็น 10n ซึ่ง n เป็นจำนวนหลักที่ดึงออกมาจากตรงกลางค่าของคีย์ยกกำลังสอง
การพับทบกัน
เป็นการนำค่าของคีย์แบ่งออกเป็นส่วน ๆ โดยแต่ละส่วนจะมีจำนวนหลักเท่ากับจำนวนหลักของตำแหน่งในตารางแฮช จากนั้นนำมาพับทบรวมกันและบวกค่าเข้าด้วยกัน ถ้าตัวเลขที่ได้มีจำนวนหลักเกินทางซ้ายให้ตัดทิ้งไปโดยการหารเหลือเศษ (Divide Modulo) ด้วยขนาดของตารางแฮช ก็จะได้ตำแหน่งในตารางแฮช การพับทบกันเพื่อบวกค่าแบ่งออกได้เป็น 2 ลักษณะ คือ
1. การพับทบกันแบบแบ่งเขต (Boundary Folding) เป็นการแบ่งส่วนเป็นเขตตามจำนวนหลักและพับเข้าหากัน เช่น ค่าของคีย์ 123456789 แบ่งเขตละ 4 หลักได้ส่วนแรกเป็น 1 ส่วนที่สองเป็น 2345 และส่วนที่สามเป็น 6789 เมื่อพับเข้าหากันได้เป็น ดังนี้
| 1 |
| 2345 |
| 9876 |
และบวกกันก็จะได้ตำแหน่งในตารางแฮชเท่ากับ 3221 (13221 mod 10000)
2. การพับทบกันแบบเลื่อนลง (Shift Folding) เป็นการแบ่งส่วนตามจำนวนหลักและเลื่อนลงมาไว้ด้านล่างเพื่อบวกกัน เช่น ค่าของคีย์ 123456789 แบ่งตามแบบที่แล้ว เมื่อเลื่อนลงมาไว้ด้านล่างได้เป็น ดังนี้
| 1 |
|
2345 |
|
6789 |
และบวกกันก็จะได้ตำแหน่งในตารางแฮชเท่ากับ 9135 (9135 mod 10000)
เมื่อใช้การพับทบกันแบบแบ่งเขตจะได้ตำแหน่งในตารางแฮชดังในรูปที่ 12.9 และเช่นเดียวกับค่าตรงกลาง-ยกกำลังสอง ขนาดของตารางแฮชที่ได้จะเป็น 10 n เหมือนกัน
|
คีย์ |
ตำแหน่งในตารางแฮช |
|
123456789 |
3221 8999 4321 6110  2740 |
ชนกัน ชนกัน
4820
4752
5752
2740
2740
รูปที่ 12.9 ตัวอย่างแฮชฟังก์ชันที่ใช้การพับทบกันแบบแบ่งเขต
นอกจากวิธีการแมพของแฮชฟังก์ชันที่ได้กล่าวมาแล้วยังมีอีกหลายวิธี เช่น วิธีการดึงบางค่าออกมา (Extraction) เป็นการนำค่าเฉพาะบางส่วนมาใช้เป็นตำแหน่งในตารางแฮช เช่น ค่าของคีย์ 123456789 ใช้สี่ตัวแรกได้เป็น 1234 ใช้สี่ตัวหลังได้เป็น 6789 และอาจนำมาประกอบกันโดยใช้สองตัวแรกรวมกับสองตัวหลังได้เป็น 1289 หรือในรูปแบบอื่น ๆ แต่ต้องหลีกเลี่ยงการนำตัวเลขที่ซ้ำเหมือนกันในทุก ๆ ค่าของคีย์มาใช้ เช่น รหัสนักศึกษาที่มีปี พ.ศ. ซึ่งเป็นตัวเลขมีอยู่ในทุกคีย์ ถ้านำมาใช้รวมอยู่ด้วยทำให้โอกาสการชนกันมีมาก
การแปลงเลขฐาน (Radix Transformation) เป็นอีกวิธีหนึ่งโดยการแปลงค่าของคีย์ให้อยู่ในเลขฐานอื่นและใช้เป็นตำแหน่งในตารางแฮช เช่น ค่าของคีย์ 345 ในเลขฐานสิบแปลงเป็นเลขฐานเก้า (Nonal) ได้เป็น 423 จากนั้นทำการหารเหลือเศษด้วยขนาดของตารางแฮช
การแก้ปัญหาชนกัน
เนื่องจากแฮชฟังก์ชันทำการแมพค่าของคีย์จากพื้นที่ขนาดใหญ่ไปเป็นพื้นที่ตำแหน่งในตารางแฮชขนาดเล็กทำให้เกิดการชนกันที่มีค่ามากกว่าหนึ่งอ้างไปยังตำแหน่งเดียวกัน การแก้ไขอาจใช้แฮชฟังก์ชันที่สามารถกระจายค่าไม่ให้ชนกันหรือเพิ่มขนาดตารางแฮชให้มากขึ้น แต่ก็ช่วยลดให้น้อยลงเท่านั้นจึงมีเทคนิคที่นำมาใช้แก้ปัญหาชนกันหลายวิธีซึ่งจะกล่าวถึง คือ
- การเปิดแอดเดรส (Open Addressing)
- การต่อเป็นลูกโซ่ (Chaining)
- การใช้พื้นที่บักเก็ต (Bucket Addressing)
การเปิดแอดเดรส
เป็นวิธีแบบหนึ่งซึ่งเมื่อใดมีการชนกันก็จะไปค้นหาตำแหน่งอื่นในตารางแฮชที่ยังว่างอยู่เพื่อเก็บค่าที่ชนกัน โดยมีหลักการแบบง่าย ๆ เรียกว่า การตรวจหาเชิงเส้น (Linear Probing) ซึ่งทำการค้นหาเรียงตามลำดับที่เริ่มจากตำแหน่งถัดไปจากตำแหน่งที่ชนกันไปเรื่อย ๆ จนกว่าพบตำแหน่งว่างให้เก็บค่า หากถึงตำแหน่งสุดท้ายแล้วยังไม่พบก็จะไปหาต่อที่ตำแหน่งแรกในตาราง และการทำงานสิ้นสุดลงเมื่อพบตำแหน่งว่างหรือหาต่อจนกลับมายังตำแหน่งที่ชนกันซึ่งหมายถึง ตารางเก็บค่าเต็มไม่มีตำแหน่งว่าง ขั้นตอนการทำงานดังตัวอย่างในรูปที่ 12.10
คีย์ คีย์ คีย์
(a) (b) (c)
รูปที่ 12.10 ตัวอย่างการใช้แฮชฟังก์ชันกับการตรวจหาเชิงเส้น
เป็นการใช้แฮชฟังก์ชัน h(K) = K mod 11 และมีค่าของคีย์เพิ่มเข้ามาตามลำดับ คือ 27, 18, 29, 28, 39, 13, และ 16 โดยในรูป (a) เก็บค่า 27, 18, 29 ที่ตำแหน่ง 5 และ 7 เนื่องจากค่า 29 ชนกับ 18 จึงหาตำแหน่งว่างถัดไปได้ที่ตำแหน่ง 8 ในรูป (b) เพิ่มค่า 28, 39 เก็บที่ตำแหน่ง 6 แต่ค่า 39 ชนกันกับ 28 จึงตรวจหาได้ที่ตำแหน่ง 9 ในรูป (c) เพิ่มค่า 13 เก็บที่ตำแหน่ง 2 ส่วนค่า 16 ชนกับ 27 จึงตรวจหาไปเรื่อย ๆ ตามลำดับจนเก็บที่ตำแหน่ง 10 เก็บที่ตำแหน่ง 2 ส่วนค่า 16 ชนกับ 27 จึงตรวจหาไปเรื่อย ๆ ตามลำดับจนเก็บที่ตำแหน่ง 10
อีกหลักการ คือ ดับเบิ้ลแฮชชิ่ง (Double Hashing) หรือแฮชชิ่งซ้ำ (Rehashing) หรือผลหารเชิงเส้น (Linear Quotient Hashing) หลังจากที่ทำการแฮชชิ่งในครั้งแรกถ้ามีการชนกันอีกให้มีการแฮชชิ่งครั้งที่สองจนกว่าพบตำแหน่งว่างเพื่อเก็บค่าที่ชนกัน ดังนี้
h(K) = (current position + increment) mod TableSize
จากตัวอย่างที่แล้วเมื่อใช้กับดับเบิ้ลแฮชชิ่งได้เป็นรูปที่ 12.11 โดยแฮชฟังก์ชันครั้งแรกใช้ h1(K) = K mod 11 และครั้งที่สองใช้ h2(K) = (current position + (K/11) mod 11
คีย์ คีย์ คีย์
รูปที่ 12.11 ตัวอย่างการใช้แฮชฟังก์ชันกับดับเบิ้ลแฮชชิ่ง
การทำงานเป็นแบบเดียวกับตัวอย่างที่แล้วแต่เมื่อเกิดการชนกันจะใช้แฮชฟังก์ชันครั้งสองแทนการตรวจหา โดยในรูป (a) ค่า 29 ชนกับ 18 ที่ตำแหน่ง 7 จึงใช้แฮชฟังก์ชันครั้งที่สอง (7 + (27/11)) mod 11 ได้ตำแหน่ง 9 ในรูป (b) ค่า 39 ชนกับ 28 จึงใช้แฮชฟังก์ชัน ครั้งที่สอง (6 + (39/11)) mod 11 ได้ตำแหน่ง 9 แต่ก็ชนกันอีกจึงใช้แฮชฟังก์ชันครั้งที่สอง (9 + (39/11)) mod 11 ได้ตำแหน่ง 1 ในรูป (c) ค่า 16 ชนกับ 27 จึงใช้แฮชฟังก์ชันครั้งที่สอง (5 + (16/11)) mod 11 ได้ตำแหน่ง 6 แต่ยังชนกันจึงใช้แฮชฟังก์ชันครั้งที่สองอีกก็ยังชนกันที่ตำแหน่ง 7 เมื่อใช้แฮชฟังก์ชันครั้งที่สองอีกครั้งจึงได้ตำแหน่ง 8 ที่สามารถเก็บค่าได้
การต่อเป็นลูกโซ่
เป็นวิธีการที่ค่าของคีย์ไม่ได้เก็บในตารางแฮช แต่ละตำแหน่งในตารางจะเป็นตัวชี้ (Pointer) ไปยังลิ้งค์ลิสต์หรือลูกโซ่ของเรคคอร์ดที่เก็บค่าของคีย์ไว้ หลักการนี้ เรียกว่า การต่อเป็นลูกโซ่แยกกัน (Separate Chaining) และตารางที่ใช้เป็นตัวชี้ เรียกว่า ตารางกระจาย (Scatter Table) ดังนั้น การเก็บค่าจะไม่เกิดการล้น (Overflow) เมื่อมีค่าใหม่เข้ามาและชนกันก็เพียงแต่ต่อขยายลิ้งค์ลิสต์ให้ยาวขึ้น ดังในรูปที่ 12.12 เป็นการเก็บค่าของคีย์จากตัวอย่างที่ผ่านมา
รูปที่ 12.12 การเก็บค่าในตารางแฮชโดยการต่อเป็นลูกโซ่
อีกวิธีหนึ่งของการต่อเป็นลูกโซ่ เรียกว่า แฮชชิ่งต่อรวมกัน (Coalesced Hashing) หรือลูกโซ่ต่อรวมกัน (Coalesced Chaining) เป็นการนำวิธีการตรวจหาเชิงเส้นมาใช้ร่วมกับการต่อเป็นลูกโซ่ การทำงานเป็นแบบเดียวกับการตรวจหาเชิงเส้น เมื่อใดที่มีการชนกันก็จะนำค่าที่ชนไปไว้ที่ตำแหน่งว่างในตอนท้ายของตารางและสร้างตัวเชื่อมระหว่างค่าที่ชนกันโดยมีตัวชี้เพิ่มเข้ามาในตารางแฮช วิธีการนี้ช่วยให้การหาค่าได้เร็วขึ้นไม่ต้องหาแบบเรียงตามลำดับ จากตัวอย่างที่แล้วเมื่อใช้แฮชชิ่งต่อรวมกันได้เป็นดังรูปที่ 12.13
รูปที่ 12.13 การเก็บค่าในตารางแฮชแบบแฮชชิ่งต่อรวมกัน
จากตัวอย่างตารางแฮชจะเพิ่มส่วนที่เป็นตัวชี้เข้ามาและใช้เมื่อมีการชนกัน ถ้ามีค่าชนกันมากตัวชี้ก็จะเชื่อมต่อกันไปเรื่อย ๆ เป็นลูกโซ่และสิ้นสุดที่ค่าสุดท้ายซึ่งมีตัวชี้เป็นค่า Null วิธีการแฮชชิ่งต่อรวมกันมีข้อจำกัดในเรื่องจำนวนค่าที่เก็บในตารางจึงเปลี่ยนมาใช้พื้นที่ส่วนล้น (Overflow Area) เรียกว่า เซลลาร์ (Cellar) เพิ่มเข้ามาใช้เก็บค่าที่ชนกันดังในรูปที่ 12.14
รูปที่ 12.14 การใช้แฮชชิ่งต่อรวมกันที่มีพื้นที่ส่วนล้น
การใช้พื้นที่บักเก็ต
แนวทางหนึ่งในการแก้ปัญหา คือ นำค่าที่ชนกันมารวมในตำแหน่งเดียวกันในตารางแฮชแต่ละตำแหน่ง เรียกว่า บักเก็ต (Bucket) เป็นพื้นที่บล็อกที่สามารถเก็บได้หลาย ๆ ค่า ดังในรูปที่ 12.15 โดยแต่ละตำแหน่งจะมีบักเก็ตเก็บได้สองค่า
รูปที่ 12.15 การเก็บค่าในตารางแฮชที่ใช้เป็นบักเก็ต
การใช้บักเก็ตไม่สามารถแก้ปัญหาการชนกันได้ทั้งหมด ถ้าบักเก็ตเก็บค่าเต็มก็ต้องไปหาตำแหน่งว่างให้กับค่าที่เพิ่มเข้ามา แนวทางการแก้ไขอาจใช้การเปิดแอดเดรสโดยการตรวจหาเชิงเส้นค้นหาตำแหน่งว่างในบักเก็ตที่อยู่ถัดไป หรือใช้พื้นที่ส่วนล้นเพิ่มเข้ามาเก็บค่าที่ล้นบักเก็ตเช่นเดียวกับการใช้แฮชชิ่งต่อรวมกันและและมีตัวชี้เชื่อมถึงกัน
ทรีค้นหาหลายทาง
จากที่ผ่านมาได้กล่าวถึงไบนารี่เสิร์ชทรีโดยค่าของคีย์ในทรีย่อยด้านซ้ายมีค่าน้อยกว่าค่าที่อยู่ในทรีและค่าในทรีย่อยด้านขวามีค่ามากกว่าค่าที่อยู่ในทรี เมื่อมีการเพิ่มเติมข้อกำหนดและการทำงานมากขึ้น เรียกว่า ทรีค้นหาหลายทาง (Multiway Search Tree) ซึ่งแต่ละโหนดจะมีทรีย่อยได้มากกว่าสอง และมีค่าของคีย์มากกว่าหนึ่งค่า ดังในรูปที่ 12.16 โดยแต่ละโหนดมีคุณสมบัติดังต่อไปนี้
รูปที่ 12.16 โครงสร้างโหนดในทรีค้นหาหลายทาง
1. ค่าของคีย์ k มีจำนวนเท่ากับ d-1 ที่แยกทรีย่อย T จำนวน d ซึ่งเป็นดีกรี (Degree) ของทรีค้นหาหลายทาง
2. ค่าของคีย์ k จะเรียงลำดับจากค่าน้อยไปหาค่ามาก (Ascending) มีจำนวน d-1 (K0 < K1 < K2 < … < Kd-2)
3. ลำดับของทรีย่อยมีจำนวน d (T0, T1, T2, …, Td-1) ที่ถูกอ้างถึงด้วยตัวชี้ (P0, P1, P2, …, Pd-1)
4. ค่าของคีย์ที่อยู่ใน Ti มีค่าน้อยกว่าค่าของ ki สำหรับ i = 0, 1, 2, …, d-2
5. ค่าของคีย์ที่อยู่ใน T d-1 มีค่ามากกว่าค่าของ k d-2
ทรีค้นหาหลายทางบางครั้ง เรียกว่า ทรีค้นหา M ทาง (M-way Search Tree) เมื่อให้ d = m และแต่ละโหนดมีดีกรี £ m ดังในรูปที่ 12.17 เป็นทรีค้นหา 4 ทางที่ m = 4 โดยแต่ละโหนดมีดีกรี 4, 3, 2 จึงมีช่วงดีกรีตั้งแต่ 2 ถึง 4 มีจำนวนค่าของคีย์ทั้งหมด 17 ค่ากับ 8 โหนด และจะเห็นว่าทรีค้นหา 2 ทาง คือ ไบนารี่เสริ์ชทรี ถ้าต้องการหาค่าของคีย์ 65 จะเริ่มต้นที่รูทโหนด a เมื่อสแกนหาค่าพบว่ามีค่าน้อยกว่า 85 จึงวิ่งลงมายังโหนด d และสแกนพบว่ามีค่าน้อยกว่า 70 จึงวิ่งต่อลงมายังโหนด g และสแกนพบว่ามีอยู่ในโหนดนี้
รูปที่ 12.17 ตัวอย่างทรีค้นหา 4 ทาง มีช่วงดีกรี 2-4
เมื่อนำทรีค้นหาหลายทางมาใช้เป็นดัชนี จากแต่ละโหนดที่มีค่าของคีย์กับตัวชี้อ้างไปยังทรีย่อยก็จะเพิ่มตัวชี้อ้างไปยังตำแหน่งหรือแอดเดรสของเรคคอร์ดที่มีค่าของคีย์นั้น ดังในรูปที่ 12.18
รูปที่ 12.18 โครงสร้างโหนดที่ใช้เป็นดัชนี
กระบวนการค้นหาค่าของคีย์ในทรีค้นหา M ทางมีลักษณะเช่นเดียวกับกระบวนการการค้นหาในไบนารี่เสริ์ชทรี สิ่งที่แตกต่างกันคือ ค่าของคีย์เก็บเป็นอาร์เรย์จำนวน d-1 ค่าในแต่ละโหนดจึงต้องสแกนหา ถ้าพบค่าของคีย์ที่ต้องการก็ใช้ตัวชี้ Ai อ้างไปยังเรคคอร์ด ไม่เช่นนั้นใช้ตัวชี้ Pi อ้างไปยังทรีย่อยในระดับล่างลงมา
บีทรี
โดยส่วนใหญ่โปรแกรมฐานข้อมูล (Database Program) จัดเก็บสารสนเทศบนดิสก์หรือเทป แต่มีอุปสรรคในเรื่องของเวลาการเข้าถึงข้อมูลไปยังอุปกรณ์จัดเก็บข้อมูลสำรอง (Secondary Storage) ซึ่งสามารถลดลงได้โดยเลือกใช้โครงสร้างข้อมูลที่เหมาะสม และแนวทางหนึ่งคือ ใช้บี-ทรี ที่คิดค้นโดย R. Bayer และ E. McCreight มีลักษณะการทำงานจะใกล้ชิดกับอุปกรณ์จัดเก็บสำรอง คุณสมบัติสำคัญอย่างหนึ่ง คือ ขนาดของแต่ละโหนดสามารถใหญ่เท่ากับขนาดของบล็อก ซึ่งอาจมีขนาด 512 ไบต์ 4 เคไบต์หรือมากกว่านั้นขึ้นกับระบบที่ใช้งาน บี-ทรีเมื่อมีดีกรี m เป็นทรีค้นหาหลายทางจะมีคุณสมบัติ ดังนี้
1. รูทโหนดจะต้องมีทรีย่อยอย่างน้อย 2 โหนด ยกเว้นเมื่อรูทโหนดเป็นโหนดปลายด้วย
2. โหนดภายใน (Internal Node) ที่ไม่ใช่รูทโหนดและโหนดปลาย มีค่าของคีย์จำนวน k-1 ค่าและตัวชี้จำนวน k ตัวเพื่ออ้างไปยังทรีย่อย โดยที่ é m/2ù £ k £ m
3. โหนดปลายมีค่าของคีย์จำนวน k-1 ค่า โดยที่ êm/2 ù £ k £ m
4. โหนดปลายทั้งหมดต้องอยู่ระดับ (Level) เดียวกัน
จากคุณสมบัติดังกล่าวเพื่อรับประกันว่าแต่ละโหนดเก็บค่าของคีย์ไม่น้อยกว่าครึ่งของทั้งหมด ความสูงของทรีมีระดับไม่มาก และบี-ทรีเป็นทรีสมดุล ต่างจากไบนารี่เสิร์ชทรีและทรีค้นหาหลายทางที่ไม่สมดุล ส่วนทรีเอวีแอล (AVL Tree) ก็เป็นการแก้ปัญหาความไม่สมดุลแบบบนลงล่าง (Top-Down) โดยการหมุนทรีให้ความสูงของทรีย่อยใกล้เคียงกันมากที่สุดและมีค่าใช้จ่ายสูง สำหรับบี-ทรีจะแก้ปัญหาแบบล่างขึ้นบน (Button-Up) โดยเริ่มที่โหนดปลายกลับขึ้นไปยังรูทโหนด มีการปฏิบัติงานแยกโหนดที่เต็มเป็นสอง โหนดและการรวมโหนดว่างเข้าไว้ด้วยกัน มีค่าใช้จ่ายและการดำเนินการน้อยกว่าในการดูแลจัดการกระบวนการเพิ่มและลบค่าของคีย์ จากตัวอย่างในรูปที่ 12.17 จึงไม่ใช่บี-ทรีเมื่อเปลี่ยนเป็นบี-ทรีได้เป็นดังในรูปที่ 12.19 ถ้าหากนำบี-ทรีใช้เป็นดัชนี แต่ละโหนดจะมีตัวชี้เพิ่มเข้ามาใช้อ้างไปยังตำแหน่งหรือแอดเดรสของเรคคอร์ดในแต่ละค่าของคีย์ที่มีอยู่ ซึ่งไม่ได้แสดงในรูป
รูปที่ 12.19 ตัวอย่างบี-ทรี ดีกรีเท่ากับ 4
การค้นหาแต่ละค่าของคีย์ในบี-ทรีเป็นการทำงานแบบเดียวกับการค้นหาหลายทาง แต่การดำเนินการค้นหาของบี-ทรีเป็นอย่างไร โดยพิจารณาจากจำนวนค่าของคีย์ที่น้อยที่สุด n ค่าในบี-ทรีที่มีดีกรี m และมีความสูง h จะถูกจำกัดขอบเขต ดังนี้
2 é m/2ù h -1 £ n £ m h+1 -1
ความสูง h ของบี-ทรีที่มีจำนวนค่าของคีย์ n และมีดีกรี m จะถูกจำกัดขอบเขตดังนี้
h £ Log m/2 (n+1)/2 + 1 = O(Log n)
ดังนั้น เวลาที่ใช้ในการค้นหาเป็นลอกการิทึม โดยที่โหนดปลายจะอยู่ในระดับสูงสุด คือ ที่ h-1 ความสูงของบี-ทรี จึงนำมาใช้พิจารณาถึงความยาวมากที่สุดในการค้นหา และเหมาะสมที่จะนำมาใช้กับการค้นหาโดยตรง จำนวนในการอ่านดิสก์ที่ต้องการเข้าถึงเรคคอร์ดจึงไม่มากกว่า h+2
บี-ทรีเป็นโครงสร้างข้อมูลมาตรฐานที่ทำงานเป็นดัชนีภายนอกสำหรับตารางฐานข้อมูลโดยแต่ละค่าของคีย์จะมีตำแหน่งหรือแอดเดรสของเรคคอร์ดที่มีค่าของคีย์นั้นรวมอยู่ด้วย ดีกรีของบี-ทรีจะถูกกำหนดให้แต่ละโหนดเพื่อสามารถจัดเก็บข้อมูลในหนึ่งดิสก์บล็อก นอกจากนี้ยังมีการเปลี่ยนแปลงโครงสร้างบี-ทรีเป็นหลายรูปแบบเพื่อให้มีประสิทธิภาพมากขึ้น แต่ยังอยู่ภายใต้พื้นฐานบี-ทรีที่พัฒนาขึ้นมาใช้งาน เช่น
บี*-ทรี (B*-Tree)
เป็นโครงสร้างข้อมูลที่กำหนดขึ้นมาโดย Donald Knuth โดยกำหนดให้ทุกโหนดยกเว้นรูทโหนดจะต้องมีจำนวนค่าของคีย์อย่างน้อยสองในสามแทนที่จะเหลือครึ่งหนึ่งในแบบบี-ทรี ดังนั้น บี*-ทรีที่มีดีกรี m จะมีจำนวนค่าของคีย์เป็น é(2m-1)/3ù £ n £ m-1 ทำให้บี*-ทรีถ่วงเลาการแยกโหนดให้ช้าลงเมื่อมีการเก็บค่าล้น (Overflow) จากการแทรกค่าใหม่เพิ่มเข้ามา รวมทั้งการรวมโหนดเมื่อมีการลบค่าออกไป นอกจากนี้ยังมีการกำหนดให้จำนวนค่าของคีย์ต้องไม่น้อยกว่า 75 เปอร์เซ็นต์ในแต่ละโหนดโดย McCreight เรียกว่าบี**-ทรี (B**-Tree)
บี+-ทรี (B+-Tree)
เป็นเทคนิคที่นิยมมาใช้เป็นดัชนีจัดการกับแฟ้มข้อมูลลำดับเชิงดัชนี (Indexed Sequential File) ในบางครั้งการทำงานมีความต้องการเข้าถึงค่าของคีย์เรียงตามลำดับในบี-ทรีจะต้องใช้การวิ่งตามเส้นทางแบบอิน-ออเดอร์เช่นเดียวกับไบนารี่เสิร์ชทรี แต่จะได้เพียงค่าเดียวในแต่ละช่วงเวลา จึงเพิ่มความสามารถการเข้าถึงแบบเรียงตามลำดับเข้ามาโดยใช้เป็นบี+-ทรี
ในแต่ละโหนดของบี-ทรีจะมีตัวชี้อ้างไปยังตำแหน่งหรือแอดเดรสของเรคคอร์ด แต่สำหรับบี+-ทรีจะมีเฉพาะที่โหนดปลายเท่านั้น โดยให้โหนดภายใน (Internal Node) ใช้เป็นดัชนีเพื่อการเข้าถึงข้อมูลอย่างรวดเร็วโดยตรง มีตัวชี้อ้างไปยังโหนดลูก เรียกส่วนนี้ว่า ชุดดัชนี (Index Set) ส่วนโหนดปลายจะมีโครงสร้างต่างจากโหนดภายในที่มีตัวชี้อ้างไปยังตำแหน่งหรือแอดเดรสของเรคคอร์ดและมีตัวชี้อ้างถึงโหนดปลายที่อยู่ลำดับถัดไปเรียงตามลำดับ เรียกส่วนนี้ว่า ชุดเรียงลำดับ (Sequence Set) ดังนั้น บี+-ทรีสามารถเข้าถึงแต่ละค่าได้โดยตรง โดยใช้ส่วนของชุดดัชนี หากต้องการเข้าถึงทีละค่าเรียงตามลำดับก็จะใช้ส่วนของชุดเรียงลำดับ ดังตัวอย่างในรูปที่ 12.20
รูปที่ 12.20 ตัวอย่างบี+-ทรีที่มีค่าของคีย์แบบเดียวกับบี-ทรีในรูปที่ 12.19
เป็นบี+-ทรีที่มีความสูงเท่ากับ 3 โดยระดับ 0 และ 1 เป็นชุดดัชนี แต่ละโหนดภายในมีดีกรี 4 ส่วนระดับ 2 เป็นชุดเรียงตาม แต่ละโหนดปลายมีดีกรี 3 เมื่อต้องการค้นหาแต่ละค่า โดยตรงจะเริ่มที่รูทโหนด a วิ่งลงมาจนถึงโหนดปลาย d ถึง j ถ้าพบก็ใช้ตัวชี้อ้างไปยังตำแหน่งหรือแอดเดรสของเรคคอร์ดที่ต้องการ ถ้าไม่พบแสดงว่าไม่มีเรคคอร์ดที่ต้องการ ในกรณีที่ต้องการใช้ทุกค่าเรียงตามลำดับ เช่น การทำรายงานซึ่งต้องใช้ทุกเรคคอร์ด จะเริ่มที่โหนดปลาย d ทางด้านซ้ายสุดวิ่งไปยังด้านขวาทีละโหนดจนถึงโหนดปลาย j ด้านขวาซึ่งเป็นโหนดสุดท้ายที่ตัวชี้มีค่า NUL
บทเรียนข้อมูลและหลักการเขียนโปรแกรมเบื้องต้นรหัสวิชา ง 30294 