%0 Journal Article
%T 一般间隙及一次性条件的严格模式匹配
%A 柴欣？
%A 贾晓菲？
%A 武优西？
%A 江贺？
%A 吴信东？
%J 软件学报
%P 1096-1112
%D 2015
%R 10.13328/j.cnki.jos.004707
%X 具有间隙约束的模式匹配是序列模式挖掘的关键问题之一.一次性条件约束是要求序列中每个位置的字符最多只能使用一次,在序列模式挖掘中采用一次性条件约束更加合理.但是目前,间隙约束多为非负间隙,非负间隙对字符串中每个字符的出现顺序具有严格的约束,一定程度上限定了匹配的灵活性.为此,提出了一般间隙及一次性条件的严格模式匹配问题;之后,理论证明了该问题的计算复杂性为np-hard问题.为了对该问题进行有效求解,在网树结构上构建了动态更新结点信息的启发式求解算法(dynamicallychangingnodeproperty,简称dcnp).该算法动态地更新各个结点的树根路径数、叶子路径数和树根-叶子路径数等,进而每次可以获得一个较优的出现;之后,迭代这一过程.为了有效地提高dcnp算法速度,避免动态更新大量的结点信息,提出了checking机制,使得dcnp算法仅在可能产生内部重复出现的时候才进行动态更新.理论分析了dcnp算法的时间复杂度和空间复杂度.大量实验结果验证了dcnp算法具有良好的求解性能.
%K 一般间隙
%K 模式匹配
%K 一次性条件
%K 网树
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=4707&flag=1