臺灣博碩士論文加值系統

在解決精確字串比對問題的許多演算法中，離散旋積方法是一個簡單的方法。在這篇論文中，首先分析一個機率問題：一個樣本字串出現在另一個較長的本文字串中的機率？在論文中假設所有的樣本字串與本文字串都是隨機產生的，依照這個假設，我們得到了一個近似的公式，可以知道當樣本字串的長度增加時，樣本字串在本文字串中出現的機率將快速地下降至0。根據這個結果，論文中提出一個提前終止離散旋積程序的演算法。在離散旋積程序進行的過程中，當我們發現樣本字串的一個字首沒有出現在本文字串中時，可以提前終止離散旋積程序。依照實驗的結果，提前終止的離散旋積演算法，可以有效率的解決精確字串比對問題。除此之外，我們比較了離散旋積演算法，以及同樣用來解決精確字串比對問題的位移加法演算法。根據論文中的討論，我們知道離散旋積與位移加法演算法的概念是相同的。

In this thesis, we introduce discrete convolution method on solving the exact string matching problem. Based on the assumption that all the text and pattern strings are generated randomly, we derived an equation which can approximate the probability of appearing of a pattern string in a text string. From this equation, we see that the probability that a pattern string appears in a text string reduces to 0 quickly as the length of the pattern string increases. Because of this observation, we introduce an algorithm based on the discrete convolution method with early termination. The algorithm terminates as soon as it discovers that a prefix of the pattern string does not appear in the text string. We show that the discrete convolution method with early termination is quite efficient to solve exact string matching problem for randomly generated text and pattern strings. In this thesis, we also show that the shift-add algorithm is equivalent to and can be implemented by the discrete convolution.

CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND 1
1.2 THESIS ORGANIZATION 1
CHAPTER 2 DISCRETE CONVOLUTION METHOD 3
2.1 DEFINITION OF DISCRETE CONVOLUTION FOR STRINGS 3
2.2 DISCRETE CONVOLUTION FOR SOLVING EXACT STRING MATCHING PROBLEM 4
2.3 EXAMPLES OF DISCRETE CONVOLUTION 6
2.4 OBSERVATIONS AND IDEAS 9
CHAPTER 3 PROBABILITY ANALYSIS 11
3.1 INCLUSION-EXCLUSION PRINCIPLE 11
3.2 APPEARING OF A STRING IN ANOTHER STRING 12
3.3 DISCUSSING AND DIVIDING THE PROBLEM 12
3.4 APPROXIMATING THE PROBABILITY BY PART 1 14
CHAPTER 4 PROBABILITY FROM EQUATION AND EXPERIMENTS 18
4.1 PROBABILITY FROM THE DERIVED EQUATION 18
4.2 PROBABILITY FROM RANDOMLY GENERATED TEXT AND PATTERN STRINGS 19
CHAPTER 5 DISCRETE CONVOLUTION WITH EARLY TERMINATION 20
CHAPTER 6 EXPERIMENTS 23
CHAPTER 7 DISCRETE CONVOLUTION AND SHIFT-ADD ALGORITHM 27
7.1 SHIFT-ADD ALGORITHM 27
7.2 RELATIONSHIP BETWEEN DISCRETE CONVOLUTION AND SHIFT-ADD METHOD 35
7.3 A MODIFIED VERSION OF SHIFT-ADD ALGORITHM 41
CHAPTER 8 CONCLUDING REMARKS AND FUTURE WORKS 47

[1] Knuth, D.E., Morris, J.H., Pratt V.R. Fast pattern matching in strings, SIAM Journal on Computing, 6(1), 1977, pp.323-350.
[2] Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W. and Rytter, W. Speeding up on two string matching algorithms, Algorithmica, Vol.12, 1994, pp.247-267.
[3] Boyer, R.S. and Moore, J.S. A fast string searching algorithm, Communications of the ACM 20, 10, 1977, pp.762-772.
[4] Horspool, R.N. Practical fast searching in strings Software Practice and Experience, Vol.10, No. 6. (1980), pp. 501-506
[5] Fischer, M.J. and Paterson, M.S. String-Matching and other products, SIAM-AMS Proceedings, Vol.7, 1974, pp.113-125 (In "Complexity of Computation", R.M. Karp.)
[6] R. C. T. Lee. String matching, 2011. (Unpublished)
[7] Baeza-Yates, R.A. and Gonnet, G.H. A new approach to text searching, Communications of the ACM, Vol.35(10), 1992, pp.74-82.
[8] H. Kwakernaak, R. Sivan, Modern signals and systems. Prentice-Hall, 1991.
[9] Lee, R. C. T., Chiu, M. C. and Lin, J. S. Communications engineering, essentials for computer scientists and electrical engineers, John Wiley &; Sons, 2007.