Google         youtube            psv            สพม.11

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

next = low + 

เมื่อใช้การค้นหาแบบสอดแทรกเขียนเป็นอัลกอริทึมดังในตารางที่ 12.5

ตารางที่ 12.5  อัลกอริทึมการค้นหาแบบสอดแทรก 

1.  ให้ low = 0  และ high = n-1
2.  ทำขั้นตอน 3-5 ซ้ำ  ถ้า low < high
3.  ให้ next = low + ( (k-a low)/(a high-a low))*(high-low-1)
4.  ถ้าค่า a mid < k ให้  low = next + 1  และ current = low  ไม่เช่นนั้นให้ high = next+1  และ current = high
5.  ถ้าค่า a current  =  k  ให้ส่งค่า current กลับมา
6.  ไม่พบส่งค่า -1 กลับมา                และเขียนเป็นฟังก์ชันการค้นหาแบบสอดแทรกได้เป็นตารางที่ 12.6

ตารางที่ 12.6  ฟังก์ชันการค้นหาแบบสอดแทรก 
int interpolateSearch (int key[],int size ,int value){
int low=0;
int high=size-1;
int next=0;
int curr;
while(low <high){
next = low+( (value-key[low])*(high-low-1)/(key[high]-key[low];
if (key[next]<value){
low=next+1;
curr=low;
} else{
high=next;
curr=high;
}
If(key[curr]==value)
Return curr
}
return-1;
}
         การ ค้นหาแบบสอดแทรกในกรณีเฉลี่ยการค้นหาจะเท่ากับ O(log2 log2 n)  ซึ่งดีกว่าการค้นหาแบบแบ่งครึ่งที่เท่ากับ  O(log2 n)  แต่ในกรณีโชคร้ายจะเป็นแบบเชิงเส้นมีค่าเท่ากับ O(n)  เนื่องจากค่าของคีย์ต่าง ๆ มีการกระจายไม่สม่ำเสมอ  เช่น  (1,2,4,8,16,..)  นอกจากนี้ยังต้องมีการคำนวณเพื่อหาตำแหน่งถัดไป  ถ้าหากต้องการใช้การค้นหาแบบสอดแทรกจึงควรใช้กับค่าของคีย์ที่กระจายสม่ำ เสมอ  (Uniformly Distributed)  เช่น  (1,2,4,6,8,10,..)  อย่างไรก็ตามหากค่าของคีย์กระจายไม่สม่ำเสมอ  การค้นหาตำแหน่งถัดไปจะใช้สูตรต่อไปนี้แทน
gap  =  sqrt(high – low + 1) // gap < next – low and high – next
probe  =  low + ´ (high-low)
next  =  min(high – gap, max(probe, low + gap) )

การ ค้นหาแบบสอดแทรกเหมาะที่จะนำไปใช้กับการค้นหาข้อมูลในอุปกรณ์จัดเก็บข้อมูล สำรอง  เนื่องจากเวลาการเข้าถึงข้อมูลมากกว่าเวลาที่ใช้ในการคำนวณ  และการเรียกใช้มีลักษณะการกระจายสม่ำเสมอ  ส่วนการค้นหาแบบแบ่งครึ่งเหมาะที่จะใช้ค้นหาข้อมูลที่อยู่ในหน่วยความจำหลัก และมีการคำนวณน้อยกว่า

การค้นหาคำในข้อความ 
โดยทั่วไปคอมพิวเตอร์มีพื้นฐานการทำงานและคำนวณในรูปแบบของตัวเลข  แต่มีการนำมาใช้จัดการกับสัญลักษณ์ที่ประกอบด้วยตัวอักษรทั่วไปและตัวอักษร พิเศษ  ซึ่งคนเราสนใจและใช้งานแอปพลิเคชั่นส่วนใหญ่ในการประมวลผลกับสัญลักษณ์ที่ ไม่ใช่ตัวเลข  ในที่นี้จึงเป็นเรื่องของการประมวลผลเพื่อค้นหาคำในข้อความ  (Text Searching)  หรือการค้นหารูปแบบเหมือนกัน  (Pattern Matching)  เพื่อหารูปแบบตามลำดับของสัญลักษณ์  S1,  S2, S3, …, Sn,  ในข้อความที่ประกอบด้วยสัญลักษณ์เรียงต่อกันเป็นจำนวนมาก ๆ เช่นต้องการค้นหาคำว่า  “Computer”  ในข้อความต่อไปนี้
string  problem  solving  is  a  common  paradigm  of  computer  science.

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

ตารางที่ 12.7  อัลกอริทึมการค้นหาคำในข้อความ 

1.  ทำขั้นตอน 2-4 ซ้ำ  ตั้งแต่ i = 0  จนถึง  i = n – patternsize
2.  ทำขั้นตอน 3 ซ้ำ  ตั้งแต่ j = 0 จนถึง j = patternsize
3.  ถ้าค่า ai ! = tj  ออกจากการวนซ้ำของขั้นตอน 2
4.  ถ้าค่า j = patternsize  ให้ส่งค่า i กลับมา
5.  ไม่พบส่งค่า -1 กลับมา

และเขียนเป็นฟังก์ชันเรียงการค้นหาคำในข้อความได้เป็นตารางที่ 12.8

ตารางที่ 12.8  ฟังก์ชันการค้นหาคำในข้อความ 
int stringSearch(char text[],int tsize, char pattern[],int psize){
int I =0;
int j = 0;
int k = 0;
while((i<tsize)&&(j
if(text[k]!=pattern[j]){
i++;
j = 0;
k = I;
}else{
J++;
K++;
}
If(j==psize-1)
Return I;
}
Return-1;
}

อัล กอริทึมการค้นหาคำในลักษณะดังกล่าวยังไม่มีประสิทธิภาพ  เนื่องจากในกรณีโชคร้ายต้องใช้การเปรียบเทียบถึง  O(mn)  เมื่อ  m  คือ  ความยาวของคำและ n  คือ  ความยาวของข้อความ  ถ้าหากข้อความมีความยาวมาก ๆ ก็จะด้อยประสิทธิภาพ  การขยับตำแหน่งของคำเพื่อเปรียบเทียบมีความล่าช้าและเป็นการเปรียบเทียบที่ ซ้ำซ้อนมากเกินไป  จึงมีการปรับปรุงอัลกอริทึมการค้นหารูปแบบเหมือนกันที่เป็นของ  Knuth, Morris, Pratt  ซึ่งมีลักษณะเป็น  finite Automaton  และของ  Boyer  กับ  Moore  ที่มีลักษณะเป็นการกระโดด  อัลกอริทึมที่น่าสนใจและมีความเร็ว  คือ  ของ  Boyer  กับ  Moore  ซึ่งกระบวนการค้นหาเปรียบเทียบจะเริ่มทางด้านขวาของคำแทนที่เริ่มจากด้าน ซ้ายในรูปแบบเดิม  ช่วยให้มีประสิทธิภาพมากขึ้น
ถ้าหากการเปรียบเทียบสัญลักษณ์ในข้อความกับสัญลักษณ์ทางด้านขวาของคำไม่ เหมือนกันและไม่พบในคำ  ก็จะเลื่อนคำกระโดดข้ามสัญลักษณ์ของข้อความตัวนั้นไป  จากรูปที่ 12.5  การเปรียบเทียบครั้งแรกระหว่างสัญลักษณ์ช่องว่างของข้อความกับ r ของคำว่า  computer ก็กระโดดข้ามสัญลักษณ์ช่องว่างไปเนื่องจากไม่มีในคำ  ถ้าหากการเปรียบเทียบสัญลักษณ์ไม่เหมือนกันแต่พบในคำก็จะเลื่อนให้สัญลักษณ์ ที่พบกระโดดอยู่ตรงกับสัญลักษณ์ของข้อความ  จากรูปในการเปรียบเทียบครั้งที่สามระหว่างสัญลักษณ์ m ใน common ของข้อความกับ r ของคำไม่เหมือนกัน  แต่พบ m ของคำที่เหมือนกัน  จึงเลื่อนให้ตรงกับ m ของข้อความ  จากนั้นเริ่มทำการเปรียบเทียบใหม่ยังตำแหน่งขวาสุดของคำ  เมื่อการเปรียบเทียบสัญลักษณ์ทางด้านขวาเหมือนกันก็จะมาเปรียบเทียบ สัญลักษณ์ถัดไปทางด้านซ้ายไปเรื่อย ๆ จนเหมือนกันครบทุกตัวจึงพบ   แต่ถ้าไม่ครบก็จะกระโดดไปทางขวาเพื่อค้นหาใหม่ต่อไป  การเขียนเป็นโปรแกรมเพื่อค้นหาคำในข้อความแบบ Boyer-Moore ได้เป็นฟังก์ชันดังในตารางที่ 12.9

ตารางที่ 12.9  ฟังก์ชันการค้นหาคำในข้อความแบบ Boyer-Moore
Void computeJump(int jump[],int jSize,char pattern[],int pSize){
Int I;
for (i=0;i
jump[i]=pSize;
for (i=0; i
jump[pattern[i]]=psize-i-1;
}
int stringMatching(char text[],int tSize, char pattrn[],int pSize){
int i=psize-1;
int j=i;
int charJump[256];
computeJump(charJump,256,pattern,pSize);
while((I <tsize)&&(j>=0)){
if (text[i]==pattern[j]){
i–;
j–;
}else{
I +=charJump[text[i]];
}
}
If (j== -1)
Return i+1;
Return -1;
}

อัล กอริทึมการค้นหารูปแบบเหมือนกันของ Boyer กับ Moore มีการเปรียบเทียบเพียง 14 ครั้งเพื่อค้นหาคำว่า  computer  ขณะที่อัลกอริทึมธรรมดาทั่วไปต้องมีการเปรียบเทียบถึง 51 ครั้ง  แต่มีส่วนเพิ่มเติม  คือ  การคำนวณหาค่าการกระโดดของสัญลักษณ์แต่ละตัวที่มีอยู่และไม่มีอยู่ในคำ  โดยใช้ฟังก์ชัน  computeJump

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

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

การเข้าถึงโดยตรง 
หรือการเข้าถึงโดยการสุ่ม  (Random Access)  จะค้นหาเรคคอร์ดที่อ้างโดยตรงไปยังตำแหน่งของเรคคอร์ดที่ต้องการในแฟ้ม ข้อมูล  โดยใช้ดัชนี  (Index)  ซึ่งมีตัวชี้  (Pointer)  เป็นแอดเดรสของ       เรคคอร์ดที่ต้องการ  ดังนั้น  การเข้าถึงโดยตรงจึงทำงานได้เร็วกว่าการเข้าถึงแบบลำดับ  แต่ต้องทราบค่าดัชนีของแต่ละเรคคอร์ดก่อนและนำมาใช้กับแฟ้มข้อมูลโดยตรง  (Direct File)  หรือแฟ้มข้อมูลสุ่ม  (Random File)  แฟ้มข้อมูลลำดับเชิงดัชนี  (Index Sequence File)  และแฟ้มข้อมูลหลายคีย์  (Multi-key File)  ซึ่งใช้อุปกรณ์จัดเก็บข้อมูลที่เข้าถึงโดยตรง  เช่น  จานแม่เหล็กหรือดิสก์  (Disk)  ที่สามารถอ่านและเขียนข้อมูลกลับไปกลับมาในแฟ้มข้อมูลได้
แฟ้มข้อมูลใช้เก็บรวบรวมเรคคอร์ดแบบเดียวกันที่มีโครงสร้างข้อมูลประกอบด้วย หลาย ๆ สมาชิก  เรียกว่า  ฟิลด์  (Field)  ซึ่งแต่ละฟิลด์จะมีชื่อและชนิดข้อมูล  เมื่อจัดเก็บข้อมูลเป็นหลาย ๆ         เรคคอร์ด  เรียกว่า  เทเบิล  (Table)  แต่ละเทเบิลจะมีคีย์เพื่อกำหนดความแตกต่างให้กับแต่ละเรคคอร์ดที่มีอยู่ใน เทเบิลโดยใช้ฟิลด์ที่เรียกว่า  คีย์ฟิลด์  (Key Field)  ดังนั้นในการค้นหาเรคคอร์ดที่ต้องการจึงใช้คีย์ฟิลด์ค้นหาและเพื่อความเหมาะ สมจึงกำหนดเป็นค่าที่มีความยาว  สั้น ๆ และมีความเรียบง่าย  โดยอัลกอริทึมการเข้าถึงแบบลำดับมีลักษณะเป็นแบบเดียวกับวิธีการค้นหาแบบ ลำดับที่ได้กล่าวในตอนต้นของบทนี้  ส่วนอัลกอริทึมการเข้าถึงโดยตรงมีเทคนิคอยู่หลายวิธีซึ่งจะกล่าวถึงคือการ คำนวณหาตำแหน่งหรือแอดเดรสโดยใช้แฮชชิ่ง  (Hashing)  และการใช้ดัชนีในลักษณะโครงสร้างทรีแบบบี-ทรี  (B-Tree)

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