  Pattern matching can be used to calculate the support of patterns, and is a
key issue in sequential pattern mining (or sequence pattern mining).
Nonoverlapping pattern matching means that two occurrences cannot use the same
character in the sequence at the same position. Approximate pattern matching
allows for some data noise, and is more general than exact pattern matching. At
present, nonoverlapping approximate pattern matching is based on Hamming
distance, which cannot be used to measure the local approximation between the
subsequence and pattern, resulting in large deviations in matching results. To
tackle this issue, we present a Nonoverlapping Delta and gamma approximate
Pattern matching (NDP) scheme that employs the (delta, gamma)-distance to give
an approximate pattern matching, where the local and the global distances do
not exceed delta and gamma, respectively. We first transform the NDP problem
into a local approximate Nettree and then construct an efficient algorithm,
called the local approximate Nettree for NDP (NetNDP). We propose a new
approach called the Minimal Root Distance which allows us to determine whether
or not a node has root paths that satisfy the global constraint and to prune
invalid nodes and parent-child relationships. NetNDP finds the rightmost
absolute leaf of the max root, searches for the rightmost occurrence from the
rightmost absolute leaf, and deletes this occurrence. We iterate the above
steps until there are no new occurrences. Numerous experiments are used to
verify the performance of the proposed algorithm.
