Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/17841
標題: 大型文字檔案的近似吻合字串找尋
Strings near-matching techniques for large textual files
作者: 蕭如淵
XIAO, RU-YUAN
關鍵字: LARGE-TEXTUAL-FILE;大型文字檔案;STRINGS-SEARCH;TEXTUAL-FILES;NEAR-MATCHING-STRINGS;FINITE-STATE-AUTOMATION;字串找尋;文字檔案;近似吻合字串;有限自動機
出版社: 應用數學研究所
摘要: 
應用上,在一個大型文字檔案(large textual file)中找尋樣本字串(patterns)
時,樣本字串及文字字串(textual string)都可能會因為使用不同的拼法,不同的
字母格式或打字的疏忽等原因而以不完全相同的形式出現。這些字串稱為近似合(
near-matching )字串。
在本篇論文,我們利用有限狀態自動機(finite-state automaton)的狀態轉移觀
念,提出一個方法,根據此方法可以相當簡單又有效地在一個大型文字檔案中將與一
堆樣本字串近似合的字串及其在文字檔案中的位置找尋出來。根據我們的方法,則
被處理的文字檔案毋需作任何特殊的處理。當文字檔案的長度為n 時,所需的搜尋時
間為 O(n )且受樣本字串之個數的影響甚微。
URI: http://hdl.handle.net/11455/17841
Appears in Collections:應用數學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.