基于自然语言处理的算法知识名称发现

网络中的很多程序资源在知识概念上有内在的联系,却没有超链接将它们连接在一起。将网络程序资源中的算法知识名称获取出来,组织成一个算法知识专家库文件,用于识别程序设计资源所含的知识点,即可将程序设计资源按知识点相互联系。为了自动获取程序资源中的算法知识名称,提出一种基于自然语言处理的算法知识名称发现方法。通过发现含有算法知识名称语句的字符串模式,从程序资源中提取可能含算法知识名称的字符串,从中找出最有可能出现在算法知识名称中的分词,并根据这些分词获取算法知识名称。实验结果表明,与原有人工整理出的算法知识名称集合相比,该方法新增了11.2%的算法知识点和13.6%的算法知识名称。     

一种高效的多模式字符串匹配算法

在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。     

大图数据上顶点驱动的并行最小生成树算法

最小生成树(minimum spanning tree,MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高.然而,随着互联网的迅猛发展,图数据规模也变得越来越大,包含千万甚至上亿个顶点的大图数据越发常见.因此,如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外,由于大图数据的动态性特征,如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim,PP)算法,基于此提出了顶点驱动的并行MST算法——PB(PP Boru。vka)算法,并论证了PB算法的正确性.另外,基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征,提出了MST维护算法,以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后,使用真实和模拟数据集,验证了PB算法和维护算法的有效性、高效性和可扩展性.     

度量空间中的Top-k反向Skyline查询算法

不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-kreverse skyline).MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS(sort and threshold skyline),它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS(reuse STS),进一步减少了STS中80%以上的I?O访问.大量的实验表明提出的算法有效、快速.     

基于颜色矩的图像检索算法研究

为克服基于文字的图像检索技术对大型图像数据库实施困难、描述不完整等弊端,对RGB颜色矩和Munsell颜色矩进行研究,RGB颜色矩只适用于简单图像,Munsell颜色矩无法判断图片具体信息。为此,采用信息融合技术进行检索判断层的融合,选择多颜色空间融合颜色矩,在分析传统融合算法基础上,提出一种改进融合算法NewcombMNZ。实验结果表明,该算法能提高检索精准度和排序值,对噪声具有良好的鲁棒性,且能减少检索性能较差的特征对融合结果的影响,适用于特征数量较少的情况。     

无线传感器网络中的改进数据聚集调度算法

针对现有聚集数据调度近似算法具有较高延时上界的问题,提出一种改进的聚集数据调度近似算法。建立一棵根在中心结点的广度优先搜索树,分层构造一个最大独立集(MIS),使MIS中相邻的2个结点相距两跳。将MIS中的结点连接起来,形成一棵根在中心结点的数据聚集调度树,使结点按数据聚集调度树进行分层数据调度。在数据聚集调度树的构造过程中,对于任意支配点,以最小的结点连接其相距两跳的支配点。对于2个相邻支配点的公共邻居支配点,通过在距中心点最近的支配点加入数据聚集树,使其在数据调度过程中将数据发送给距中心点最近的支配点,从而降低数据的聚集延时。实验结果表明,与SAS算法、Guo’s算法和IAS算法相比,该算法的数据聚集延时更低,其延时上界为14R+△?10。     

基于重加权快速交替方向法的频谱感知

在认知无线电网络中,由于深衰落和低信噪比的影响,单个认知用户的宽带频谱检测性能较差,且算法复杂度较高。针对该问题,提出一种基于重加权快速交替方向法的频谱感知算法。利用目标函数的凸性,通过求导简化辅助变量的更新过程。对目标函数进行线性化处理,增加一个二次项,使待估变量更新时部分项线性化的增广拉格朗日函数成为严格凸函数,并使用迭代软阈值算法进行求解。在目标项中增加大权值抑制信号中的非零元素,获得接近于最小?0范数的解。实验结果表明,该算法能有效提高低信噪比环境下的检测概率和检测速度。     

一种基于轻权加密体制的RFID认证协议

针对射频识别(RFID)系统在计算与存储资源有限情况下的特殊需求,提出一种基于公钥密码体制NTRU的轻权认证协议。在该协议中,标签和读写器均完成一次随机数生成操作,且仅在服务器端存储一个密钥对,各个RFID标签采用公钥进行消息加密并发送给读写器和服务器,服务器通过存储在本地的私钥进行解密,在标签端仅存储服务器的公钥,以确保认证过程中信息的保密传输和隐私性,实现标签与读写器间的相互认证。通过分析证实,该协议能够抵抗窃听、位置追踪、重放、反向跟踪等攻击,而且标签仅需提供轻权加密和随机数生成操作,该认证协议非常适合应用于低成本的RFID系统。     

一种局部强化的多标签传播社区发现算法

在社交网络中,社区和圈子均表现为一组内部连接相对紧密的节点,但后者规模较小。圈子是重要的局部社区信息,利用这一特点有助于进行社区发现。然而,现有的大部分基于标签传播的社区发现算法并没有考虑圈子的信息。为此,提出一种基于局部强化的多标签传播(LSMLP)社区发现算法。给出圈子的定义,提出一种基于圈子信息的迭代多标签传播策略,并从每个节点的多个标签中选择归属系数最大的标签作为其从属的临时社区。采用两步优化方法使模度最大化。在真实网络的数据实验结果表明,与已有的社区发现算法相比,LSMLP算法能更高效地发现社区。     

基于RDC-Q学习算法的移动机器人路径规划

传统Q算法对于机器人回报函数的定义较为宽泛,导致机器人的学习效率不高。为解决该问题,给出一种回报详细分类Q(RDC-Q)学习算法。综合机器人各个传感器的返回值,依据机器人距离障碍物的远近把机器人的状态划分为20个奖励状态和15个惩罚状态,对机器人每个时刻所获得的回报值按其状态的安全等级分类,使机器人趋向于安全等级更高的状态,从而帮助机器人更快更好地学习。通过在一个障碍物密集的环境中进行仿真实验,证明该算法收敛速度相对传统回报Q算法有明显提高。