臺灣博碩士論文加值系統

一個字串比對問題的定義，是指在本文(text)中尋找與一個特定字串相符的所有發生位置。對於電腦科學而言，字串比對問題是一個重要的議題。目前最著名的二個基本的字串演算法則是Knuth-Morris-Pratt (簡稱KMP)演算法與Boyer-Moore(簡稱BM)演算法，而這二個演算法皆只能在線性時間與空間內處理字串比對的問題。因此，如何設計一個在線性時間與常數空間下就能處理字串比對問題的演算法，就變成一個有趣但也很複雜的議題。近年來，有很多的常數空間與線性時間下的字串比對演算法被提出，而這些演算法大多數皆是以KMP演算法為基礎進行發展而來。

在本篇論文中，我們將針對三個最近提出的常數空間與線性時間下的字串比對演算法進行探討。這三個演算法為：MaxSuffix-Matching演算法、Two-Way Pattern Matching演算法與Sequential Sampling機制。在論文中，我們首先將先針對KMP演算法進行介紹，並且針對它的不同的前置函數進行討論。其次，我們將依序分章介紹與討論前述的三個常數空間的字串比對演算法。最後，我們再依據不同的主題來對以上的三個演算法進行比較，藉由這些主題的比較來看出這三個演算法之間的不同之處。

The string matching problem is to find all occurrences of a given pattern string P in a text string T. It is a classical and important problem in computer science and two well-known string matching algorithms are the Knuth-Morris-Pratt (KMP) algorithm and the Boyer-Moore (BM) algorithm and both of them work in linear time and linear space. Hence, designing a string matching algorithm with linear time cost and simultaneously constant space are interesting and usually sophisticated in the string matching problem. In recent years, many constant space and linear time string matching algorithms were proposed and most of them are based on the KMP algorithm.

In this thesis, we perform a review of three recent constant space string matching algorithms: the MaxSuffix-Matching algorithm, the Two-Way Pattern matching algorithm and the Sequential-Sampling scheme. We first discuss the KMP algorithm and introduce its preprocessing functions. We then introduce above three constant space algorithms respectively. Finally, we compare their differences between these three algorithms by several different subjects.

List of Figures vii
List of Tables ix
Chapter 1 Introduction 1-1
1.1 Motivations 1-1
1.2 Previous Works 1-2
1.3 Thesis Organization 1-3
Chapter 2 Reviews and Survey 2-1
2.1 The Basic Terminologies of Strings 2-1
2.2 The String Matching Problem and the Brute-Force Algorithm 2-1
2.3 The Knuth-Morris-Pratt Algorithm 2-2
2.4 The Preprocessing Functions of the KMP Algorithm 2-8
2.5 The Basic Ideas of Constant Space String Matching Algorithms 2-19
Chapter 3 The MaxSuffix-Matching Algorithm 3-1
3.1 The Terminologies in the MaxSuffix-Matching Algorithm 3-1
3.2 The Naive-Period function 3-2
3.3 The MaxSuffix-Matching Algorithm 3-7
Chapter 4 The Two-Way Pattern Matching Algorithm 4-1
4.1 The Terminologies in the Two-Way Pattern Matching Algorithm 4-1
4.2 The Two-Way Pattern Matching Algorithm with Short Maximal Suffix 4-2
4.3 The Two-Way Pattern Matching with Magic Decomposition 4-6
Chapter 5 The Sequential Sampling Algorithm 5-1
5.1 The Terminologies in the Sequential Sampling Algorithm 5-1
5.2 The Basic Idea of the Sequential Sampling Algorithm 5-3
5.3 The Simple Text Searching Algorithm For Non-Periodic Patterns 5-4
5.4 The Sequential Sampling Algorithm 5-6
5.5 The Schemes of Sequential Sampling Algorithm for General Pattern Strings. 5-8
5.6 The Time Complexities 5-10
Chapter 6 The Comparisons of the Three Algorithms 6-1
6.1 The Basic Ideas of the Algorithms. 6-1
6.2 The Property of Strings used in the Algorithms 6-1
6.3 Functions in the Preprocessing Phase of the Algorithms 6-1
6.4 Functions in Searching Phase of the Algorithms 6-2
6.5 The Best Cases for the Three Algorithms. 6-2
6.6 The Worst Cases of the Three Algorithms 6-3
6.7 The Complexities of the Algorithms 6-3
6.8 A Table of the Comparisons between the Algorithms 6-4
Chapter 7 Conclusion 7-1
Bibliography 8-1

[A87] Generalized String Matching, Abrahamson, K., SIAM Journal on Computing, Vol. 16, 1987, pp. 1039-1051.
[A90] Algorithms for Finding Patterns in Strings, Aho, A. V., Handbook of Theoretical Computer Science, MIT Press/ Elsevier, Vol. A., 1990, pp. 257-300.
[BM77] A Fast String Searching Algorithm, Boyer, R. S. and Moore, J. S., Communication of the ACM, Vol. 20, 1977, pp. 762-772.
[C89] String Matching and Periods, Crochemore, M., Theoretical Computer Science, Vol. 39, 1989, pp. 149-153.
[C92] String-Matching on Ordered Alphabets, Crochemore, M., Theoretical Computer Science, Vol. 92, 1992, pp. 33-47.
[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.
[CR95] Cubes, Squares and Time-Space Efficient String Matching, Crochemore, M., Rytter, W., Algorithmica, Vol. 13(5), 1995, pp. 405-425.
[D83] Factorizing Words over an Ordered Alphabet, Duval, J. P., Journal of Algorithms, Vol. 4, 1983, pp. 363-381.
[G97] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Gusfield, D., Cambridge University Press, 1997.
[GG91] On the Exact Complexity of String Matching: Lower Bounds, Galil, Z., Giancarlo, R., SIAM Journal on Computing, Vol. 20(6), 1991, pp.1008-1020.
[GG92] On the Exact Complexity of String Matching: Upper Bounds, Galil, Z., Giancarlo, R., SIAM Journal on Computing, Vol. 21(3), 1992, pp.407-437.
[GS83] Time-Space-Optimal String Matching, Galil, Z. and Seiferas, J., Journal of Computer System Science, Vol. 26, 1983, pp.280-294.
[GPR95A] Constant-Space String Matching with Smaller Number of Comparisons: Sequential Sampling, Gasieniec, L., Plandowski, W., Rytter, W., Lecture Notes in Computer Science, Vol. 937, 1995, pp. 78-89.
[GPR95B] The Zooming Method: a Recursive Approach to Time-Space Efficient String-Matching, Gasieniec, L., Plandowski, W., Rytter, W., Theoretical Computer Science, Vol. 147, 1995, pp. 19-30.
[L2001] Computational Biology, Lee, R. C. T., 2001.
[L83] Combinatorics on Words, Lothaire, M., Addison-Wesley, 1983.
[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.
[H93] On Simon’s String Searching Algorithm, Hancart, C., Information Processing Letters, Vol. 47(2), 1993, pp.95-99.
[KMP77] Fast Pattern Matching in Strings, Knuth, D. E., Morris, J. H., Jr. and Pratt, V. R., SIAM Journal on Computing, Vol. 6(1), 1977, pp.323-350.
[MP70] A Linear Pattern-Matching Algorithm, Morris, J. H., Jr. and Pratt, V. R., Report 40, University of California, Berkeley, 1970.
[NR2002] Flexible Pattern Matching in Strings, Navarro, G., Raffinot, M., Cambridge University Press, 2002.
[R2003] On Maximal Suffixes and Constant-Space Linear-Time Versions of KMP Algorithm, Rytter, W., Theoretical Computer Science, Vol. 299(1-3), 2003, pp. 763-774.
[R89] Knuth-Morris-Pratt Algorithm: an Analysis, Régnier, M., In Proceedings of the 14th Symposium on Mathematical Foundations of Computer Science, number 397 in Lecture Notes in Computer Science, 1989, pp.431-444.
[S83] Detections of Periodicities and String-Matching in Real-Time, Journal of Sov. Math., Vol. 22(3), 1983, pp. 1316-1387.
[S93] String Matching Algorithms and Automata, Simon, I., Proceedings of the 1st SouthAmerican Workshop on String Processing, 1993, pp. 151-157.
[S94] String Searching Algorithms, Stephen, G. A., Singapore: World Scientific, 1994.
[V91] Deterministic Sampling – a New Technique for Fast Pattern Matching, Vishkin, V., SIAM Journal on Computing, Vol. 20, 1991, pp.22-40.