Abstract:Pattern matching with gap constraints is one of the key issues of sequential pattern mining. 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. Recently, most researches 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. For these reasons, this article proposes a strict pattern matching with general gaps and one-off condition and shows that this problem is NP-hard. To tackle this issue, a heuristic algorithm, named dynamically changing node property (DCNP), is designed based on nettree which dynamically updates the properties of each node such as the numbers of root paths, leaf paths and root-leaf paths, and thus can get a better occurrence. The above process is then iterated. To effectively improve the speed of DCNP and avoid dynamically updating information of nodes on a large scale, a checking mechanism is applied to allow DCNP update information of nodes only when the occurrence may have repetition. The space and time complexities of DCNP are also analyzed. Experimental results show that DCNP has better performance than other competitive algorithms.