大型文字檔案的近似吻合字串找尋

Abstract

應用上，在一個大型文字檔案（large textual file）中找尋樣本字串（patterns） 時，樣本字串及文字字串（textual string）都可能會因為使用不同的拼法，不同的 字母格式或打字的疏忽等原因而以不完全相同的形式出現。這些字串稱為近似合（ near-matching ）字串。 在本篇論文，我們利用有限狀態自動機（finite-state automaton）的狀態轉移觀 念，提出一個方法，根據此方法可以相當簡單又有效地在一個大型文字檔案中將與一 堆樣本字串近似合的字串及其在文字檔案中的位置找尋出來。根據我們的方法，則 被處理的文字檔案毋需作任何特殊的處理。當文字檔案的長度為n 時，所需的搜尋時 間為 O（n ）且受樣本字串之個數的影響甚微。