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

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