计算机科学

概率图模型表示理论

刘建伟,黎海恩,罗雄麟

计算机科学. 2014, 41 (9): 1-17. doi:10.11896/j.issn.1002-137X.2014.09.001

摘要 ( 311 )

PDF(1394KB) ( 748 )

参考文献 | 相关文章 | 多维度评价

概率图模型结合概率论与图论的知识,利用图来表示与模型有关的变量的联合概率分布。近年它已成为不确定性推理的研究热点,在人工智能、机器学习和计算机视觉等领域有广阔的应用前景。主要研究概率图模型的表示方法,讨论如何利用概率网络中的独立性来简化联合概率分布的方法表示。首先介绍了单个节点上的条件概率分布的表示模型及其引起的独立性,包括表格CPD、确定性CPD、特定上下文CPD、因果影响CPD、高斯模型和混合模型,并把单个分布模型推广到指数分布族中。然后详细介绍贝叶斯网络中的独立性以及图与概率分布的关系,讨论了高斯分布和指数分布族的贝叶斯网络表示理论。再详细描述马尔可夫网络的参数化问题及其独立性,也讨论高斯分布和指数分布族的马尔可夫网络表示理论。还给出两种局部有向图模型:条件随机场和链图。并且描述基于模板的概率模型表示,包括动态贝叶斯网络和状态观测模型这两种暂态模型,以及盘模型和概率关系模型这两种对象关系领域的有向概率模型,而且给出对象关系领域的无向表示。最后对概率图模型表示理论和方法所面临的问题及前景进行展望。

基于矩阵初等变换的量子可逆逻辑电路双向综合算法

王冬,刘强,李善治

计算机科学. 2014, 41 (9): 18-23. doi:10.11896/j.issn.1002-137X.2014.09.002

摘要 ( 202 )

PDF(433KB) ( 627 )

参考文献 | 相关文章 | 多维度评价

基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低；又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。

装备保障仿真概念模型的语义验证方法研究

顾闯,刘彬,张星,田书超,王桂起

计算机科学. 2014, 41 (9): 24-27. doi:10.11896/j.issn.1002-137X.2014.09.003

摘要 ( 326 )

PDF(1246KB) ( 507 )

参考文献 | 相关文章 | 多维度评价

概念模型验证是保证概念模型正确、可信的重要手段。针对现有概念模型形式化验证方法复杂、繁琐,非形式化验证方法的主观性较强、可信性不高等问题,采用本体理论和语义网技术,提出了一种基于本体与规则推理的装备保障仿真概念模型语义验证方法。该方法的思路是:首先将UML描述的概念模型转化为本体描述语言OWL描述的概念模型；然后根据领域知识构建验证规则,并运用语义网规则描述语言SWRL描述验证规则；最后将模型和规则转换为Jess规则引擎识别的数据格式,输入到Jess规则引擎中进行模型与规则的语义推理,检查概念模型是否符合验证规则。实例表明,该方法使用验证规则和语义推理机替代领域专家在计算机上自动对概念模型的语义内容进行验证,提高了验证效率,减少了专家验证的主观性和不确定性,降低了形式化验证方法的复杂性。

一种面向SIMD扩展部件的向量化统一架构

刘鹏,赵荣彩,赵博,高伟

计算机科学. 2014, 41 (9): 28-31. doi:10.11896/j.issn.1002-137X.2014.09.004

摘要 ( 210 )

PDF(1054KB) ( 856 )

参考文献 | 相关文章 | 多维度评价

随着多媒体应用的普及和高性能计算的需求,越来越多的处理器集成了SIMD扩展。为了针对不同SIMD扩展部件自动生成高效的向量化代码,设计了一套虚拟向量指令集,在此基础上构建了一种面向SIMD扩展部件的向量化统一架构。将输入程序通过向量识别等阶段转变为虚拟向量指令的中间表示,而后通过向量长度解虚拟化和指令集解虚拟化,将其转变为特定SIMD部件的向量指令集。在申威1600、DSP和Alpha上的实验结果表明:统一架构能够针对3种平台自动变换出高效的向量化代码,在DSP上的加速比要明显优于其它两种平台。

整机系统实时功率剖析与建模

杨良怀,朱红燕

计算机科学. 2014, 41 (9): 32-37. doi:10.11896/j.issn.1002-137X.2014.09.005

摘要 ( 225 )

PDF(506KB) ( 671 )

参考文献 | 相关文章 | 多维度评价

功率剖析与建模是功率感知DBMS的基础。将主要硬件(处理器与磁盘)的利用率作为系统功率的指示器,根据资源利用率实时地估计系统功率,构建整机系统的实时功率模型。在多核架构下,整体CPU的活动信息会掩盖单个核的使用情况,因此,从执行核粒度考察执行频率与利用率的综合影响,采用多元线性回归方法拟合执行核的执行频率和利用率、磁盘的利用率和系统功率之间的关系。实验结果显示,所构模型平均相对误差小于12%,且占用系统资源较少,从而不会影响其他应用程序的执行,具有较好的应用价值。

POP-PHP:支持PHP应用的在线集成开发环境

杨楠,吴凌,王千祥

计算机科学. 2014, 41 (9): 38-44. doi:10.11896/j.issn.1002-137X.2014.09.006

摘要 ( 282 )

PDF(3617KB) ( 612 )

参考文献 | 相关文章 | 多维度评价

随着云计算的发展,随时随地开发程序成为许多人的一种新的愿景。因此在线集成开发环境受到了软件开发人员的广泛关注。POP-PHP(Peking University Online Programming-PHP version)是一个支持PHP应用的在线集成开发环境,具有基本的集成开发环境功能,支持多用户同时使用,并提供了一种轻量级调试方法。其采用服务组合实现了较为完善的语法检查功能,并实现了编程行为回放以进行监测。

Lerisk－i*框架自动建模与编辑工具介绍

李天颍,刘璘,寇晓溪,赵德旺

计算机科学. 2014, 41 (9): 45-51. doi:10.11896/j.issn.1002-137X.2014.09.007

摘要 ( 220 )

PDF(2769KB) ( 471 )

参考文献 | 相关文章 | 多维度评价

在需求工程中,基于主体的i*建模框架(主要包括策略依赖模型及策略推理模型)已经成为最常用的早期需求建模与分析的工具之一,而且关于i*建模框架的编辑工具开发也有很多相关的研究工作。然而现有的这些工具往往只提供诸如模型图编辑、存储等基本功能,而笔者需要在需求工程小组的项目中为对需求文本进行建模的结果进行模型可视化,同时提供编辑存储及自动布局功能,并开发出新的基于i*建模框架的工具。文中首先对主流的i*建模工具进行了调研,研究了建模工具的基本功能,同时分析了其功能的不足点,在此基础上提出了新工具设计的功能补充点；然后对i*框架的布局问题进行介绍并详细描述了其自动布局算法的实现,给出了可视化工具的详细设计；最后在此工具的基础上,进行了实际需求文本的建模及模型编辑功能的实验,并将此工具与主流工具的功能进行对比,以展示本工具的功能特点。

一种基于主题建模的代码功能挖掘工具

华哲邦,李萌,赵俊峰,邹艳珍,谢冰,李扬

计算机科学. 2014, 41 (9): 52-59. doi:10.11896/j.issn.1002-137X.2014.09.008

摘要 ( 351 )

PDF(1166KB) ( 613 )

参考文献 | 相关文章 | 多维度评价

代码复用是重要的软件复用方式之一,复用者需要理解软件代码实现的功能方能有效实施软件复用。基于主题建模技术的程序理解方法逐渐受到研究人员的重视,它能够帮助软件开发者和使用者更好地理解软件的功能。目前,基于主题建模技术的程序理解方法一般欠缺对挖掘出的Topic的语义分析,为此提出的基于代码静态分析和LDA技术的代码功能挖掘(Code Function Mining,CFM)方法可作为对这类方法的补充。CFM是一套以代码为研究对象的挖掘、筛选、组织和描述主题(Topic)的方法,该方法能够生成带描述的功能型Topic的层次结构,以供使用者更清晰和方便地浏览、学习软件的功能。功能型Topic的描述能够帮助复用者理解代码功能,其层次结构能够让复用者从不同抽象层次理解代码功能。CFM方法包括4个部分:挖掘Topic、筛选Topic、组织Topic、描述Topic。以CFM方法为基础,设计并实现了一个CFM工具。CFM工具能够分析用户提交的代码,通过Web页面向用户展示带描述的功能型Topic的层次结构。最后,对CFM方法中的几个关键算法进行实验分析,验证了CFM方法的有效性。

ConUp:一个支持构件动态更新的SCA中间件系统

任国超,王姜,马晓星

计算机科学. 2014, 41 (9): 60-62. doi:10.11896/j.issn.1002-137X.2014.09.009

摘要 ( 210 )

PDF(310KB) ( 414 )

参考文献 | 相关文章 | 多维度评价

中间件已经成为网络环境下构建复杂应用系统的核心基础支撑软件。Internet的发展促使应用环境从封闭、静态转变为开放、动态,这就要求中间件上的应用具有动态更新的能力。业界广泛应用的中间件多支持构件的热部署,但不能自动保证系统的一致性。ConUp是一个基于Tuscany的SCA中间件系统,它通过对构件间动态依赖的管理来保证构件动态更新后系统的一致性。本原型演示将展示ConUp的中间件上的构件进行动态更新的过程,它对多种动态更新算法、策略的支持,及其在动态更新安全性、及时性和低干扰性方面的优势。

基于云计算的大规模性能测试服务平台

陈铁南,唐震,王晓冉,任凯,支孟轩

计算机科学. 2014, 41 (9): 63-66. doi:10.11896/j.issn.1002-137X.2014.09.010

摘要 ( 202 )

PDF(949KB) ( 457 )

参考文献 | 相关文章 | 多维度评价

性能测试是通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。测试对象分为基准测试和非基准测试两种。大规模的性能测试受到所需的大量软硬件资源以及与此规模匹配的管理维护代价的限制,传统的性能测试采用一种1:20的微缩仿真模拟,但这种微缩仿真测试不充分,会带来严重的后果。采用云计算技术,使用其承诺的按需的廉价软硬件资源服务,来构建大规模性能测试服务平台,提供按需定制的测试服务。

基于语义关系的服务计算支持工具

冯志勇,陈世展,王辉,梁其烜

计算机科学. 2014, 41 (9): 67-70. doi:10.11896/j.issn.1002-137X.2014.09.011

摘要 ( 189 )

PDF(363KB) ( 509 )

参考文献 | 相关文章 | 多维度评价

Web服务是实现软件即服务的最佳实践,也是解决集成组织间业务的关键技术。然而,互联网上的Web服务组织零散,不便于组织管理。服务网络(Service Network,SN)原型系统是一个Web服务组织管理平台,致力于Web服务整个生命周期的组织、管理和利用。其核心思想是利用语义Web(Semantic Web)和社会化网络技术,显式地识别、挖掘服务之间的语义关联和交互关系(简称为服务关系),将可用Web 服务组织成具有丰富语义信息、基于业务上下文和交互关系的服务生态系统。该系统主要包括以下几部分:服务搜集、服务标注、服务关系挖掘、服务组合。将语义推理和关系演算引入到服务的发现、组合、交互和管理过程中,使服务网络成为支撑面向服务计算模式的新型基础设施,这有助于改善和提高Web服务组合的自动化程度及效率,从而满足更加复杂的应用需求。

基于程序切片的测试用例生成系统研究与实现

王志文,黄小龙,王海军,刘烃,俞乐晨

计算机科学. 2014, 41 (9): 71-74. doi:10.11896/j.issn.1002-137X.2014.09.012

摘要 ( 308 )

PDF(319KB) ( 477 )

参考文献 | 相关文章 | 多维度评价

介绍了一种基于程序行为切片的测试用例生成系统的实现方案,系统在不扫描全部程序路径的情况下,生成可以覆盖全部程序行为的测试用例集。系统分为静态分析、动态符号执行以及测试用例生成3个模块。在静态分析模块中根据输入的程序代码分析程序的控制流和信息流,提取程序的控制依赖和数据依赖,并计算程序的潜在依赖；动态符号执行模块求解约束条件、生成测试用例和分析代码执行过程；测试用例生成模块根据执行路径和依赖关系计算被路径覆盖的程序行为切片和未被覆盖的程序行为切片,然后根据未被覆盖的程序行为切片,引导符号执行生成能覆盖新的程序行为切片的测试用例。实验证明,本系统生成的测试用例集可以保证覆盖所有的程序行为,同时能显著减少生成的测试用例数量。

基于组件的大数据分析服务平台

赵薇,刘杰,叶丹

计算机科学. 2014, 41 (9): 75-79. doi:10.11896/j.issn.1002-137X.2014.09.013

摘要 ( 217 )

PDF(951KB) ( 487 )

参考文献 | 相关文章 | 多维度评价

随着数据规模的快速增长,单机的数据分析工具已经无法满足需求。针对大数据的分析问题,设计并实现了一种基于组件的大数据分析服务平台Haflow。Haflow自定义了业务流程模型和可扩展的组件接口,组件接口支持各种异构工具的集成。系统接收用户定义的业务流程,将其翻译成执行流程实例,提交到Hadoop分布式集群上执行。Haflow是一个可扩展的、分布式的、支持异构分析工具的、面向服务的大数据分析服务平台。提出该平台有两重意义:一方面平台将与数据分析业务无关的工作封装起来,支持各种异构组件,以加快分析应用的开发速度；另一方面,平台后端使用Hadoop分布式系统来实现多任务的并发,从而提高应用的平均执行速度。

基于Web的多刻面交互式特征定位工具MFIE

彭鑫,王金水,付焜,赵文耘

计算机科学. 2014, 41 (9): 80-83. doi:10.11896/j.issn.1002-137X.2014.09.014

摘要 ( 195 )

PDF(2631KB) ( 564 )

参考文献 | 相关文章 | 多维度评价

在执行软件维护任务中,开发人员经常需要在软件代码中寻找并理解与给定的功能性特征相关的程序元素(如类或方法),这一过程称为特征定位或概念定位。相关的经验研究表明,特征定位是一个以人为中心、信息密集型的探索和认知过程,包含交互式的信息探索、反馈和策略调整。基于这一思想,提出了一种多刻面、交互式的特征定位方法,并开发了基于Web的支持工具MFIE(Multi-faceted Interactive Explorer)。介绍了MFIE所实现的多刻面、交互式特征定位方法,MFIE的多刻面界面设计以及所提供的主要功能。在此基础上,还通过一个案例介绍了MFIE所支持的特征定位过程。

PSC2GS:一个基于属性序列图的监控器生成工具

余俊,张鹏程,周宇鹏,刘宗磊

计算机科学. 2014, 41 (9): 84-87. doi:10.11896/j.issn.1002-137X.2014.09.015

摘要 ( 180 )

PDF(1279KB) ( 429 )

参考文献 | 相关文章 | 多维度评价

在开放和动态环境下,系统或环境的不安全的运行时变化可能为整个系统的正确执行埋下隐患,可能最终导致软件失效。基于监控器的软件运行时验证技术已经成为开放环境下侦测软件失效行为的基本方法,该工具采用了一种基于博弈论的从Property Sequence Charts(属性序列图)中自动生成监控器的方法。监控器被赋予多值语义:满足、无限可控、系统有限可控、系统紧急可控、环境有限可控、环境紧急可控以及违例。监控器可以提供足够的信息用来预测系统失效。正文中将描述一个名为“PSC2GS”的工具,该工具具有设计属性序列图、基于属性序列图生成博弈结构、基于博弈结构生成Aspect Oriented Programming(面向方面编程)代码(监控器)等一系列功能。PSC2GS提供的完全图形化的前端接口使软件设计者可以不用处理任何特殊的文本或者逻辑公式。

基于软件自动修复评估缺陷定位技术的工具:GenProg-FL

纪涛,齐玉华,毛晓光

计算机科学. 2014, 41 (9): 88-90. doi:10.11896/j.issn.1002-137X.2014.09.016

摘要 ( 299 )

PDF(348KB) ( 866 )

参考文献 | 相关文章 | 多维度评价

虽然缺陷定位技术和软件错误自动修复技术已经得到一定的发展,但是软件的修复工作仍然需要程序员投入大量的时间和精力。大多数开发者仍然使用传统调试技术(例如断点)来进行手工的调试,缺陷定位技术的研究成果并没有较好地运用到实际的修复工作中。近来,软件错误自动修复技术得到了快速的发展和广泛的关注。在软件错误自动修复工作中,利用缺陷定位技术自动定位错误代码是必需的,而定位的精度直接影响到补丁的生成,从而对修复的效果产生较大的影响。GenProg-FL工具可以接受不同的缺陷定位技术去自动修复故障程序。同样,使用GenProg-FL可以从软件自动修复的角度评估现有的基于程序谱的缺陷定位技术定位的有效性。

基于自然语言的软件信息检索工具

叶挺,陈秀招,邹艳珍,赵俊峰,谢冰

计算机科学. 2014, 41 (9): 91-95. doi:10.11896/j.issn.1002-137X.2014.09.017

摘要 ( 179 )

PDF(434KB) ( 453 )

参考文献 | 相关文章 | 多维度评价

随着开源软件项目规模的增大,如何快速地学习、理解一个软件项目成为基于复用的软件开发活动中的一个重要环节。这些开源软件项目的源代码和文档集的数量都比较庞大,开发人员在学习过程中查找和阅读这些软件信息需要花费大量的时间和精力。为此,提出一种基于自然语言的软件信息检索方法,以帮助开发人员快速地检索并理解其需要的软件信息。基于该方法,设计并实现了NaLSiSe工具。NaLSiSe工具在中国计算机学会主办的第一届软件研究成果原型竞赛中荣获优秀奖。以Lucene为例,验证了该工具可以有效减少开发人员阅读源代码和文档的工作量,同时具备简洁的用户界面和友好的用户体验。

一个用户主导的情景数据集成应用构造环境

王桂玲,曹波,张赛,耿美珍,张峰

计算机科学. 2014, 41 (9): 96-100. doi:10.11896/j.issn.1002-137X.2014.09.018

摘要 ( 179 )

PDF(1259KB) ( 424 )

参考文献 | 相关文章 | 多维度评价

随着网络的普及和深入应用,人们希望共享和集成丰富的网络信息资源,以满足其个性化需求。文中提出了一个用户主导的情景数据集成应用构造环境DSS,用以支持大量不具备专业编程知识的最终用户自行利用既有的网络信息资源即时构造应用。DSS支持当前常见的网络信息资源,实现了交互式的网页资源个性化服务封装,并将Spreadsheet和嵌套关系模型相结合,提供了可视化的嵌套电子表格操作和公式语言,以支持用户进行数据服务的组合。通过案例和相关工作的分析比较,表明了DSS上述功能的有效性。

一种高速嵌套CRC码的生成方法及其FPGA实现

段斌斌,孙嵩松,焦黎,周文利

计算机科学. 2014, 41 (9): 101-103. doi:10.11896/j.issn.1002-137X.2014.09.019

摘要 ( 304 )

PDF(1238KB) ( 670 )

参考文献 | 相关文章 | 多维度评价

为了实现高速融合网络数据传输中的差错控制,针对现有循环冗余校验码(CRC)计算速度难以进一步提升的问题,提出了一种用嵌套CRC码实现高速数据差错控制的方法,并在Xilinx公司的FPGA芯片上进行了实现。该嵌套CRC码由多个通道的传统CRC码并行计算器同步计算得到,可大幅度提升差错控制码的生成速度,并通过不同计算通道的组合,支持多种流量的差错控制。最后分析了嵌套CRC码的计算性能以及差错控制能力,并提供了设定嵌套次数、通道数以及计算通道并行计算位数的依据。

面向云环境的集群资源模糊聚类划分算法的优化

董世龙,陈宁江,谭瑛,何子龙,朱莉蓉

计算机科学. 2014, 41 (9): 104-109. doi:10.11896/j.issn.1002-137X.2014.09.020

摘要 ( 367 )

PDF(535KB) ( 441 )

参考文献 | 相关文章 | 多维度评价

传统的串行模糊聚类分析算法在应对高维矩阵运算时存在运算量大、运算效率低等问题,难以满足云环境中集群资源调度的时效性要求。为此,在基于等价关系的模糊聚类算法基础上对传递闭包法进行优化,提出一种基于多线程的云资源模糊聚类划分并发算法,并将其应用于Hadoop调度器的策略改进。仿真实验结果表明,优化策略有助于减少平方法求解模糊等价矩阵的计算量,所设计的并发算法能够有效解决中小规模云集群资源聚类的运算瓶颈问题,且具有较好的加速比。为了解决现有Hadoop调度器存在的异构性问题,对该优化并发算法进行了理论分析,结果表明它有助于解决异构性带来的调度难题。

三元组扩频码在扩频通信中的应用

王慧,吴成茂

计算机科学. 2014, 41 (9): 110-114. doi:10.11896/j.issn.1002-137X.2014.09.021

摘要 ( 215 )

PDF(485KB) ( 530 )

参考文献 | 相关文章 | 多维度评价

为了产生、加工出一组逼近白噪声统计信号特性的信号并将其作为扩频码来降低扩频通信系统的误码率、提高可靠性,基于三元组随机数提出三元组扩频码。该扩频码由真随机熵源提供初始值,以多轮重构技术构造背景,通过周期性变轨、控制空间映射和约束判断等方法实现离散轨迹变换,再经均匀映射产生。在不同大小的信噪比和不同幅度的正弦干扰下,采用蒙特卡罗模型仿真测试了三元组、m序列、分段Logistic序列和线性同余序列作为扩频码的直接扩频通信系统的误码率。实验结果表明,三元组扩频码的误码率更低,并且在低信噪比、强衰落、强干扰的情况下也很稳定,可以提高扩频通信系统的抗截获性和抗干扰性,从而保障通信系统的可靠性。

LBSN中位置信息与网络拓扑相融合的好友预测

潘果,徐雨明

计算机科学. 2014, 41 (9): 115-118. doi:10.11896/j.issn.1002-137X.2014.09.022

摘要 ( 224 )

PDF(324KB) ( 411 )

参考文献 | 相关文章 | 多维度评价

在基于位置的社会网络中,好友预测通常通过相似性标准来衡量用户间的相似性,然后将最相似的用户作为好友推荐给指定用户。传统的用户特征选取没有区分各个特征之间的差异,因而不能很好地代表用户的整体特征。提出了一种位置信息与社会网络拓扑相融合的好友预测方法。首先通过信息增益方法选取出更能代表用户整体特征的3个相关特征,然后对选取的特征进行融合,最后采用分类方法进行好友的预测。实验表明,提出的模型不依赖于具体的分类算法,并且预测性能优于多层好友模型。

基于上下文感知和移动位置预测的切换机制

王玉祥,王进,谢胜东

计算机科学. 2014, 41 (9): 119-124. doi:10.11896/j.issn.1002-137X.2014.09.023

摘要 ( 160 )

PDF(1122KB) ( 439 )

参考文献 | 相关文章 | 多维度评价

切换机制是无线通信系统中为用户提供无缝移动应用服务的一项关键技术,切换成功与否直接影响着用户业务体验和使用。提出了基于上下文感知和移动位置预测的切换机制,即采用多种类型上下文信息并利用修正证据理论预测移动用户的准确位置。提出的方法能够避免“乒乓切换”,缩短切换延迟,提前预留资源,为快速、准确和可靠的切换判决提供依据,显著地改善了网络服务质量。理论分析和仿真结果表明,该方法位置预测更接近用户真实的运动轨迹,位置预测的均方根误差较小,大大提高了切换成功率。

基于信息扩散的多尺度重叠社团快速探测算法

李慧嘉

计算机科学. 2014, 41 (9): 125-131. doi:10.11896/j.issn.1002-137X.2014.09.024

摘要 ( 168 )

PDF(3119KB) ( 488 )

参考文献 | 相关文章 | 多维度评价

现有的社团分析方法由于需要网络的全局信息,并且只能在单一的尺度上划分社团,因此不利于分析大规模的科技社会网络。提出了一种新颖的多尺度社团结构快速探测算法,其只利用网络的局域信息就可以模拟复杂网络中的多尺度的社团结构。该方法通过优化表示网络统计显著性的拓扑熵,来寻找有最佳统计意义的社团结构。为了得到具体的社团归属,算法只需利用局部信息的扩散来更新归属向量便能够收敛到局部极小值,因此具有较低的计算复杂性。它不需要指定具体的社团数量,便能够找到每个节点与具体社团的归属关系,从而能够自然地支持模糊社团的划分。理论分析和实验验证共同表明,该算法可以快速而准确地发现社会网络和生物网络中的各种功能社团。

基于精英的量子粒子群优化的Ad hoc能耗研究

张峰,贾智平,蔡晓军,张兰华

计算机科学. 2014, 41 (9): 132-136. doi:10.11896/j.issn.1002-137X.2014.09.025

摘要 ( 192 )

PDF(483KB) ( 405 )

参考文献 | 相关文章 | 多维度评价

在Ad hoc网络中,随着多播应用领域的日益扩大,如何构造最小能耗多播树是一个重要问题。针对选择不同的中继节点对构造最小能耗多播树产生的影响,提出了一种优化最小能耗多播树构造的基于精英学习的量子粒子群算法(QPELSO)。为了避免粒子群算法早熟收敛,采用动态逼近学习策略对精英个体进行局部更新,使其跳出局部极值点,引导种群进行有效搜索；借鉴群体早熟判断机制对停滞状态下的精英个体空间进行变尺度混沌扰动,增大种群全局搜索空间,有效平衡了算法的局部和全局搜索能力。模拟实验结果表明,改进后的粒子群算法具有较强的优化能力,并且有效地优化了最小能耗多播树的构造。

基于P2P网络的语义发布/订阅系统路由算法研究

张强,李建华,沈迪

计算机科学. 2014, 41 (9): 137-140. doi:10.11896/j.issn.1002-137X.2014.09.026

摘要 ( 175 )

PDF(445KB) ( 646 )

参考文献 | 相关文章 | 多维度评价

在结构化P2P网络基础上构建语义发布/订阅系统是近年来的研究热点。提出一种基于Chord的语义事件路由算法,算法采用基于集结点的路由策略,首先使用保留语义的哈希函数将订阅映射至事件代理集结点；其次根据订阅与事件之间的语义信息,仅发布事件至可能匹配的订阅集结点,采用Chord路由协议构建的订阅生成树分发通知消息；最后过载的集结点通过订阅迁移实现系统负载均衡。仿真实验表明,算法在一定程度上减少了资源消耗,提高了路由效率,达到了负载均衡。

环境感知的移动P2P社交网络组播路由算法

曹怀虎,张艳梅,朱建明,郭树行

计算机科学. 2014, 41 (9): 141-145. doi:10.11896/j.issn.1002-137X.2014.09.027

摘要 ( 186 )

PDF(1020KB) ( 450 )

参考文献 | 相关文章 | 多维度评价

移动社交网络节点间的组播通信是近年来研究者关注的热点问题之一。由于节点的动态变化及社会性,使得传统组播路由算法不能直接应用于移动社交网络。根据移动社交网络的环境特征,建立了移动社交网络的组播模型；利用环境感知信息,并结合最小生成树、格网组播路由算法,提出了环境感知的移动P2P社交网络组播路由算法。最后对该算法进行了理论分析及仿真实验测试,结果表明所提出的组播路由算法改善了数据传输的性能,具有较高的扩展性、鲁棒性。

云环境下基于属性的用户权限管理研究

李拴保,范乃英,傅建明,祁慧敏,刘芊

计算机科学. 2014, 41 (9): 146-151. doi:10.11896/j.issn.1002-137X.2014.09.028

摘要 ( 155 )

PDF(570KB) ( 551 )

参考文献 | 相关文章 | 多维度评价

用户权限分配是云计算服务的重要难题之一,提出了一种基于属性的用户权限管理方案。该方案以云服务中的新用户密钥分配为研究对象,论述了多方协同的用户签名验证解密管理机制,数据所有者和授权者共同选择属性集,数据所有者基于属性集定义密文访问结构,从而用户只有通过授权者认证才能获得解密密钥,达到用户权限升级与降级同步管理的目的。另外,本方案以群属性集更新为中心设计CP-ABE群签名验证机制,令数据所有者、用户和授权者组成群；基于群和自身属性用户可对消息签名以及公开验证,用以保护密文数据的细粒度访问控制。最后,给出签名有效性和不可伪造的证明结果。

基于CP-ABE和SD的高效云计算访问控制方案

陈燕俐,宋玲玲,杨庚

计算机科学. 2014, 41 (9): 152-157. doi:10.11896/j.issn.1002-137X.2014.09.029

摘要 ( 176 )

PDF(625KB) ( 688 )

参考文献 | 相关文章 | 多维度评价

存储在云端服务器中的敏感数据的保密和安全访问是云计算安全研究的重要内容。提出了一种安全、高效、细粒度的云计算访问控制方案。密文的加密采用了借助线性秘密共享矩阵的CP-ABE加密算法,并将大部分密文重加密工作转移给云服务提供商执行,在保证安全性的前提下,降低了数据属主的计算代价。该方案在用户属性撤销时,引入SD广播加密技术,有效降低了撤销时的计算开销和通信开销。理论分析表明该方案具有数据机密性、抗合谋攻击性、前向安全和后向安全,最后的实验结果验证了方案具有较高的撤销效率。

一种基于混沌的代换-置换结构图像加密算法

蔡俊,陈昕,向旭东

计算机科学. 2014, 41 (9): 158-164. doi:10.11896/j.issn.1002-137X.2014.09.030

摘要 ( 202 )

PDF(669KB) ( 481 )

参考文献 | 相关文章 | 多维度评价

近年来,随着多媒体技术的发展,互联网上数字图像相关内容和应用的比例越来越高,其安全性也日益受到人们的关注。图像的安全性,一般通过加密方法来保证。图像加密算法中,基于置乱-扩散结构的加密算法因其充分考虑图像数据二维分布的特点,特别适合图像数据的加密。然而,该加密算法存在安全性不高、扩散效率低,以及密钥扩展计算复杂度高等问题。通过引入分组密码学中的代换-置换(SP,Substitution-Permutation)结构,提出了一种基于混沌的SP结构图像加密算法SPCME,该算法采取3种策略:(1)通过混沌映射进行置换和扩散,采用AES算法的S盒进行字节代换,以增强算法安全性；(2)使用双向的置乱-扩散策略,加快扩散速度；(3)运用简单的异或和移位操作,提高密钥扩展效率。为评价该算法的性能,文中做了密钥空间分析、密钥敏感性分析、统计直方图分析、相邻像素相关性分析、信息熵分析、差分攻击分析等大量的性能分析实验。实验结果表明,该算法仅通过3轮迭代就可达到与以前提出的图像加密算法相同的安全级别,加密效率明显提高。

具有消息恢复功能的无陷门格签名方案

张襄松,刘振华

计算机科学. 2014, 41 (9): 165-168. doi:10.11896/j.issn.1002-137X.2014.09.031

摘要 ( 166 )

PDF(323KB) ( 464 )

参考文献 | 相关文章 | 多维度评价

利用Lyubashevsky拒绝抽样(无陷门)技术,提出了一个高效的具有消息恢复功能的格签名方案。新方案可以看作是具有消息恢复功能的 Abe-Okamato签名的格密码版本。在随机预言机模型下,利用General Forking Lemma,证明了新方案的选择消息攻击下存在的不可伪造安全性依赖于格上小整数解困难问题假设。新方案没有使用高斯原像抽样作为签名,仅需要简单的矩阵与向量乘法运算,具有短的消息-签名总长度。

基于节点博弈漏洞攻击图的网络风险分析方法

张健,王晋东,张恒巍,王娜

计算机科学. 2014, 41 (9): 169-173. doi:10.11896/j.issn.1002-137X.2014.09.032

摘要 ( 214 )

PDF(391KB) ( 569 )

参考文献 | 相关文章 | 多维度评价

鉴于当前的漏洞风险分析方法未考虑攻防双方的相互制约关系,尝试将博弈论引入漏洞攻击图的节点分析过程,提出了基于节点博弈漏洞攻击图的风险分析模型RAMVAG。在此基础上,提出一种基于连通矩阵的漏洞风险分析算法VRAA。算法建立了攻击图的连通矩阵,在分析信息系统漏洞的自身风险和传播风险的基础上,对漏洞全局风险进行综合评价,评价结果能够帮助管理者确定网络系统的关键漏洞。实例分析证明了模型和算法的有效性。

基于抗窃听和拜占庭攻击的随机网络编码

赵佳佳,任平安

计算机科学. 2014, 41 (9): 174-177. doi:10.11896/j.issn.1002-137X.2014.09.033

摘要 ( 418 )

PDF(301KB) ( 427 )

参考文献 | 相关文章 | 多维度评价

随机网络编码目前被广泛应用于实际网络环境中,能够有效提高网络吞吐量。然而网络编码容易受到窃听攻击和拜占庭攻击。提出一种既防窃听,又能有效检测出拜占庭攻击的安全随机网络编码算法。在信源和信宿之间共享秘密信道,该算法通过哈希函数增加少量计算量和少量冗余,实现防窃听攻击和防拜占庭攻击。该算法仅在随机网络编码的基础上改变了信源节点的编码方式和信宿节点的解码方式,中间节点编码方式保持不变,具有较高的编码效应。

改进的流不敏感的类型限定词推断

李慧松,许智武,陈海明

计算机科学. 2014, 41 (9): 178-184. doi:10.11896/j.issn.1002-137X.2014.09.034

摘要 ( 241 )

PDF(531KB) ( 403 )

参考文献 | 相关文章 | 多维度评价

类型限定词可以精化标准类型,提高类型系统的表达能力。流不敏感的类型限定词推断已被用于CQual架构,以提高C程序的质量。然而,类型转化会影响类型限定词推断的有效性。首先,展示了一种允许类型转化的程序语言和流不敏感的限定词推断系统；其次,提出了变量参与的限定词推断系统,引入了联合类型并给出约束求解算法；最后,证明了推断的正确性并展示了一些实例运行结果。

一种基于语义的业务活动推荐方法

张龙,应时,贾向阳,龚致远,李琳

计算机科学. 2014, 41 (9): 185-189. doi:10.11896/j.issn.1002-137X.2014.09.035

摘要 ( 162 )

PDF(506KB) ( 394 )

参考文献 | 相关文章 | 多维度评价

以企业复杂业务逻辑为背景,针对动态构造业务流程中的用户遗漏或错选工作等问题,提出了一种基于语义的业务活动推荐方法。首先定义面向业务活动的基础本体模型并在此基础上构建了基本推理规则,接着详细描述了方法所采用的推荐策略并在此基础上设计了推荐算法。方法的工作机制是接收并分析业务活动事件并调用推荐算法,推荐算法访问知识库,生成最终的推荐结果呈现给用户。最后通过国家综合减灾应用系统案例来验证方法的有效性。

基于位置范围的道路网skyline查询

施常月,秦小麟,许建秋,胡彩平

计算机科学. 2014, 41 (9): 190-195. doi:10.11896/j.issn.1002-137X.2014.09.036

摘要 ( 220 )

PDF(480KB) ( 536 )

参考文献 | 相关文章 | 多维度评价

随着无线通信和定位技术的发展,道路网skyline查询在基于位置的服务等方面越来越重要。考虑到现今道路网中位置隐私保护和定位设备的精度问题,用户在道路网上的位置通常用一个范围来表示。但是,已有的道路网skyline研究都是基于单一查询点。针对这一问题,研究了一种新的查询——基于位置范围的道路网skyline查询(RNS),提出了一种基于边界点替换的有效查询处理算法。另外,针对已有的道路网skyline查询中复杂的道路网距离计算对查询效率的影响问题,通过计算兴趣点在道路网上的有效skyline路段,将其与道路网信息融合,建立了道路网skyline模型。基于该模型设计了一种能有效支持RNS查询的道路网skyline索引SSR-tree,提出了基于索引的RNS查询处理算法。通过大量实验验证了所提方法的有效性,并比较了基于索引的算法在查询效率和精度上的提高。

回归测试中测试用例集缩减问题的研究

陈翔,顾庆,陈道蓄,蒋峥峥

计算机科学. 2014, 41 (9): 196-204. doi:10.11896/j.issn.1002-137X.2014.09.037

摘要 ( 228 )

PDF(855KB) ( 739 )

参考文献 | 相关文章 | 多维度评价

测试用例集缩减(Test Suite Minimization,TSM)问题作为回归测试的研究热点和难点,在满足对指定测试需求的覆盖前提下,通过识别并移除冗余测试用例来降低回归测试成本。对国内外已有的TSM研究成果进行综述。首先分别从源代码和模型两个角度出发,总结已有的TSM方法:从源代码角度出发,重点分析与总结传统TSM方法和考虑缺陷检测能力的TSM方法；从模型角度出发,重点分析与总结基于扩展有限状态自动机的TSM方法。然后对实证研究中采用的评测程序、评测指标和实证结论进行总结。随后总结了TSM方法在特定测试领域的应用,包括GUI应用测试、Web应用测试和缺陷定位等。最后展望了未来的可能发展趋势。

基于时间Petri网的嵌入式系统中断建模与验证

周宽久,常军旺,侯刚,任龙涛,王小龙

计算机科学. 2014, 41 (9): 205-209. doi:10.11896/j.issn.1002-137X.2014.09.038

摘要 ( 186 )

PDF(486KB) ( 599 )

参考文献 | 相关文章 | 多维度评价

嵌入式系统为中断驱动系统,但中断触发的随机性和不确定性导致中断缺陷很难被追踪发现,并且一旦发生中断故障,往往会使整个嵌入式系统陷入崩溃。因此必须保证中断系统软件的可信性,但是目前缺乏有效的中断系统资源冲突检测方法。针对上述问题,文中首先提出了一种基于时间Petri网的中断系统建模方法,其能够对中断的并发性和时间序列进行有效建模。然后,为方便后续形式化验证,将时间Petri网模型转化为与之等价的时间自动机模型,并提出一种符号编码方法对时间自动机进行形式化编码,将系统模型与所需验证性质编码为一阶谓词逻辑公式,从而能够通过SMT对时间自动机的不变属性进行BMC验证。最后,通过SMT求解器Z3进行实验,实验结果证明了所提方法的有效性。

基于动态时序描述逻辑的动作理论

孙永新,赵希顺

计算机科学. 2014, 41 (9): 210-214. doi:10.11896/j.issn.1002-137X.2014.09.039

摘要 ( 296 )

PDF(513KB) ( 411 )

参考文献 | 相关文章 | 多维度评价

动态时序描述逻辑(DLTLDL)是一类描述逻辑的动态时序扩展。提出一种基于DLTLALCIO的动态域建模方法,利用该方法可构造出刻画动态域知识的DLTLALCIO理论,并解决动作推理中的框架问题和分支问题。动作推理问题,如动作可执行性和投影问题等,可归结为关于DLTLALCIO理论的推理问题,并最终归结为DLTLALCIO的公式可满足性问题。DLTLALCIO公式可表达动作和时间约束,相对于其他基于描述逻辑的动作形式,基于DLTLALCIO的动作形式在需要执行复杂查询,尤其是含时间或动作的查询的应用场合具有更好的适用性。

一种基于动态规划的云环境测试配置方法

周欢欢,姜瑛

计算机科学. 2014, 41 (9): 215-219. doi:10.11896/j.issn.1002-137X.2014.09.040

摘要 ( 154 )

PDF(383KB) ( 433 )

参考文献 | 相关文章 | 多维度评价

为了得到测试代价最低的资源配置组合方案,简要介绍了测试配置对软件测试质量和效率的影响。通过分析当前云平台中松散耦合、动态变化可用资源的特点,提出了云环境下测试配置的过程、测试需求和测试配置的结构,并提出了基于动态规划的测试资源选择算法以满足用户的测试需求。最后在CloudSim下通过相关实验验证了方法的可行性。

Voronoi图的构建与受限区域内的最近邻查询方法研究

张丽平,赵纪桥,李松,经海东,崔环宇

计算机科学. 2014, 41 (9): 220-224. doi:10.11896/j.issn.1002-137X.2014.09.041

摘要 ( 176 )

PDF(503KB) ( 928 )

参考文献 | 相关文章 | 多维度评价

Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用。为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_Voronoi()算法。进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_NN()算法。理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势。

一种新的变异因子选择策略

王帅群,敖日格乐,高尚策,唐政,马海英

计算机科学. 2014, 41 (9): 225-228. doi:10.11896/j.issn.1002-137X.2014.09.042

摘要 ( 281 )

PDF(313KB) ( 493 )

参考文献 | 相关文章 | 多维度评价

在具有多层学习机制的免疫优化算法中,变异因子的选择概率对算法的有效性起着至关重要的作用。如果选择不够合理,将导致算法容易陷入局部最优,在一定程度上影响解的质量和收敛速度。针对多层学习机制的特点,讨论了各个因子之间的依赖性和相关性,提出了一种新的变异因子选择策略。选择4个基准函数作为测试函数进行了验证,结果表明,解的质量和收敛速度都有了明显的改善。

格值矩阵博弈研究

张霖,徐扬

计算机科学. 2014, 41 (9): 229-231. doi:10.11896/j.issn.1002-137X.2014.09.043

摘要 ( 172 )

PDF(303KB) ( 463 )

参考文献 | 相关文章 | 多维度评价

博弈论被广泛应用于描述和解决复杂的主体行为相互作用的决策问题。目前对于非实数值领域的博弈问题,成果很少,故研究支付值为格值类型的二人零和矩阵博弈。基于该类型博弈的特殊性,定义了纯战略纳什均衡解和准均衡解以及混合战略纳什均衡解和准均衡解,并研究解的性质,给出获得解的方法,得到各种解存在的充分必要条件。最后,给出了实例,验证了该方法处理支付值为格值类型的博弈问题的可行性和有效性。

一种批量最小二乘策略迭代方法

周鑫,刘全,傅启明,肖飞

计算机科学. 2014, 41 (9): 232-238. doi:10.11896/j.issn.1002-137X.2014.09.044

摘要 ( 424 )

PDF(558KB) ( 1094 )

参考文献 | 相关文章 | 多维度评价

策略迭代是一种迭代地评估和改进控制策略的强化学习方法。采用最小二乘的策略评估方法可以从经验数据中提取出更多有用信息,提高数据有效性。针对在线的最小二乘策略迭代方法对样本数据的利用不充分、每个样本仅使用一次就被丢弃的问题,提出一种批量最小二乘策略迭代算法(BLSPI),并从理论上证明其收敛性。BLSPI算法将批量更新方法与在线最小二乘策略迭代方法相结合,在线保存生成的样本数据,多次重复使用这些样本数据并结合最小二乘方法来更新控制策略。将BLSPI算法用于倒立摆实验平台,实验结果表明,该算法可以有效利用之前的经验知识,提高经验利用率,加快收敛速度。

面向大数据的在线特征提取研究

许烁娜,曾碧卿,熊芳敏

计算机科学. 2014, 41 (9): 239-242. doi:10.11896/j.issn.1002-137X.2014.09.045

摘要 ( 186 )

PDF(300KB) ( 460 )

参考文献 | 相关文章 | 多维度评价

在大数据环境下,当利用机器学习算法对训练样本进行分类时,训练数据的高维度严重制约了分类算法的性能。文中应用L1准则的稀疏性,提出了一种在线特征提取算法,并用该算法对训练实例进行分类。利用公开数据集对算法的性能进行了分析,结果表明,提出的在线特征提取算法能准确地对训练实例进行分类,因而能更好地适用于大数据环境下的数据挖掘。

一种基于互信息最大化的模型无关基因选择方法

魏莎莎,陆慧娟,安春霖,郑恩辉,金伟

计算机科学. 2014, 41 (9): 243-247. doi:10.11896/j.issn.1002-137X.2014.09.046

摘要 ( 199 )

PDF(401KB) ( 511 )

参考文献 | 相关文章 | 多维度评价

针对大规模基因芯片高维度的基因表达数据存在大量无关和冗余特征可能降低分类器性能的问题,提出了一种基于互信息最大化方法(MMI)和与遗传算法的模型无关的基因选择方法来将特征选择转化为全局优化问题,其中的适应度函数定义为类间距离与类内距离之比,适应程度高。为了评价算法的性能,采用3个数据集进行了实验,结果表明MMIGA-Selection取得了较好的效果,在每个数据集上获得了较高的5折交叉验证正确率。MMIGA-Selection主要有两个优点:一是可以有效减少冗余基因；二是模型无关性,选择得出的特征子集可直接用于其他类型的分类器,分类精度较高。

一种基于语义距离的Web评论SVM情感分类方法

肖正,刘辉,李兵

计算机科学. 2014, 41 (9): 248-252. doi:10.11896/j.issn.1002-137X.2014.09.047

摘要 ( 232 )

PDF(513KB) ( 589 )

参考文献 | 相关文章 | 多维度评价

情感倾向分析本质上可以看作是一个情感极性分类问题。在海量数据处理的大背景下,为了提高文本情感判断的准确率,提出了一种结合潜在语义分析LSA(Latent Semantic Analysis)和支持向量机SVM(Supported Vector Machine)的文本褒贬情感倾向分类方法。从语义的角度利用潜在语义分析方法建立“词-文档”的语义距离向量空间模型,然后使用具有良好分类精度和泛化能力的支持向量机进行情感分类。实验结果表明,该方法在句子简短、情感倾向比较明显的Web评论中的准确率较传统的SVM方法有了一定的提高,在测试集上的分类准确率接近88%。

基于词典的中文微博情绪识别

牛耘,潘明慧,魏欧,蔡昕烨

计算机科学. 2014, 41 (9): 253-258. doi:10.11896/j.issn.1002-137X.2014.09.048

摘要 ( 437 )

PDF(632KB) ( 1915 )

参考文献 | 相关文章 | 多维度评价

微博等社交媒体已成为表达个人情绪和感受的重要平台。自动分析微博文本表达的情绪对于迅速了解大众情绪走向以及调节个人情绪有着重要的意义。文中首次针对中文微博中的情绪进行自动分析,识别微博表达的喜、哀、怒、惧情绪。提出以词典为依据的基于规则的方法,通过实验详细分析了中文情绪词典在社交媒体文本分析中的现状,讨论了存在的主要问题。并深入讨论了微博中情绪表达的语言特点,为建立高精度的情绪分析系统提供了依据。

动态路网中基于实时路况信息的分布式路径生成算法

龙其,叶晨,张亚英

计算机科学. 2014, 41 (9): 259-262. doi:10.11896/j.issn.1002-137X.2014.09.049

摘要 ( 182 )

PDF(428KB) ( 923 )

参考文献 | 相关文章 | 多维度评价

动态路网中的寻路问题在交通诱导和交通流仿真中有重要意义。提出一种基于实时路况信息的分布式路径规划算法,根据安装在道路路口的智能摄像头所采集到的交通参数对路口的畅通程度进行建模,估算车辆在路口间通行需要的时间。当有车辆需要交通诱导时,通过智能摄像头之间的网络进行基于网络路由思想的分布式最短路径寻路,在寻路过程中加入延时发送机制。网络中的智能摄像头根据车辆所在路口的畅通程度和到邻近路口的距离设置一定的延时,来广播路径询问数据包,使数据包能模拟当前的路况,从而有效、迅速地获得路径规划的结果。

基于CUDA的并行粒子群优化算法研究及实现

陈风,田雨波,杨敏

计算机科学. 2014, 41 (9): 263-268. doi:10.11896/j.issn.1002-137X.2014.09.050

摘要 ( 176 )

PDF(478KB) ( 1469 )

参考文献 | 相关文章 | 多维度评价

应用图形处理器(GPU)来加速粒子群优化(PSO)算法并行计算时,为突出其加速性能,经常有文献以恶化CPU端PSO算法性能为代价。为了科学比较GPU-PSO算法和CPU-PSO算法的性能,提出用“有效加速比”作为算法的性能指标。文中给出的评价方法不需要CPU和GPU端粒子数相同,将GPU并行算法与最优CPU串行算法的性能作比较,以加速收敛到目标精度为准则,在统一计算设备架构(CUDA)下对多个基准测试函数进行了数值仿真实验。结果表明,在GPU上大幅增加粒子数能够加速PSO算法收敛到目标精度,与CPU-PSO相比,获得了10倍以上的“有效加速比”。

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

项泰宁,郭丹,王海平,胡学钢

计算机科学. 2014, 41 (9): 269-273. doi:10.11896/j.issn.1002-137X.2014.09.051

摘要 ( 172 )

PDF(464KB) ( 472 )

参考文献 | 相关文章 | 多维度评价

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

格值一阶逻辑LF(X)中的α-语义归结方法

张家锋,徐扬

计算机科学. 2014, 41 (9): 274-278. doi:10.11896/j.issn.1002-137X.2014.09.052

摘要 ( 133 )

PDF(390KB) ( 572 )

参考文献 | 相关文章 | 多维度评价

自动推理是人工智能的一个重要研究方向,基于归结原理的自动推理因易于在计算机上实现而得到广泛研究。语义归结是对归结原理的一种改进,它利用限制参与归结子句类型和归结文字顺序的方法来提高推理效率。为了提高基于格蕴涵代数的格值逻辑的α-归结原理的效率,将语义归结策略应用于α-归结原理。首先给出了格值一阶逻辑系统中的α-语义归结概念和α-语义归结演绎概念,接着讨论了格值一阶逻辑系统的α-语义归结方法,并证明了其可靠性和条件完备性,最后通过实例说明了其有效性。

一种支持多种子近似串匹配的q-gram索引

孙德才,王晓霞

计算机科学. 2014, 41 (9): 279-284. doi:10.11896/j.issn.1002-137X.2014.09.053

摘要 ( 281 )

PDF(473KB) ( 382 )

参考文献 | 相关文章 | 多维度评价

如何在大型文本库中快速找出给定串的近似串是大数据时代要解决的关键问题。基于多种子的近似串匹配算法因匹配速度快而得到众多学者的青睐,但巨大的索引空间消耗也使其难以处理大型文本库。提出了一种支持多种子的q-gram索引结构,通过该索引能够快速地计算出给定任意长度连续种子的地址集合,解决了多种子近似串匹配算法中种子的数目和长度受存储空间限制的问题。实验数据显示,新索引方案成倍地减少了存储空间的消耗。实验结果表明,提出的索引方案在大数据环境下的多种子近似匹配中具有一定的优势。

改进的分布估计算法求解软硬件划分问题

余娟,贺昱曜,冯晓华

计算机科学. 2014, 41 (9): 285-289. doi:10.11896/j.issn.1002-137X.2014.09.054

摘要 ( 185 )

PDF(371KB) ( 414 )

参考文献 | 相关文章 | 多维度评价

软硬件划分是软硬件协同设计中的关键步骤,为NP难问题。分布估计算法可以解难优化问题,具有很好的全局搜索能力,但存在局部搜索能力差、种群多样性易失问题。针对此问题,对分布估计算法进行改进,对精英解进行克隆选择以加强局部搜索能力,对概率模型进行修正以改善种群多样性损失问题。同时,针对划分问题提出一种不可行解的修复方法。将改进后的分布估计算法应用于软硬件划分问题, 并与现有算法做比较,结果表明所提算法在不同的约束条件下均可获得更好的优化结果。

基于语义技术的柑橘园土壤环境判定决策支持系统的设计与实现

朱颖,张自力

计算机科学. 2014, 41 (9): 290-293. doi:10.11896/j.issn.1002-137X.2014.09.055

摘要 ( 199 )

PDF(1415KB) ( 463 )

参考文献 | 相关文章 | 多维度评价

农业生产管理决策支持系统对提高相关农产品的产量与质量起到越来越重要的作用。针对柑橘生产中土壤环境影响柑橘生长的问题,提出了基于语义技术的柑橘园土壤环境判定决策支持系统,重点讨论了该决策支持系统的系统结构、土壤语义数据库的建立以及推理规则的定义等,并应用语义数据库软件AllegroGraph实现了柑橘土壤语义数据库。

基于分块KPCA集成的人脸民族特征提取研究

刘文辉,许瑞,刘华咏,马光春

计算机科学. 2014, 41 (9): 294-296. doi:10.11896/j.issn.1002-137X.2014.09.056

摘要 ( 183 )

PDF(870KB) ( 377 )

参考文献 | 相关文章 | 多维度评价

为了实现人脸图像民族特征提取,提出了一种分块集成KPCA的特征提取方法。考虑到利用全局特征与局部特征的互补性能够更好地反映信息的本质,先以KPCA提取整体图像特征,然后使用KPCA 对各个分块进行局部特征提取,再组合为民族特征,最后使用设计的Boosting-RBF分类器进行民族分类识别。实验以构建的少数民族人脸样本库为研究对象,对维吾尔族、柯尔克孜族、蒙古族、塔吉克族的人脸图像进行民族特征提取。实验结果表明:提取的人脸民族特征,可以对人脸图像进行较准确的民族分类识别。

基于MultiLayer水平集的脑MRI图像分割框架

朱晓舒,孙权森,夏德深,孙怀江

计算机科学. 2014, 41 (9): 297-300. doi:10.11896/j.issn.1002-137X.2014.09.057

摘要 ( 159 )

PDF(844KB) ( 411 )

参考文献 | 相关文章 | 多维度评价

提出了一种新的自动初始化水平集的方法和基于MultiLayer水平集的活动轮廓模型。该模型同时进行偏移场去除和图像分割,因此可以有效地克服灰度不均匀性的影响。最后利用了大脑皮层的距离信息,在框架中增加了厚度约束项。实验结果显示,相比著名的LBF模型,该框架不但可以获得更高的分割精度,而且分割时间也大大减少。

基于指导滤波与二值图像组互相关匹配的3D掌纹识别

刘明,李丽华,李哲

计算机科学. 2014, 41 (9): 301-305. doi:10.11896/j.issn.1002-137X.2014.09.058

摘要 ( 203 )

PDF(2981KB) ( 595 )

参考文献 | 相关文章 | 多维度评价

提出了一种鲁棒的掌纹识别方法。在特征提取阶段,使用指导图像滤波去除噪声,然后基于Gabor变换提取鲁棒的掌纹方向特征,并使用一组二值图像表示每幅3D掌纹图像；在匹配阶段,采用了基于二值图像组互相关运算的匹配算法。该方法能够充分利用图像组中的特征配准图像来得到准确的匹配分数。HK-PolyU 2D+3Dpalmprint database数据库上的实验表明,该方法能够有效提高掌纹识别算法的识别率。

分层关联的多目标跟踪算法研究

杨国亮,张进辉

计算机科学. 2014, 41 (9): 306-310. doi:10.11896/j.issn.1002-137X.2014.09.059

摘要 ( 176 )

PDF(2653KB) ( 488 )

参考文献 | 相关文章 | 多维度评价

检测跟踪(Tracking by detection)是近年来多目标跟踪领域的一个主要研究方向。遵循检测跟踪框架,提出一种基于分层关联的全局性的数据关联算法。首先利用目标检测器在整个视频上检测目标,得到检测响应；然后利用广义最小团图在视频片段中对检测响应进行数据关联,得到轨迹片段；最后再在整个视频中对轨迹片段进行分层关联,得到最终的轨迹。在公共数据集上的测试结果表明,该算法能够有效地对多个目标进行数据关联,具有较强的处理遮挡能力。

雾化图像的约束进化时频加权滤波去雾算法

刘伟,崔永锋,吴相林

计算机科学. 2014, 41 (9): 311-314. doi:10.11896/j.issn.1002-137X.2014.09.060

摘要 ( 149 )

PDF(1209KB) ( 474 )

参考文献 | 相关文章 | 多维度评价

传统的基于物理纹理特征的去雾算法不能有效去除雾化图像的边缘雾点,特别在浓雾条件下处理效果不好。提出一种采用约束进化时频加权滤波的雾化图像去雾算法,首先采用分块处理方法,基于3×3模板求解雾化图像的暗原色。以图像暗原色为新的图像特征,设置约束进化条件,对图像雾点进行平滑重排伪魏格纳-维尔-霍夫变换(RSPWVD-Hough)时频分析,提取RSPWVD-Hough时频特征作为加权向量来指导雾化图像的盒子滤波,实现去雾处理,并通过约束进化算法对图像去雾的结果不断进行循环优化。RSPWVD-Hough时频特征能有效反映图像的边缘雾化特征点,故对雾化图像的边缘雾点去雾效果甚好。仿真测试表明,改进的图像去雾算法能在提高处理速度的同时优化图像输出结果,透过率提高明显,在浓雾条件下对图像目标识别等领域有较好的应用价值。

一种改进HOG特征的行人检测算法

田仙仙,鲍泓,徐成

计算机科学. 2014, 41 (9): 320-324. doi:10.11896/j.issn.1002-137X.2014.09.062

摘要 ( 253 )

PDF(405KB) ( 688 )

参考文献 | 相关文章 | 多维度评价

针对HOG特征检测准确率高、计算量大的特点,通过对HOG特征的结构进行调整,提出了使用Fisher特征挑选准则来挑选出有区别能力的行人特征块,得到MultiHOG特征。该算法结合线性SVM二值分类器,实现行人滑动窗口检测。用Inria标准数据集和自行拍摄数据集进行了测试,结果证明该算法较HOG在准确率及实时性上都有很大的提高。