:::
字串檢索 - 教育百科
| 字 | |
| 串 | |
| 檢 | |
| 索 |
國家教育研究院辭書
基本資料
| 英文： | String Search |
| 作者： | 莊道明 |
| 日期： | 1995年12月 |
| 出處： | 圖書館學與資訊科學大辭典 |
辭書內容
|
名詞解釋： 字串檢索又可稱之為字串比對(String Matching)，是以查詢的字串，逐一比對儲存於電腦內的文字串，找出完全相同的文字。例如找電腦檔案中，有「Computer」的字串，則電腦會依照檢索的程式，以「Computer」字元逐一比對內文字串，找出含有此檢索字的段落或行列。一般系統會以加強顯示的方式，標示出找到字串的位置。由於字串檢索使用字元對字元比較(Character-by-Character Comparison)的蒐尋方式，因此檢索效率將隨著內容字數的增加，使得檢索的時間與成本增加。字串檢索法主要應用在全文檢索(Full Text Search)的查詢上。 字串檢索屬於全文掃描運算(Text-Scanning Operation)的方式之一，乃將查尋的字串從左向右，一次一個字元逐一比對文獻的內文字串。此種檢索方式不同於一般文獻檢索法中，利用反轉式檔案(Inverted File)的檢索法。字串檢索法隨著文獻內文的長度增加，而檢索效率逐漸下降。因此，如何有效增進字串檢索的效率，便成為許多全文檢索演算法研究的主題。快速字串比對法(Fast String Matching)便是字串檢索法中，較為快速的一種檢索方法。該方法改進全文掃描運算法中，一次一個字元比對的方式。該法於正式比對內文之前，先分析查尋字串是否有一定的規律，然後再按此規律比對內文的字串。當查尋字串具有某種的規律時，比對內文時，就以跳躍的方式，由左而右快速跳過沒有規律的內文。一旦找到與查尋字串規律相同的內文字串時，程式才執行一對一逐字比對的工作。如此掃描全文就比一個字一個字比對的方法快速許多。此方法最初由克努斯(D.E. Knuth)、摩理斯(J.H. Morris)與帕瑞特(V.R. Pratt)3位科學家所提出，因此快速字串比對法又稱之為KMP法（以此3位科學家姓氏的第一字組成）。 除了快速字串比對法之外，另一種更快速的字串檢索法稱之為BM法，是由鮑依爾(R.S. Boyer)與摩耳(J.S. Moore)共同提出而命名。BM法是按照查尋字串由右向左比對。由右向左比對更可加速找尋字串的速度。例如在「BANANA CREAM PIE」字串中，查尋「CREAM」字串時。利用BM法時，最右端的查尋字串字母M與內文字串第5個字N比對如下： BANANA CREAM PIE （內文字串） CREAM （查尋字串） 查尋結果不符，因此查尋字串很快向右移動5格再比對，如下： BANANA CREAM PIE （內文字串） CREAM （查尋字串） 查尋字串最右字母M與內文字串E相比文不符，但比對中發現內文字串E與查尋字串的E相差兩格。於是查尋字串又向右移動兩格比對，如下： BANANA CREAM PIE （內文字串） CREAM 查尋字串M與內文字串M相符，然後由右向左逐一比對，字母完全相符。因此，BM法只用3個步驟即完成了字串檢索，較KMP法或一般的字串比對法來的快速。字串檢索法廣泛應用文獻的自動化檢索研究與探討的主題。 |
|
| 資料來源： | 國家教育研究院_字串檢索 |
| 授權資訊： | 資料採「 創用CC-姓名標示- 禁止改作 臺灣3.0版授權條款」釋出 |
我是貓頭鷹博士，
有問題可以問我喔！
有問題可以問我喔！