Strict pattern matching under non-overlapping condition

详细信息    查看全文

• 作者：Youxi Wu ; Cong Shen ; He Jiang ; Xindong Wu
• 关键词：pattern matching ; sequential pattern mining ; gap constraint ; flexible wildcard ; non ; overlapping ; occurrence ; Nettree
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：60
• 期：1
• 全文大小：326 KB
• 刊物类别：Computer Science
• 刊物主题：Chinese Library of Science
  Information Systems and Communication Service
  
• 出版者：Science China Press, co-published with Springer
• ISSN：1869-1919
• 卷排序：60

文摘

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.