Pattern Matching With General Gaps And One-off Conditions

One of the basic problems in computer science is pattern matching, with the development of technology, pattern matching with wildcards has widely used in many areas such as information retrieval, computational biology, and sequential pattern mining ect. Pattern matching with wildcards has more flexibility, which allow each sub patterns interval several characters, it’s more significant.The traditional research focus on pattern matching with non-negative gaps, but the rule of non-negative gaps implies the character’s order in the sequence may limit the flexibility of matching. One-off condition which is always used in sequential pattern mining tasks means that the character of each position in the sequence can be used at most once for pattern matching. For these reasons, we propose the strict pattern matching with general gaps and one-off condition. To handle this issue, we propose a new algorithm based on Nettree.We firstly show that the problem of pattern matching with general gaps and one-off condition is NP-Hard. Then we introduce the conception of Nettree. We propose a heuristic algorithm, named Dynamically Changing Node Property(DCNP). The main idea of DCNP is dynamically updates the properties of each node such as the numbers of root paths, leaf paths and root-leaf paths, thus we can get a better occurrence. Then we iterate the above process. To improve the speed of DCNP effectively and avoid dynamically updating information of nodes on a large scale, a checking mechanism is proposed which means that DCNP will update information of nodes only when the occurrence may have repetition. We also theoretically analyze the space and time complexities of DCNP. Experimental results show that DCNP has better performance than other competitive algorithms.