Research On Strict Pattern Matching Under Non-overlapping Condition

Sequential pattern mining is a branch of data mining, while sequential pattern matching is an important foundation of sequential pattern mining. Using mining method to analyse biological sequences, customer purchasing lists and network daily records, we can achieve kinds of protential principles and interesting information from big data. Among these investigations, it is more challenging that biologial sequential matching and mining with wildcards gap constraints compared with traditional string matching methods. What’s more, there are a lot of conditions and constraints which have derived. A state-of-the-art sequential pattern mining algorithm, which based on a non-overlapping condition and given the pattern with gap constraints, uses the maximum number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. Consequently, in this paper, we investigate strict pattern matching under the non-overlapping constraint.The main research content and related work of this thesis are as follows:(1)We present the definition of strict pattern matching under the non-overlapping condition.(2)We show that the problem of strict pattern matching under the non-overlapping condition is in P.(3)We propose an effecitive algorithm, named NETLAP-Best, which employs a Nettree.(4)Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.Recapitulating, in this paper, we not only prove that the problem of strict pattern matching under the non-overlapping condition is in P, but also propose effective solving algorithm NETLAP-Best. Extensive experimental results not only validate the completeness of this algorithm, but also suggest it is more efficient than INSgrow.