检索结果-南通市图书馆

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

在线全文

学校读者我要写书评

暂无评论

模式识别与人工智能 2012年第6期25卷 1013-1021页

作者：王海平胡学钢谢飞郭丹吴信东合肥工业大学计算机与信息学院计算机科学与技术系合肥230009 合肥师范学院计算机科学与技术系合肥230601 Department of Computer Science The University of Vermontburlington05405

带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便,却也造成求解上的困难.目前没有任何多项式算法能得到该问题的完备解,同时也缺少足够的完备性分析.文中认为模式特征是影响PMWL完备性的关键因素,并提出模式重复度的概念... 详细信息

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

关键词：模式特征完备性通配符模式匹配

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

在线全文

学校读者我要写书评

暂无评论

电子学报 2013年第10期41卷 2082-2086页

作者：明洋王育民长安大学信息工程学院陕西西安710064 西安电子科技大学综合业务网理论及关键技术国家重点实验室陕西西安710071

针对通配符基于身份加密方案中安全归约不紧密以及运算量大的缺陷,利用双线性对和分级基于身份加密的思想提出标准模型下可证安全的通配符基于身份加密方案.新方案取得紧密的安全归约,同时加密算法不需要对运算,解密算法仅仅需要2个对运... 详细信息

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

关键词：基于身份加密标准模型通配符双线性对

在线全文

学校读者我要写书评

暂无评论

基于索引树的带通配符序列模式挖掘算法

计算机学报 2019年第3期42卷 554-565页

作者：王乐王水刘胜蓝王辉兵宁波财经学院信息工程学院浙江宁波315175 大连理工大学创新创业学院辽宁大连116024

随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树... 详细信息

随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树的结构和模式匹配方法对挖掘效率有决定性的影响.该文首先设计一个新的树结构索引树I-Tree(Index-Tree)来维护原始序列数据以及序列模式和模式索引信息;然后在索引树的基础上,提出一个新的带通配符的序列模式挖掘算法ITM(Index-Tree based sequential pattern Mining).算法ITM主要用4个策略提高算法的挖掘效率:(1)将原始序列中相同项压缩到一个节点上,该节点只记录项在原始序列中的索引;(2)采用迭代的方式,长度k+1的序列模式是用长度k(k>0)的候选序列模式产生;(3)采用前缀树的结构,逐层将k+1的候选序列模式压缩到索引树上,叶子节点上记录序列模式最后一项的索引;(4)整个挖掘过程,只用一棵索引树.算法ITM通过采用以上索引树压缩原始序列数据以及存储候选序列模式,有效地缩小搜索空间,从而算法效率得到显著提升.另一种提高挖掘效率的思路,是在挖掘过程中允许有小部分的模式丢失,来换取挖掘效率的大幅度提升,即所谓的近似模式挖掘.该文也给出了一个近似序列模式挖掘算法AITM(Approximate Index-Tree based sequential pattern Mining),该近似算法通过估计超序列模式的支持数,将非候选节点提前删掉,减少索引树上的节点个数,从而提高算法的时空效率;但是也因为估计的支持数可能会小于实际值,从而丢失了部分频繁的序列模式.该文实验中,提出的两个算法分别与算法MGCS、MAPB和MAPD进行了对比实验,采用3个典型数据序列进行测试,并设计了3组实验:(1)不同的最小支持度对算法的效率影响;(2)算法的扩展性;(3)通配符长度对算法效率的影响.实验结果验证了该文提出算法的有效性,时空效率得到一定的提高;针对不同的阈值,最小支持度越小、原始序列长度越长、通配符长度越长,算法的时间效率提高幅度越大;同时近似挖掘算法的精确度接近100%.

关键词：数据挖掘序列模式通配符模式匹配索引树

在线全文

学校读者我要写书评

暂无评论

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

计算机科学 2014年第9期41卷 269-273,310页

作者：项泰宁郭丹王海平胡学钢合肥工业大学计算机与信息学院合肥230009

随着生物信息学、信息检索等领域的发展,带有通配符和长度约束的模式匹配问题引起了广泛关注。该问题扩展了精确模式匹配问题,使匹配更加灵活,同时也增加了匹配的复杂性,极大地提高了非线性匹配算法的复杂度。求解该问题的匹配算法的效... 详细信息

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

关键词：解空间分割模式匹配通配符

在线全文

学校读者我要写书评

暂无评论

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

计算机应用 2013年第3期33卷 800-805页

作者：黄国林郭丹胡学钢合肥工业大学计算机与信息学院合肥230009

针对近似模式匹配算法在处理带有灵活通配符和长度约束近似模式匹配(APMWL)问题时只能解决替换操作,提出一种基于动态规划的编辑距离矩阵(EDM)构造方法,设计了基于EDM的近似模式匹配算法APM,可以处理近似匹配中的三种编辑操作,即插入、... 详细信息

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

关键词：近似匹配通配符长度约束编辑距离矩阵 one—off条件

在线全文

学校读者我要写书评

暂无评论

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

南京大学学报（自然科学版） 2013年第2期49卷 226-234页

作者：马晓文胡学钢谢飞郭丹合肥工业大学计算机与信息学院合肥230009 合肥师范学院计算机科学与技术系合肥230601

带有通配符的多序列模式挖掘在文本检索、网络安全、生物科学等领域中具有很重要的作用.通过挖掘多序列模式,能够透彻的了解序列之间的联系,在各个领域中具有重要的现实意义.在已有的工作中,随着多序列集长度的增大,挖掘的规模呈现指数... 详细信息

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

关键词：多序列间隔约束通配符 one-off条件频繁模式

在线全文

学校读者我要写书评

暂无评论

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

计算机科学 2012年第12期39卷 177-180,194页

作者：侯宝剑谢飞胡学钢刘应玲王海平合肥工业大学计算机与信息学院合肥230009 合肥师范学院计算机科学与技术系合肥230601 中国科学技术大学物理学院合肥230026

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其中通配符可以在模式的任... 详细信息

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

关键词：模式匹配通配符后缀树

基于Trie结构的带通配符的相似字符串匹配算法

在线全文

学校读者我要写书评

暂无评论

计算机应用 2004年第10期24卷 121-124页

作者：王燚西南交通大学智能信息控制开发中心

提出了一种新的相似字符串查询的方法。其目的在于提高基于相似字符串匹配的查询在大规模字符串数据库中的查询效率,并且提供带通配符的字符串查询方式。该方法使用Trie数据结构组织数据库中的数据,使用基于编辑距离的相似字符串匹配方... 详细信息

提出了一种新的相似字符串查询的方法。其目的在于提高基于相似字符串匹配的查询在大规模字符串数据库中的查询效率,并且提供带通配符的字符串查询方式。该方法使用Trie数据结构组织数据库中的数据,使用基于编辑距离的相似字符串匹配方法,在Trie数据结构中进行高效的匹配和查询,得到K相似度下的候选词集。实验证明,本方法在K 2时具有相当高的查询效率。

关键词：相似字符串匹配 Tire OCR文本校对拼写校对通配符

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

在线全文

学校读者我要写书评

暂无评论

计算机科学 2016年第4期43卷 279-283,F0003页

作者：汪浩王海平吴信东合肥工业大学计算机与信息学院合肥230009

讨论了带有通配符和长度约束的模式匹配(PMWL)问题,其中模式由子模式序列集组成,两个相邻子模式的间隔在一定长度范围内。针对PMWL问题,已有工作包括设计启发式求解算法和对特殊情况进行完备性分析,然而还需要构建问题的基础求解模型。... 详细信息

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

关键词：长度约束通配符求解模型模式匹配