%0 Journal Article
%T 一般间隙近似无重叠模式匹配
%A 武优西
%A 闫文杰
%A 陈彤
%A 高雪冬
%J 中山大学学报（自然科学版）
%D 2020
%X 摘要 具有间隙约束条件模式匹配问题是序列模式挖掘问题的基础与核心.无重叠模式匹配是其中的一种方法,当前研究是在间隙为正的精确模式匹配,为了进一步增加匹配的灵活性,本文探索了一般间隙近似无重叠模式匹配问题.本文提出一种有效的求解算法,该算法首先将问题转化为网树;然后为了有效地避免可行解丢失,提出近似监测机制以解决该问题;采用迭代搜索最左孩子策略的方式寻找无重叠出现;之后在网树上剪枝找到的无重叠出现,并迭代上述过程直至没有新的无重叠出现产生.最后本文理论分析了算法的空间复杂度和时间复杂度.大量实验结果验证了本文算法具有较好的求解质量及求解效率
%K 模式匹配
%K 网树
%K 一般间隙
%K 近似
%K 无重叠
%U http://xwxt.sict.ac.cn/CN/abstract/abstract5285.shtml