Google        youtube          psv       สพม.11

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

  1. การค้นหาแบบลำดับ  (Sequential Search)
  2. การค้นหาแบบแบ่งครึ่ง  (Binary Search)
  3. การค้นหาแบบสอดแทรก  (Interpolation Search)
  4. การค้นหาข้อความ  (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;
}

  1. การสลับตำแหน่ง  (Transposition)

หลังจากที่ค้นหาคีย์ที่ต้องการพบ  ก็ทำการย้ายเรคคอร์ดที่มีคีย์นั้นสลับกับเรคคอร์ดที่อยู่ก่อนหน้าหนึ่งตำแหน่ง  นำมาใช้กับเรคคอร์ดที่ถูกค้นหาบ่อยและค่อย ๆ ขยับไปด้านหน้าตามช่วงระยะเวลา  อัลกอริทึมมีการเปลี่ยนแปลงเพิ่มเติมในส่วนที่พบค่าของคีย์ได้เป็น  ดังนี้
If (I <size){
Tmp=key[i];
For (; I > 0; i–)
Key[i]=[i];
Key[0]=tem;
Return 0;
}

  1. นับจำนวนการค้นหา  (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[1]
Table[2]
Table[3]
Table[4]
Table[5]

Table[23]
Table[24]

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
987654321
123456790

ชนกัน

555555555
000000472
100064183
200120472
200120473
117400000
027000400

2762
2086
2763
2424
0473
4184
0473
0474
4606
3613

รูปที่ 12.7  ตัวอย่างแฮชฟังก์ชันที่มีตัวหารเท่ากับ 5003

ค่าตรงกลางยกกำลังสอง 
เป็นการนำค่าของคีย์ยกกำลังสอง  จากนั้นนำค่าที่อยู่ช่วงตรงกลางออกมาได้เป็นตำแหน่งในตารางแฮช  ถ้าตำแหน่งในตารางเป็นเลขจำนวน n หลักก็ดึงค่าช่วงตรงกลางออกมา n ตัวที่ห่างจากซ้ายขวาเท่ากัน  ดังในรูปที่ 12.8

คีย์

ค่ายกกำลังสอง

ตำแหน่งในตารางแฮช

123456789
987654321
123456790
555555555
000000472
100064183
200120472
200120473
117400000
027000400

15241578750190521
975461055789971041
15241578997104100

ชนกัน

308641974691358025
00000000000222784
10012860719457489
40048203313502784
40048203713743729
13782760000000000
02430021600160000

8750
5789
8997
4691
0000
0719
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
987654321
123456790
555555555
000000472
100064183
200120472
200120473
117400000
027000400

3221
8999
4321
6110
2740

ชนกัน                    ชนกัน

4820
4752
5752
2740
2740

รูปที่ 12.9  ตัวอย่างแฮชฟังก์ชันที่ใช้การพับทบกันแบบแบ่งเขต

                           นอกจากวิธีการแมพของแฮชฟังก์ชันที่ได้กล่าวมาแล้วยังมีอีกหลายวิธี  เช่น  วิธีการดึงบางค่าออกมา  (Extraction)  เป็นการนำค่าเฉพาะบางส่วนมาใช้เป็นตำแหน่งในตารางแฮช  เช่น  ค่าของคีย์  123456789  ใช้สี่ตัวแรกได้เป็น 1234  ใช้สี่ตัวหลังได้เป็น 6789  และอาจนำมาประกอบกันโดยใช้สองตัวแรกรวมกับสองตัวหลังได้เป็น 1289  หรือในรูปแบบอื่น ๆ แต่ต้องหลีกเลี่ยงการนำตัวเลขที่ซ้ำเหมือนกันในทุก ๆ ค่าของคีย์มาใช้  เช่น  รหัสนักศึกษาที่มีปี พ.ศ. ซึ่งเป็นตัวเลขมีอยู่ในทุกคีย์  ถ้านำมาใช้รวมอยู่ด้วยทำให้โอกาสการชนกันมีมาก
การแปลงเลขฐาน  (Radix Transformation)  เป็นอีกวิธีหนึ่งโดยการแปลงค่าของคีย์ให้อยู่ในเลขฐานอื่นและใช้เป็นตำแหน่งในตารางแฮช  เช่น  ค่าของคีย์  345  ในเลขฐานสิบแปลงเป็นเลขฐานเก้า  (Nonal)  ได้เป็น 423  จากนั้นทำการหารเหลือเศษด้วยขนาดของตารางแฮช

การแก้ปัญหาชนกัน 
เนื่องจากแฮชฟังก์ชันทำการแมพค่าของคีย์จากพื้นที่ขนาดใหญ่ไปเป็นพื้นที่ตำแหน่งในตารางแฮชขนาดเล็กทำให้เกิดการชนกันที่มีค่ามากกว่าหนึ่งอ้างไปยังตำแหน่งเดียวกัน  การแก้ไขอาจใช้แฮชฟังก์ชันที่สามารถกระจายค่าไม่ให้ชนกันหรือเพิ่มขนาดตารางแฮชให้มากขึ้น  แต่ก็ช่วยลดให้น้อยลงเท่านั้นจึงมีเทคนิคที่นำมาใช้แก้ปัญหาชนกันหลายวิธีซึ่งจะกล่าวถึง  คือ

      1. การเปิดแอดเดรส  (Open Addressing)
      2. การต่อเป็นลูกโซ่  (Chaining)
      3. การใช้พื้นที่บักเก็ต  (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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s