| Pattern matching is a basic and classic problem in the area of computer science, as wellas in many other areas, such as biological sequence analysis, text retrieval, data mining, andthe sensor network.In the study of pattern matching, the wildcard is usually introduced into this problem inorder to meet the needs of users. Only the “?”and “*” were used as the wildcard in thetraditional way while in recent years, the pattern matching problem with gap constrainedbecomes more and more important in the music information retrieval and data mining areas.This kind of pattern matching can be described as a string P=p0[min0, max0]p1…[minj-1,maxj-1]pj…[minm-2, maxm-2]pm-1, where minj-1and maxj-1, respectively, are the meaning of thenumber of characters which can be matched between pj-1and pj. In the study of patternmatching with the wildcard, one-off condition is a more challenging subject. It means thatone position can’t occur in more than one occurrence. However, the current study wasfocused on exact pattern matching. The study of approximate pattern matching is moremeaningful.In this paper we analyze the approximate pattern matching with one-off condition andgap constrained. The current algorithm named SAIL-APPROX which was used to solve theproblem can not find the occurrence in high accuracy. This paper firstly gives the formaldefinition of this problem and then proposes a new nonlinear data structure to solve thePattern Matching with Wildcards and Length Constraints with one-offs conditions. Finally, aheuristic algorithm, SBO-APP algorithm is designed based on the nettree.We have twostrategies in this algorithm, so we can get more than one occurrence and select the better oneas the final occurrence,and each iteration of the procedure we got one more occurrence, untilthe occurrence is found out.A large number of comparative experiments are used to validate the correctness of thealgorithm and the superiority of the solution with the approximate pattern matchingalgorithm. |
PDF Full Text Request