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

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

子网树求解一般间隙和长度约束严格模式匹配

具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(strict pattern matching with generalgaps and length constraints,简称SPANGLO).该问题具有如下4 个特点:它是一种严格的精确模式匹配;允许序列中任意位置的字符被多次使用;模式串中可以包含多个一般间隙;对出现的总体长度进行了约束.最坏情况下,一个SPANGLO 实例将转换出指数个非负间隙的严格模式匹配实例.为了有效地解决该问题,提出了子网树及其相关概念和性质.在此基础上提出了求解算法Subnettree Spanglo(SETS),并给出算法的正确性和完备性证明,同时指出该算法的空间复杂度与时间复杂度分别为O(m×MaxLen×W)和O(MaxLen×W×m²×n),其中,m,n,MaxLen和W分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性.     

基于强社交图的多约束信任图模式增量匹配算法

针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法.为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下文背景信息,提出维护强社交图索引的算法INC-SSG和多约束图匹配的增量算法SSG-IncMGPM,当面对强社交图结构的变化时能快速有效地识别多约束图模式匹配结果.通过对五个真实社交图的实证研究,验证了该方法在效率和有效性方面的优越性.     

基于全集的复杂模式匹配

模式匹配是数据集成和数据转换中的重要问题.现有的模式匹配方法大多集中于发掘模式间的1:1匹配,然而,在现实世界模式之间除了1:1匹配还包括很多的复杂匹配.提出一种基于全集的复杂模式匹配方法,它可应用模式和映射的全集为被匹配模式添加信息;然后,利用多个具有特殊目的的检索程序分别对候选空间的特殊部分进行检索,发掘1:1和复杂匹配;最后通过学习全集中元素及元素间关系的统计,自动推导出可过滤候选匹配的约束,生成最优的匹配.实验表明,该方法不仅能全面地发掘模式间匹配,与其他复杂模式匹配方法相比,还具有较高的查全率和查准率.     

一种带稀疏间隙约束的并行模式匹配算法

带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（pattern matching with sparse gaps constraint based on suffix automaton index）.SGPM-SAI通过对文本串预处理,建立一种称为W-SAM的图索引结构,然后对模式串分段查找EndPos集合,最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明：在不考虑预处理时间的情况下,相比几种最典型的模式匹配算法（KMP,BM,AC,suffix array）,SGPM-SAI算法性能优势显著,至少高出3~5倍.通过与SAIL算法的最新优化版本（SAIL-Gen）进行比较,在稀疏间隙约束条件下,SGPM-SAI的性能要显著优于SAIL-Gen算法.此外,为有效利用现代处理器的大规模并行处理单元,提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明：Parallel SGPM-SAI算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.     

一般间隙近似无重叠模式匹配

具有间隙约束条件模式匹配问题是序列模式挖掘问题的基础与核心.无重叠模式匹配是其中的一种方法,当前研究是在间隙为正的精确模式匹配,为了进一步增加匹配的灵活性,本文探索了一般间隙近似无重叠模式匹配问题.本文提出一种有效的求解算法,该算法首先将问题转化为网树;然后为了有效地避免可行解丢失,提出近似监测机制以解决该问题;采用迭代搜索最左孩子策略的方式寻找无重叠出现;之后在网树上剪枝找到的无重叠出现,并迭代上述过程直至没有新的无重叠出现产生.最后本文理论分析了算法的空间复杂度和时间复杂度.大量实验结果验证了本文算法具有较好的求解质量及求解效率.     

一般间隙及一次性条件的严格模式匹配

具有间隙约束的模式匹配是序列模式挖掘的关键问题之一.一次性条件约束是要求序列中每个位置的字符最多只能使用一次,在序列模式挖掘中采用一次性条件约束更加合理.但是目前,间隙约束多为非负间隙,非负间隙对字符串中每个字符的出现顺序具有严格的约束,一定程度上限定了匹配的灵活性.为此,提出了一般间隙及一次性条件的严格模式匹配问题;之后,理论证明了该问题的计算复杂性为NP-Hard问题.为了对该问题进行有效求解,在网树结构上构建了动态更新结点信息的启发式求解算法(dynamically changing node property,简称DCNP).该算法动态地更新各个结点的树根路径数、叶子路径数和树根-叶子路径数等,进而每次可以获得一个较优的出现;之后,迭代这一过程.为了有效地提高DCNP算法速度,避免动态更新大量的结点信息,提出了Checking机制,使得DCNP算法仅在可能产生内部重复出现的时候才进行动态更新.理论分析了DCNP算法的时间复杂度和空间复杂度.大量实验结果验证了DCNP算法具有良好的求解性能.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

简单模式的一种匹配方法

模式匹配是包括LFC在内的大多数函数式语言都具有的特点。文章在LFC语言现有的模式匹配实现方法的基础上,结合常用的模式匹配树的构造思想,设计了一种模式匹配方法。这种模式匹配方法通过计算给定模式集合的扩展集合来构造模式匹配树。虽然在最坏情况下,该方法与LFC现有实现的空间复杂度一样,但当函数定义是部分构造式,而定义中的非项模式覆盖了较多项时,这种模式匹配方法可以避免LFC语言现有实现中较大的编码空间。这个方法略作修改即可用于复杂的嵌套模式,是一种通用的模式匹配方法。     

基于多层次模式匹配的三维重建方法研究

本文面向实际工程图样,首先,借助工程图样语义分析,设计了一组识别模式:尺寸约束模式、投影约束模式及组合方式约束模式;其次,提出了一种基于多层次模式匹配的三维重建新方法,根据组合体的复杂程度和识别问题的类型,分别应用上述三种识别模式,分阶段、分层次地对组合体中的基元体进行识别,然后根据识别出的基元组合关系对组合体进行重建.最后,基于该方法建立了一个三维重建原型系统一.