无间隙约束下无重叠模式匹配的在线求解算法

摘要：

间隙约束序列模式挖掘可以有效地挖掘满足用户特定需要的频繁模式,其核心是间隙约束模式匹配问题.无重叠的模式匹配问题是其中的一种方法,即任何两个出现的相同位置不能共用序列的同一位置的字符.但在无先验知识的情况下,如何设定间隙是难以解决的问题.针对此问题,本文设计了在线匹配算法SNGP-Best,其依据序列串来计算满足查询模式的最多出现数.该算法通过计算模式的长度来确立队列的个数,然后采用在线计算的方式,能够及时计算出满足条件的出现并输出,起到了降低算法空间复杂性的作用.实验结果验证SNGP-Best算法具有良好的求解性能.

关键词：模式匹配、间隙约束、无重叠条件、在线求解算法

所属期刊栏目：40

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目61702157;黑龙江省自然科学基金项目F2017019

在线出版日期：2019-07-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1491-1495