一种带通配符的报文分类方法

为了解决软件ACL报文分类性能慢、无法快速匹配携带通配符规则的问题,提出了一种基于线性表递归求解的报文分类方法。采用可动态伸缩的hash链表,根据报文的七元组计算hash key进行快速查找。针对包含通配符的表项,先采用线性链表缓存通配符,再通过迭代链表快速找到报文对应的匹配域,解决软件转发报文匹配性能问题。同时利用交换机硬件MAC芯片的TCAM资源,进一步加速软件转发ACL的匹配性能。

带通配符和One-Off条件的序列模式挖掘

很多应用领域产生大量的序列数据.如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务.研究这样一个问题:给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符.在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性.

TwigStar——快速处理XML Twig查询中含通配符*的算法

XMLTwig查询可以表示为一棵带标签结点的查询树,它支持对XML文档进行带有复杂谓词的结构或内容查询.整体(holistic)Twig查询算法已经被公认为XML查询处理的核心算法.很多学者提出了大量基于整体处理的XML Twig查询算法.但是目前已有的算法都只适合于Twig查询中不包含通配符*的情况.而当Twig查询中包含通配符*时,一种简单而直接处理的方法就是,把被查询文档中的所有结点元素都读到内存,把这些元素都看做通配符*所对应的元素,然后按照已有的算法进行查询处理.显然这种方法是不合理的,它会增加大量I/O开销.因此提出了一种有效地支持通配符*的查询处理算法.通过建立索引,它可以很好地处理含通配符*的查询,从而可以避免不必要的I/O开销.最后通过实验证明,算法要明显好于已有的算法.

提高文献查全率和查准率的有效途径——逻辑运算符、位置算符和通配符的灵活运用

逻辑运算符、位置算符和通配符是文献检索中经常使用的检索手段,本文首先概述了它们的使用原理,然后详细介绍了在几个常用数据库中的使用技巧,最后通过具体实例解析了在数据库中的应用,以便为广大的科技工作者和情报检索人员提供有益的参考。

标准模型下可证安全的通配符基于身份加密方案

针对通配符基于身份加密方案中安全归约不紧密以及运算量大的缺陷,利用双线性对和分级基于身份加密的思想提出标准模型下可证安全的通配符基于身份加密方案.新方案取得紧密的安全归约,同时加密算法不需要对运算,解密算法仅仅需要2个对运算.安全性分析表明,基于改进判定双线性Diffie-Hellman指数假设下。

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

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

满足非重叠条件的带有通配符序列模式挖掘

很多应用领域产生大量的序列数据,例如:基因序列,超市购买记录,股市交易数据,文本序列等.如何从这些序列数据中挖掘具有重要价值的模式已成为序列模式挖掘研究的主要任务.本文研究带有通配符的序列模式挖掘问题,给定支持度阈值和间隔约束,从序列数据库中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.本文设计一种基于层次图的带有通配符序列模式挖掘算法PMLG,利用层次图结构在多项式时间和空间复杂度内构建和存储模式在序列中满足间隔约束的所有出现位置,采用深度优先搜索策略对图进行遍历,计算模式的支持度,其中模式的任意两次出现的相同位置都不共享序列中同一位置的字符,即满足非重叠出现.在生物DNA序列上的实验表明,PMLG比相关的序列模式挖掘算法具有更好的时间性能和完备性.

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

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

支持通配符的多步长Trie树包分类方法

文章提出一种使用支持通配符的多步长tire树结构对数据包进行分类的算法WMTrie,通过增加额外的分支来处理CIDR地址产生的前缀型规则,从而提高了匹配算法的性能。实验结果表明,WMTrie算法在不同规模的规则集上的性能比EGT-PC算法均有所提高。

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

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

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

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

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

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

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

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

具有独立通配符间隔的模式匹配算法

模式匹配作为一种关键技术已被广泛应用于生物序列分析和文本过滤等领域.通配符间隔可以匹配特定长度子序列,为模式匹配问题带来了更多的灵活性.为增加灵活性和一般性给出一种新的模式匹配问题定义,其中通配符间隔可以独立设置,并基于模式分解设计出一种有效的计算匹配数量的算法.实验结果显示,与同类算法相比本算法在性能上具有更优的时间复杂度和空间复杂度.

基于通配符和长度约束的近似模式匹配算法

针对近似模式匹配算法在处理带有灵活通配符和长度约束近似模式匹配(APMWL)问题时只能解决替换操作,提出一种基于动态规划的编辑距离矩阵(EDM)构造方法,设计了基于EDM的近似模式匹配算法APM,可以处理近似匹配中的三种编辑操作,即插入、替换和删除操作。此外,根据文本中字符是否允许被重复使用的约束条件,设计APM-OF算法。实验结果表明,APM和APM-OF与同类算法相比具备显著的优势:与Sail_Approx匹配算法实验对比,获取解的平均增长率分别达到8.34%和12.37%;将APM-OF算法应用至模式挖掘中,挖掘出的频繁近似模式个数为OneoffMining算法的2.07倍。

增强DOS文件名通配符的使用范围

一些以DOS命令不允许使用文件名通配符“*”或“?”来指定文件名,这给用户在操作使用过程中带来了诸多不便。本文将向您介绍一种利用FOR子命令编写批处理程序,从而达到支持使用DOS文件名通配符来指定文件名的方法。

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

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

通配符在WORD查找与替换中的问题与解决

用Word对文档进行编辑修改时，经常会遇到为一篇文章中所有引号引起的内容设置所需格式问题，在Word的查找与替换命令中利用通配符就可解决这一问题。

带通配符的多序列模式挖掘

带有通配符的多序列模式挖掘在文本检索、网络安全、生物科学等领域中具有很重要的作用.通过挖掘多序列模式,能够透彻的了解序列之间的联系,在各个领域中具有重要的现实意义.在已有的工作中,随着多序列集长度的增大,挖掘的规模呈现指数级增长.研究这样一个问题:给定多条序列s1,…,sn,支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一个有效的算法M-OneOffMine,模式在序列中的出现满足one-off条件.在生物DNA序列上的实验结果表明,M-OneOffMine算法比相关的序列模式挖掘算法具有更好的时间性能.

带通配符的模式匹配问题及其解空间特征分析

随着生物信息学、信息检索等领域的发展,带有通配符和长度约束的模式匹配问题引起了广泛关注。该问题扩展了精确模式匹配问题,使匹配更加灵活,同时也增加了匹配的复杂性,极大地提高了非线性匹配算法的复杂度。求解该问题的匹配算法的效率与问题的解空间密切相关,而目前针对该问题的解空间及其特征尚缺乏系统的研究。鉴于此,描述了该问题的解空间,并分析了解空间的可分性。之后,提出解空间划分算法SPLIT,并分析了SPLIT的时间复杂性。实验部分以3个匹配算法为对照,在真实DNA数据集下,使用了5109组模式。实验结果表明,SPLIT不影响匹配解的结构,且可以有效降低非线性匹配算法的时间消耗。