精確字串比對演算法上的一些結果

Some Results on Exact String Matching Algorithm

劉貴文(Kuei-Wen Liu)

指導教授 ： 李家同

國立暨南國際大學/科技學院/資訊工程學系/碩士(2008年)

https://doi.org/10.6837/NCNU.2008.00262

摘要

這裡有二個字串問題。 一個是精確字串比對問題 (Exact String Matching Problem), 另一個則是找字串週期問題 (Period of String)。
精確字串比對問題是給定二個字串T跟P，T 字串長度為n, T字串長度為n。n大於等於m。 精確字串比對問題上我們介紹二個演算法。第一個濵算法是首先從P字串來找出一個位置，此位置使得P在T上比對時給予多個移動值。我們的演算法介紹如何從P求出這個位置。
第二個演算法是先在T上開n/m 個重疊比對範圍，長度為2m-1。此比對範圍名為寬闊比對範圍。在每一個寬闊比對範圍，從中間往右方向尋找是否有P字尾出現。如果P字尾出，尋求找所對應的P字首。P字尾或P字首是否出現我們使用改良迴旋方法。
字串週期問題是給定一個字串T。T字串長度為n。 把T字串的週期利用bit parallel 方法找出來。所以在這個論文中，我們會介紹一個演算法如何在線形時間內找出字串的週期。

關鍵字

精確字串比對問題, 樣本搜尋，字串週期，改良迴旋方法

並列摘要

In this paper, we introduce two algorithms for stringology. One is to solve the exact string matching problem and the other is to find the string cycle (period of a string).
In the exact string matching problem, we are given two strings T=t1t2...tn and P=p1p2...pm. We are asked to find all occurrences of P in T. Our searching method is based upon a single character rule. Consider a location i in P. Suppose that pi is aligned with tj and pi <> tj. We then must move P in such a way that some pk=tj will be aligned with tj. In the thesis, we propose a method to find the optimal location i.
We also modified a string matching approach, named wide window approach, which divides the text into n/m overlapping windows of size 2m-1. In the windows, the approach attempts m possible occurrence positions in parallel. It firstly searches pattern suffixes from middle to right with the modified convolution method, shifts the window directly when it fails, otherwise, scans the corresponding prefixes backward with the modified convolution method again.
For the period of string problem, we are given a string T and we are asked to find the periods of T. Our algorithm is based upon the bit parallel approach.

並列關鍵字

Exact String Matching Problem, Pattern Searching, String Period Problem, Bit Parallel Approach, Modified Convolution Method.

參考文獻

[A90] Algorithms for finding patterns in strings, Aho, A. V., Handbook of Theoretical Computer Science, Volume A, Algorithms and complexity, 1990, pp. 255-300.

[AC91] Optimal canonization of all substrings of a string, Apostolico, A. and Crochemore, M., Information and Computation, Vol. 95, No. 1, 1991, pp. 76-95.

[AKLLLR2000] Text indexing and dictionary matching with one error, Amir, A., Keselman, D., Landau, G. M., Lewenstein, M., Lewenstein, N. and Rodeh, M., Journal of Algorithms, Vol. 37, 2000, pp. 309-325.

[BR92] Average running time of the Boyer- Moore-Horspool algorithm, Baeza-yates, R. A. and Régnier, M., Theoretical Computer Science, Vol. 92, No. 1, 1992, pp. 19-31.

[BC92] Éléments d'algorithmique, Beauquier, D., Berstel, J. and Chrétienne, P., 1992, Chapter 10, pp. 337-377, Masson, Paris.