(3.238.186.43) 您好!臺灣時間:2021/03/01 09:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:顏成哲
研究生(外文):Chen-Cheng Yen
論文名稱:結合BerryRavindran演算法與TwoWay演算法用於精確字串比對
論文名稱(外文):A Combination of Berry Ravindran Algorithm and Two Way Algorithm for Exact String Matching
指導教授:李家同李家同引用關係
指導教授(外文):R.C.T. Lee
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:34
中文關鍵詞:精確字串比對問題Two Way 演算法Berry Ravindran 演算法
外文關鍵詞:Exact String MatchingTwo Way algorithmBerry Ravindran algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:377
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
精確字串比對問題定義如下:給予一個長度為 的字串 ,長度為 的字串 我們的目標是要在T 上找出所有 發生的位置。對於電腦科學而言,字串比對問題是一個重要的議題。
在本篇論文中,我們提出一個新的方法來解決這個問題. Two Way 演算法與Berry Ravindran 演算法在找尋在 上找出所有 發生的位置而言都是很好的演算法, 不過仍然存在著一些問題. 如果我們考慮在Window後面的兩個字元與P最右邊的兩個字元相等的情形,那麼Berry Ravindran 演算法就會沒有效率.如果我們把 分成 跟 兩部份,常常在 部份就發生錯誤,那麼Two Way 演算法也沒有效率.所以我們把兩個演算法結合起來來解決精確字串比對問題.

最後, 我們會討論Two Way 演算法、Berry Ravindran演算法跟我們的方法
The exact string matching problem is defined as follows: We are given a text and a pattern , . Our purpose is to find all occurrences of in . It is a classical and important problem in computer science.

In this thesis, we propose a new approach to solve this problem. Two Way algorithm and the Berry Ravindran algorithm are good algorithms which find all occurrences of in , but some problems still exist. If we consider the situation that the last two text characters of the window with size m are the same with that of , Berry Ravindran algorithm is not efficient in this situation. If a mismatch often occurs within v part of , Two Way algorithm is not efficient in this situation. So we combine Two Way algorithm and Berry Ravindran algorithm to slove this problem

Finally; we discuss the results of Two Way algorithm, Berry Ravindran algorithm and our approach.
Contents

Chapter 1 Introduction………………………………………………………………1


1.1 Motivations………………………………………………………………………..1

1.2 Previous Works……………………………………………………………………1

1.3 Thesis Organization……………………………………………………………….2


Chapter 2 Reviews and Basic Algorithm…………………………………………..3


2.1 The Basic Terminologies of Strings………………………………………...……3


2.2 The Brute-Force Algorithm………………………………………………………5


2.3 Two Way Algorithm……………………………………………………………...6

2.3.1 The Terminologies in the Two Way Algorithm…………………………….6

2.3.1.1 Short Maximal Suffix……………………………………………….6

2.3.1.2 The Non-Overlapping Property of Maximal Suffix………………...7

2.3.2 The Two Way Algorithm with Short Maximal Suffix……………………...8

2.4 Berry Ravindran Algorithm………………………………………………………14

2.4.1 Idea…………………………………………………………………………14

2.4.2 Preprocessing Phase………………………………………………………..21

2.4.3 Full Example……………………………………………………………….23





Chapter 3 Our Faster algorithm………………………………………………….26


3.1 Our Algorithms……………………………………………………………….…26

3.1.1 Preprocessing Phase……………………………………………………….28

3.1.2 Searching Phase……………………………………………………….…..29

3.1.3 Full Example………………………………………………………………31
.

Chapter 4 Experimental Result…………………………………………………...32



Chapter 5 Conclusion……………………………………………………………...33


Bibliography……………………………………………………………………..…34
Bibliography


[BM77] A Fast String Searching Algorithm, Boyer, R. S. and Moore, J. S.,Communication of the ACM, Vol. 20, 1977, pp. 762-772.

[KMP77] Fast pattern matching in strings, KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R. SIAM Journal on Computing 6(1), 1977, pp.323-350


[C89] String Matching and Periods, Crochemore, M., Theoretical Computer Science, Vol.39, 1989, pp. 149-153.

[S90] A very fast substring search algorithm, SUNDAY D.M., Communications of the ACM .1990, pp. 132-142.

[CLP98] Very Fast String Matching Algorithm for Small Alphabets and Long Patterns, Christian, C., Thierry, L. and Joseph, D.P., Lecture Notes in Computer Science, Vol. 1448, 1998, pp. 55-64

[BR99] Proceedings of the Prague Stringology Club Workshop ’99, Prague, Czech Republic, pp.16-28.

[CP91] Two-Way String Matching, Crochemore, M. and Perrin, D., Journal of ACM, Vol.38(3), 1991, pp.651-675.

[CR2002] Jewels of Stringology, Crochemore, M. and Rytter, W., World Scientific, Singapore, 2002.


[CR94] Text Algorithms, Crochemore, M. and Rytter, W., Oxford University Press, 1994.
[L2001] Computational Biology, Lee, R. C. T., 2001.

[LTCT2005] Introduction to the Design and Analysis of Algorithms, Lee, R. C. T., Tseng,S. S., Chang, R. C., Tsai, Y. T., McGraw-Hill Education(Asia), 2005.

[R89] Knuth-Morris-Pratt Algorithm: an Analysis, Régnier, M., In Proceedings of the 14thSymposium on Mathematical Foundations of Computer Science, number 397 in LectureNotes in Computer Science, 1989, pp.431-444.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔