Approximate String Matching Under Different Models

Approximate string matching is an important issue in the research areas of pattern matching. With the rapid development of various disciplines, the research of approximate string matching in many different areas gradually attracts lots of attentions. Particularly, in the emerging disciplines such as computational biology, many models for approximate string matching are proposed. On one hand, these models can be applied widely in many areas. On the other hand, the research on pattern matching under these models is not enough, since most of these models have been proposed for not long time. In view of this situation, we studied the approximate pattern matching problems under three different models, which are property pattern matching, swap matching and blocked pattern matching.For the property matching problem, an off-line matching algorithm is proposed. In that algorithm, the indexes based on compressed suffix arrays are used as the care structure. In order to reduce more space overhead, we gave two solutions for different sizes of the property. In these two solutions, different auxiliary structures are designed in order to meet the higher query efficiency and lower space overhead. Compared with other existing index supporting the property matching, the space overhead of our solution is much smaller. As return, the time complexity of the matching is a little higher.For the swap matching problem, an off-line matching algorithm is proposed, and it is the first off-line swap matching algorithm. At the same time, a more accurate upper bound of the number of swap versions of a pattern is given. In this solution, the existing full text index is used as our index instead of designing new ones. Our solution is more effective than the existing on-line algorithms when the pattern is short.The Blocked Pattern Matching (BPM) Problem is studied. Blocked pattern matching problem is proposed by Julio N. et.al in2011. Now there is little research on this problem. For the blocked pattern matching problem and other related problems, a group of algorithms which improved the time efficiency or space efficiency separately are given. An incorrect statement in Julio’s paper is found, and a solution for the problem which needs less searching time is proposed. The mutated blocked pattern matching problem and fused blocked pattern matching problem are studied, and new algorithms are given.