(34.239.150.57) 您好！臺灣時間：2021/04/19 00:00

### 詳目顯示:::

:

• 被引用: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: Anaid 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 approachto 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 2eJournees Franco-Belges, D. Krob ed., Rouen, France, 1991, pp45-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, Journalof Algorithms, 16(2), pp.163-189.[9] L. J. Guibas, A. M. Odlyzko, 1980, A new proof of the linearityof the Boyer-Moore string searching algorithm, SIAM Journal onComputing, 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, Fastpattern 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.
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 精確字串比對演算法上的一些結果 2 基於KMP演算法的多字元字串比較架構與其FPGA實作 3 跳躍式字串比對演算 4 基於AC演算法的多重封包平行字串比對架構 5 在壓縮字串中解序列比對問題：最大共同子序列,編輯距離及重複序列 6 加速深層封包檢查的字串比對演算法 7 運用雜湊結構解決完整字串比對問題 8 基於常數字串長度比對演算法之近似字串比對演算法 9 以Boyer-Moore演算法為基礎改良之近似字串比對演算法 10 利用獨特性質解決字串比對問題和利用篩選方法解決近似字串比對問題 11 使用編碼技術解決完整字串比對問題 12 不需製表格的字串比對演算法之分析 13 常數空間的字串比對演算法之比較分析 14 具可變長度及容忍度特徵之字串搜尋比對演算法 15 字串比對問題之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室