(34.239.150.57) 您好!臺灣時間:2021/04/19 00:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:薛睿光
研究生(外文):Hsueh Jui Kuang
論文名稱:字串比較演算法之研究
論文名稱(外文):A Study on String-Matching Algorithms
指導教授:陳維美
學位類別:碩士
校院名稱:大同大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
中文關鍵詞:字串比較
外文關鍵詞:String-Matching
相關次數:
  • 被引用被引用:0
  • 點閱點閱:146
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
我們對數種常見的字串比較演算法做實驗模擬,分析研究各種演算法所需的工作效能。同時,進一步詳細探討波以爾莫爾演算法及其衍生相關演算法所需之工作量,包含比較次數和執行時間。

In this thesis, we give experimental results on the performance of several popular string-matching algorithms. Meanwhile the behaviors of the costs of some variant Boyer-Moore algorithms are investigated. The costs considered include the numbers of character inspections, and the total time used.

Contents
1 Introduction 1
2 The String-Matching Algorithms 5
2.1 Knuth-Morris-Pratt Algorithm . . . . . . . . . . . . . . 5
2.1.1 KMP shift rule . . . . . . . . . . . . . . . . . . 6
2.2 Karp-Rabin Algorithm . . . . . . . . . . . . . . . . . . 9
2.2.1 KR shift rule . . . . . . . . . . . . . . . . . . . 10
2.3 Shift-Or Algorithm . . . . . . . . . . . . . . . . . . . . 11
2.3.1 SO shift rule . . . . . . . . . . . . . . . . . . . . 12
2.4 Boyer-Moore Algorithm . . . . . . . . . . . . . . . . . 15
2.4.1 Right-to-left scan . . . . . . . . . . . . . . . . . 17
2.4.2 DELTA 1 : Bad character shift . . . . . . . . . 18
2.4.3 DELTA 2 : Good sux shift . . . . . . . . . . . 19
2.5 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Variants of the BM Algorithm 28
3.1 Turbo BM Algorithm . . . . . . . . . . . . . . . . . . . 28
3.2 Tuned BM Algorithm . . . . . . . . . . . . . . . . . . . 31
3.3 Horspool Algorithm . . . . . . . . . . . . . . . . . . . . 33
3.4 Sunday Algorithm . . . . . . . . . . . . . . . . . . . . 34
3.5 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Conclusions 50

Bibliography
[1] A. V. Aho, M. J. Corasick, 1975, Ecient String Matching: An
aid to bibliographic search. Communications of the ACM, 18(4),
pp.333-340.
[2] A. APOSTOLICO, R. GIANCARLO, 1986, The Boyer-Moore-
Galil string searching strategies revisited, SIAM Journal on Com-
puting, 15(1), pp.98-105.
[3] R. A. BAEZA-YATES, G. H. GONNET, 1992, A new approach
to text searching, it Communications of the ACM. 35(10), pp.74-
82.
[4] R. S. BOYER, J. S. MOORE., 1977, A fast string searching al-
gorithm. Communications of the ACM. 20, pp.762-772.
[5] M. CROCHEMORE, A. CZUMAJ, L. GASIENIEC, S.
JAROMINEK, T. LECROQ, W. PLANDOWSKI, W.RYTTER,
1992, Deux methodes pour accelerer l'algorithme de Boyer-
Moore, in Theorie des Automates et Applications, Actes des 2e
Journees Franco-Belges, D. Krob ed., Rouen, France, 1991, pp
45-63, PUR 176, Rouen, France.
[6] M. CROCHEMORE, D. PERRIN, 1991, Two-way string-
matching, Journal of the ACM, 38(3), pp.651-675.
[7] R. COLE, 1994, Tight bounds on the complexity of the Boyer-
Moore pattern matching algorithm, SIAM Journal on Computing,
23(5), pp.1075-1091.
[8] L. COLUSSI, 1994, Fastest pattern matching in strings, Journal
of Algorithms, 16(2), pp.163-189.
[9] L. J. Guibas, A. M. Odlyzko, 1980, A new proof of the linearity
of the Boyer-Moore string searching algorithm, SIAM Journal on
Computing, 9(4), pp.672-682.
[10] R. N. HORSPOOL, 1980, Practical fast searching in strings, Soft-
ware - Practice and Experience, 10(6), pp.501-506.
[11] A. HUME and D. M. SUNDAY , 1991, Fast string searching,
Software - Practice and Experience, 21(11), pp.1221-1248.
[12] D. E. KNUTH, J. H. MORRIS (Jr), PRATT V.R., 1977, Fast
pattern matching in strings, SIAM Journal on Computing, 6(1),
pp.323-350.
[13] R. M. KARP, M. O. RABIN, 1987, Ecient randomized pattern-
matching algorithms. IBM J. Res. Dev, 31(2), pp.249-260.
[14] J. H. MORRIS (Jr), V. R. PRATT, 1970, A linear pattern-
matching algorithm, Technical Report 40, University of Califor-
nia, Berkeley.
[15] D. M. SUNDAY, 1990, A very fast substring search algorithm,
Communications of the ACM, 33(8), pp.132-142.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔