【摘 要】
：
带通配符约束的模式匹配是热点的研究问题.在一个给定的文本和带灵活通配符的模式中,计算模式在文本中的出现次数是个非常困难的问题.提出了一个时间复杂度和空间复杂度分别为O(n+m+a)和O(m+B)的算法TAIL (paTtern mAtching with wiLdcards),其中n和m分别表示文本和模式的长度,a是所有子模式在文本中出现的数目,B是模式中通配符间距下限的总和.解决此问题,先前最好
【机 构】
：
合肥工业大学计算机与信息学院 合肥230009 合肥工业大学计算机与信息学院 合肥230009;佛
【出 处】
：
第十二届中国Rough集与软计算学术会议、第六届中国Web智能学术研讨会及第六届中国粒计算学术研讨会联合学术会议
论文部分内容阅读
带通配符约束的模式匹配是热点的研究问题.在一个给定的文本和带灵活通配符的模式中,计算模式在文本中的出现次数是个非常困难的问题.提出了一个时间复杂度和空间复杂度分别为O(n+m+a)和O(m+B)的算法TAIL (paTtern mAtching with wiLdcards),其中n和m分别表示文本和模式的长度,a是所有子模式在文本中出现的数目,B是模式中通配符间距下限的总和.解决此问题,先前最好算法的时间复杂度和空间复杂度分别是O(nm2w2)和O(mw),其中w是模式中最大通配符间距.对真实和人工的数据进行了实验,结果进一步验证了TAIL算法比其他算法更加稳定和有效.
其他文献
在粗糙集不确定性度量公式中,模糊熵和模糊度是重要的度量方式.根据粗糙集不确定性度量中模糊熵和新的模糊度公式,提出了在决策信息系统中修正条件信息熵和相对模糊熵的概念,并分别用两种方式证明了熵在属性约简过程中的单调性.然后利用向前添加属性算法进行属性约简,约简结果在RIDAS平台上进行识别率测试,通过实验对比分析了提出的两种新的信息熵与条件信息熵的约简,从而为基于信息熵的属性约简提供了参考.
相对于硬聚类算法,软聚类算法可以更好地表示具有不精确边界的类簇.粗糙集和模糊集均是用于描述不精确数据的有效的数学工具,二者之间互为补充.研究人员已经将粗糙集和模糊集的概念相结合,并应用到聚类算法中.而阴影集的引入可以有效地解决粗糙模糊聚类算法中的阈值选择问题.
随着社会媒体的发展,用户网络将产生大量内容,发现其潜在的社区及主题便于了解网络结构及用户兴趣,进行更深层次的分析和预测.融合内容和链接的主题发现或社区发现概率模型成为完成该任务的主流方法,按模型目标将其分为主题发现模型、主题社区发现模型和社区-主题发现模型.分析各模型的设计背景、基本原理、参数求解及优缺点等,并通过典型模型的定性比较和定量实验分析探索该类模型存在的问题,最后预测来来融合模型的可能研
最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应用.然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题,算法的实际性能也不能满足许多应用问题的要求.针对求解一个给定的有向网络上最大流问题,本文提出一种新方法——收缩邻居节点集的方法(CNA).该方法旨在通过收缩邻居节点集来有效降低网络规模,使得经典算法及改进算法可以直接使用.首先给出收缩邻居节点集的
介绍了事件本体的体系结构和原理.事件本体以事件类的格结构作为主线,每个事件类包括6个要素,对象要素描述事件参与的角色和角色所属概念以及角色成员的数量,全部所属概念组成对象概念格；动作要素描述事件类中的事件进展平均程度、过程、工具、方式方法,程度由属性值描述,过程由成员事件组成的流程描述,全部工具、方式方法概念分别组成工具、方式方法概念格；时间要素描述事件类的时间区间,用区间数表示；环境要素描述事件
为了能为粒计算的粒提供一种统一的表示形式,研究了粒的特征的基本含义、描述及其关系,并说明了粒的4个要素都与粒的特征密切相关,提出了数据层面上基于特征的粒四元组的形式化表示形式,即由对象集、特征集、关系集和约束集四元组组成.接着给出了几个特殊粒的表示形式,然后分析了该表示形式的统一性及其优点,并结合具体的例子进行了研究.该形式化表示形式能够很好地解决数据层面基于特征的粒表示问题,有利于问题求解和粒计
由于多粒度粗糙集更广的应用范围和丰富的研究内容,多粒度粗糙集正逐渐成为粒计算和粗糙集领域的一个新的研究热点.为了构造具有更好泛化能力的粗糙分类器,有时需要在粗糙近似过程中保留带有语义的信息粒,带有内涵和外延的信息粒称为概念.试图建立一个带概念描述的多粒度粗糙集数据建模方法,这种表达方式称为概念多粒度粗糙集,其有助于构建具有更好泛化能力的多粒度粗糙分类器.概念多粒度粗糙集有3个核心概念:多粒度上/下
根据粒计算的观点,在不同尺度的层次结构下,数据集中有不同粗细的信息粒度.本文在不完备信息系统中介绍了信息传递函数,并通过多重标记构造了多层粒度；然后利用非对称相似关系给出了多标记粒度上、下近似的定义,并对它们的性质进行了讨论.
The workflow scheduling algorithms and strategies having been put forward by Wieczorek M,Rajakumar S,Simion B,Shi Zhiao,etc can be effectively applied to deal with instance-sparse workflows and single
提出一种基于粒计算思想和局部线性嵌入(LLE)相结合的图像分析处理方法.首先对图像进行分块,以每个块作为图像粒对图像进行预处理,针对人脸研究领域中高维数据问题进行了降维处理,从而达到降低计算复杂度的效果.应用LLE算法对Frey人脸数据率中的多个不同粒度的人脸图像分别进行实验,给出人脸姿态、表情分布和变化的实验结果,并分析了图像信息的损失情况.