无重叠条件严格模式匹配的高效求解算法

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现,然后剪枝无用结点的方式计算模式的支持度,其计算时间复杂度为O(m×m×n×W),其中,m,n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度,从而有效地降低无重叠条件序列模式挖掘时间,提出了一种高效的算法,该算法将模式匹配问题转换为一棵网树,然后从网树的最小树根结点出发,采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现,在网树上剪枝该出现后,无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性,并将该算法的时间复杂度降低为O(m×n×W).在此基础上,继续指明该问题还存在另外3种相似的求解策略,分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能,特别是在序列模式挖掘中,应用该方法的挖掘算法可以降低挖掘时间.

无重叠条件下的Top-k序列挖掘

无重叠条件序列模式挖掘是一种带间隙约束的序列模式挖掘方法,能够有效地克服当前此类挖掘中的问题.但是当前的方法仅仅用于挖掘频繁模式,为了高效地挖掘最为频繁的k种无重叠序列模式,本文提出了"Gfp-tree(Gain-frequence-patterntree)"这一数据结构,构建了无重叠条件下完备的Top-k模式挖掘算法.该算法基于Apriori性质,不预先设定支持度阈值,而是在挖掘过程中生成并动态调整,直到挖掘过程结束.有效减少了候选模式的生成数量,节约了运行时间.实验表明,该算法具有较高的效率.

无重叠条件模式匹配的在线求解算法

无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点。为了解决该问题,设计了一种在线求解算法,该算法一边读入序列串,一边在流网树中寻找符合约束条件的树根-树叶路径,以快速剪枝无用节点,从而加快了匹配速度。与离线算法的空间复杂度相比,在线算法的空间复杂度为O(m×maxlen×W),这里m,maxlen和W分别表示模式串长度、模式最大长度约束和最大间隙约束。实验结果不仅验证了算法的完备性,与现有算法相比,在内存占用上均有较大性能的提升。

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

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