logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 1: 012101(2017) https://doi.org/10.1007/s11432-015-0935-3

Strict pattern matching under non-overlapping condition

More info
  • ReceivedFeb 14, 2016
  • AcceptedMay 11, 2016
  • PublishedNov 15, 2016

Abstract

Pattern matching (or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support (or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints (or flexible wildcards) uses the 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. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.


Acknowledgment

Acknowledgments

The work was supported by National Natural Science Foundation of China (Grant Nos. 61229301, 61571180, 61370144), Natural Science Foundation of Hebei Province (Grant Nos. F2013202138, G2014202031), Graduate Student Innovation Program of Hebei Province (Grant No. 220056), and Youth Foundation of Education Commission of Hebei Province (Grant No. QN2014192).

  • Figure 2

    A Nettree for strict pattern matching with gap constraints. (a) A Nettree; (b) the new Nettree after pruning $\langle$9,10,12,14$\rangle$; (c) the new Nettree after pruning $n_3^{11}$; (d) a Nettree with min-root and max-root. Note: The grey nodes are pruned.

  • Table 1   Pattern growth from g to g[0,2]c[0,2]g
    Set $\textit~I^{\rm~g}$ Set $\textit~I^{\rm~g[0,2]c}$ Set $\textit~{I}^{\rm~g[0,2]c[0,2]g}$
    $\langle1\rangle$ $\langle1,2\rangle$ $\langle1,2,3\rangle$
    $\langle3\rangle$ $\langle3,4\rangle$ $\langle3,4,5\rangle$
    $\langle5\rangle$
    $\text{sup}$(rm g) = 3 $\text{sup}$(rm g[0,2]c) = 2 $\text{sup}$(rm g[0,2]c[0,2]g) = 2
  •   

    Algorithm 1 NETLAP-Best

    Require: Pattern $P$, sequence $S$ and the length constraints ($\text{MinLen}$ and $\text{MaxLen}$)

    Output:

  •   

    [b]

  • Table 2   Pattern growth from g to g[0,1]c[0,1]g
    Set $\textit~I^{\rm~g}$ Set $\textit~I^{\rm~g[0,1]c}$ Set $\textit~I^{\rm~g[0,1]c[0,1]g}$
    $\langle1\rangle$ $\langle1,2\rangle$
    $\langle5\rangle$
    $\text{sup}$(rm g) = 2 $\text{sup}$(rm g[0,1]c) = 1 $\text{sup}$(rm g[0,1]c[0,1]g) = 0

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1