带任意长度通配符的模式匹配

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.     

带可变长度通配符的模式匹配算法

针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时,需要的时间是多项式级别,而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI（pAttern mAtching with wIldcards） 算法,计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为[O(n+m+α)]和[O(m+B)],其中[n]和[m]分别表示文本和模式的长度,[α]是所有子模式在文本中出现的数目,[B]是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明,AAI算法与同类算法相比具备显著的优势。     

带弱通配符的模式匹配及其在时序分析中的应用

针对模式匹配的准确性和灵活性问题,提出了一种基于弱通配符的匹配算法,以快速定位重要的时间点,辅助用户决策。首先通过数据预处理得到编码字符串序列,然后定义具有特殊语义的弱通配符及区间长度,最后设计一种高效的模式匹配算法。在时序分析中,模式反映了数据的变化趋势,预示着事件的发生。传统的精确匹配受噪声的影响比较大,匹配的灵活性低。通过添加弱通配符可以兼顾匹配过程的灵活性和准确性。油田产量与股票交易数据实验表明,所提方法较精确匹配而言,能够更有效地找到符合用户要求的模式。     

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

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

带有通配符和长度约束的模式匹配问题求解模型

讨论了带有通配符和长度约束的模式匹配(PMWL)问题,其中模式由子模式序列集组成,两个相邻子模式的间隔在一定长度范围内。针对PMWL问题,已有工作包括设计启发式求解算法和对特殊情况进行完备性分析,然而还需要构建问题的基础求解模型。借鉴约束可满足问题框架,构建了由变量、值域和约束组成的三元组求解模型,对PMWL问题的基本概念和基本性质给出了形式化描述。最后,给出了算法求解PMWL问题的特定条件下的完备解。     

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.     

一个高效安全三方带通配符模式匹配协议

安全多方计算(secure multiparty computation, SMPC)是实现分布式计算安全的重要技术,其主要考虑在多个相互独立的实体之间协同完成某项任务的计算,同时要实现输入信息的隐私保护.模式匹配在信息检索、生物工程、人脸识别等领域有着广泛应用,在实现匹配功能的同时保证查询模式及结果的隐私是当下研究的重点.带通配符模式匹配是模式匹配的一种类型,其允许查询模式中可以存在某些通配符信息,因此能够实现某一类信息的批量查询.传统的安全带通配符模式匹配协议中主要涉及数据库方和查询方2个实体,鉴于当下数据共享技术的发展,这种模型难以刻画更多的应用场景.以实际应用出发,首次在三方场景下研究安全带通配符模式匹配协议的构造.首先考虑一个具体的安全三方带通配符模式匹配功能函数,并给出其形式化描述和功能性分析;然后,基于秘密分享(secret sharing)和外包茫然传输协议(outsourced oblivious transfer, OOT)在半诚实敌手模型下给出协议构造,并通过茫然传输扩展(oblivious transfer extension)技术提高协议效率,协议仅需要3轮交互,且计算和通信复杂度为O(k)和O(nm),其中n和m是2个数据提供方的输入长度,k是实现OT扩展协议的基数,其值远小于nm.     

模式特征对带有通配符和长度约束的模式匹配问题的影响

带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便,却也造成求解上的困难。目前没有任何多项式算法能得到该问题的完备解,同时也缺少足够的完备性分析。文中认为模式特征是影响PMWL完备性的关键因素,并提出模式重复度的概念,记为rep。证明在rep=0的限定条件下PMWL的完备性,同时分析rep>0时PMWL不完备的原因。实验以近似比为指标,说明rep对PMWL完备性的影响。     

一种支持通配符查询的XML模式匹配算法

XML查询语言当中,包含通配符*的查询能够方便有效地满足一些特殊查询要求,但在大数据时代下XML文件容量与结构复杂性不断增加,现有支持通配符查询的算法需消耗巨量内存来解析XML,并且在对嵌套通配符处理时需要大量的单路径匹配操作和局部结果的缓存。针对此现状,结合现有经典算法,提出一种新的、能够高效解决小枝模式当中含有通配符*的查询算法-WTwigList。该算法首先对查询模式进行通配符的层次关系处理,减少不必要的通配符匹配,以数据流形式解析XML文件并执行局部的扩展Dewey编码,经过滤操作后得到有序的叶子节点编码列表,在列表中执行匹配操作得到结果;其次在真实和合成数据集上做大量实验,结果表明WTwigList算法与现有算法相比,能够有效提高查询效率,在空间效率上具有一定优势,且能够快速准确地处理查询模式中P C关系。     

字符分布特征对带有通配符串匹配问题的影响

近年来,字符串匹配问题被不断扩展。其中,具有代表性的是在模式中引入可变长度的通配符,本文称之为PMWL问题。针对此问题,已有工作分析了在不同的模式特征下,匹配数Ω随文本长度增加呈指数级增长。本文同时考虑文本分布特征和模式特征,建立了期望模型E(Ω)＝n*D*π(P),其中n为文本长度,D为模式中各通配符跨度的乘积,π(P)为基于字符分布的模式出现概率。实验部分,在人工随机数据和DNA真实数据上验证了E(Ω)的准确性,得到预测误差率分别为1.8%~3.2%和4.7%~7.8%;在不同字符分布中,分析了模式模长和通配符跨度对匹配数Ω的影响。E(Ω)模型揭示了Ω的增长趋势不一定呈指数级,而取决于π(P)和D的共同影响。此外,E(Ω)模型能够在线性时间内得到近似完备解。     

支持带有通配符的字符串匹配算法

研究了查询字符串中含有通配符"*"以及"?"两种情况下的字符串匹配问题,其中,"*"代表任意长度的字符串,"?"代表字母表中任意一个字符。由于gram索引结构在空间大小以及查询效率上的优势,将gram索引结构用于带通配符的字符串匹配问题。通过将带有通配符的查询字符串分解为若干不含通配符的查询片段,成功地将带有通配符的复杂查询问题转化为不含通配符的简单精确子串匹配问题。同时在片段查询过程中运用长度过滤、位置过滤以及计数过滤等方法来提高查询速度。     

协同DNA计算机解空间问题的模块化设计方案

提出了一种基于检测型生物芯片的协同DNA计算机解空间问题的模块化解决方案。为了解决解空间检测这个问题，该文总结了目前典型的DNA计算模型中所用到的生物检测技术，在先前的协同DNA计算机基本组成原理模型的基础上，结合了当前检测型生物芯片技术的发展趋势，提出了解决方案，并对各模块的工作原理、功能等进行了介绍，给出了问题与展望。     

基于特征空间轨迹匹配法的业务语音自动识别工具研究

该测试工具的主要目的是实现电话业务语音的自动识别功能，对从电话交换机采集到的业务语音输出进行分析，检验交换机的输出是否正确。识别对象主要为无失真传输语音。采用基于特征空间语音轨迹的声学特征模式匹配法组织识别内核，为了实现识别的高速性和高效性，特别讨论了识别对短时能量特征的充分利用以及判决的策略，并在最后对测试数据进行了分析。