Efficient Solving Algorithm For Strict Pattern Matching Under Nonoverlapping Condition

Nonoverlapping conditional pattern mining is a method of gap constrained sequence pattern mining.Compared with similar mining methods,this method is easier to find valuable frequent patterns.The core of the problem is to calculate the support(or the number of occurrences)of a pattern in the sequence,and then determine whether the pattern is frequent.The essence of calculating the support is the pattern matching under nonoverlapping condition.The current studies employ the iterative search to find a nonoverlapping occurrence,and then prune the useless nodes to calculate the support of the pattern.The computational time complexities of these algorithms are O(m~*m~*n~*W),where m,n,and W are the pattern length,sequence length,and maximum gap,respectively.In order to improve the calculation speed of pattern matching under nonoverlapping condition,and effectively reduce sequence pattern mining time,this paper proposes an efficient and effective algorithm,which converts the pattern matching problem into a Nettree,and then starts from the minroot node of the Nettree,and adopts the backtracking strategy to iteratively search the leftmost child to calculate the nonoverlapping minimum occurrence.After pruning the occurrence on the Nettree,the problem can be solved without further searching and pruning invalid nodes.This paper proves the completeness of the algorithm and reduces the time complexity to O(m~*n~*W).On this basis,the paper continues to indicate that there are other three similar solving strategies for this problem,iteratively finds the leftmost parent path from the leftmost leaf,the rightmost child path from the rightmost root,and the rightmost parent path from the rightmost leaf.Extensively experimental results verify the efficiency of the algorithm in this paper,especially,the mining algorithm adopting this method can reduce the mining time.