【字串檢索】

豐碩

【字串檢索】

 

StringSearch

 

【辭書名稱】圖書館學與資訊科學大辭典

 

字串檢索又可稱之為字串比對(StringMatching)，是以查詢的字串，逐一比對儲存於電腦內的文字串，找出完全相同的文字。

 

例如找電腦檔案中，有「Computer」的字串，則電腦會依照檢索的程式，以「Computer」字元逐一比對內文字串，找出含有此檢索字的段落或行列。

 

一般系統會以加強顯示的方式，標示出找到字串的位置。

 

由於字串檢索使用字元對字元比較(Character-by-CharacterComparison)的蒐尋方式，因此檢索效率將隨著內容字數的增加，使得檢索的時間與成本增加。

 

字串檢索法主要應用在全文檢索(FullTextSearch)的查詢上。

 

字串檢索屬於全文掃描運算(Text-ScanningOperation)的方式之一，乃將查尋的字串從左向右，一次一個字元逐一比對文獻的內文字串。

 

此種檢索方式不同於一般文獻檢索法中，利用反轉式檔案(InvertedFile)的檢索法。

 

字串檢索法隨著文獻內文的長度增加，而檢索效率逐漸下降。

 

因此，如何有效增進字串檢索的效率，便成為許多全文檢索演算法研究的主題。

 

快速字串比對法(FastStringMatching)便是字串檢索法中，較為快速的一種檢索方法。

 

該方法改進全文掃描運算法中，一次一個字元比對的方式。

 

該法於正式比對內文之前，先分析查尋字串是否有一定的規律，然後再按此規律比對內文的字串。

 

當查尋字串具有某種的規律時，比對內文時，就以跳躍的方式，由左而右快速跳過沒有規律的內文。

 

一旦找到與查尋字串規律相同的內文字串時，程式才執行一對一逐字比對的工作。

 

如此掃描全文就比一個字一個字比對的方法快速許多。

 

此方法最初由克努斯(D.E.Knuth)、摩理斯(J.H.Morris)與帕瑞特(V.R.Pratt)3位科學家所提出，因此快速字串比對法又稱之為KMP法（以此3位科學家姓氏的第一字組成）。

 

除了快速字串比對法之外，另一種更快速的字串檢索法稱之為BM法，是由鮑依爾(R.S.Boyer)與摩耳(J.S.Moore)共同提出而命名。

 

BM法是按照查尋字串由右向左比對。

 

由右向左比對更可加速找尋字串的速度。

 

例如在「BANANACREAMPIE」字串中，查尋「CREAM」字串時。

 

利用BM法時，最右端的查尋字串字母M與內文字串第5個字N比對如下：BANANACREAMPIE（內文字串）CREAM（查尋字串）查尋結果不符，因此查尋字串很快向右移動5格再比對，如下：BANANACREAMPIE（內文字串）CREAM（查尋字串）查尋字串最右字母M與內文字串E相比文不符，但比對中發現內文字串E與查尋字串的E相差兩格。

 

於是查尋字串又向右移動兩格比對，如下：BANANACREAMPIE（內文字串）CREAM查尋字串M與內文字串M相符，然後由右向左逐一比對，字母完全相符。

 

因此，BM法只用3個步驟即完成了字串檢索，較KMP法或一般的字串比對法來的快速。

 

字串檢索法廣泛應用文獻的自動化檢索研究與探討的主題。

 

 

轉自:http://edic.nict.gov.tw/cgi-bin/tudic/gsweb.cgi?o=ddictionary