.png){kind=icon}
返回
Strict pattern matching under non-overlapping condition
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-015-0935-3.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
pattern matching
sequential pattern mining
gap constraint
flexible wildcard
non-overlapping
occurrence
Nettree
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
7.6
论文数:
4.9K
被引数:
8.9K
机构
引用论文
分享收藏Microsurgical reconstruction of the isolated columellar defect with a prelaminated radial forearm free flap. A case report and a review of the literature.png)
Microsurgery
MicrosurgeryIF0
PREAI
分享收藏分享收藏
分享收藏
查看更多内容