1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2015年第7期, 刊出日期:2018-11-14
  
目次
无线传感器网络时间同步机制研究
胡 冰 孙知信
计算机科学. 2015, 42 (7): 1-4.  doi:10.11896/j.issn.1002-137X.2015.07.001
摘要 ( 149 )   PDF(431KB) ( 512 )   
参考文献 | 相关文章 | 多维度评价
时间同步是无线传感器网络中一项重要的底层支撑技术,是实现节点的协同感知、通信、能量管理等网络功能的前提条件。针对无线传感器网络不同的应用需求,相继提出了不同种类的时间同步算法。归纳了无线传感器网络时间同步机制的分类方法,分析了每类典型的时间同步机制,最后总结了无线传感器网络时间同步机制的发展方向和未来的研究热点。
网络表格间的快照关系发现
王 宁 任红伟
计算机科学. 2015, 42 (7): 5-11.  doi:10.11896/j.issn.1002-137X.2015.07.002
摘要 ( 156 )   PDF(817KB) ( 222 )   
参考文献 | 相关文章 | 多维度评价
近年来,互联网上涌现出大量结构化的表格数据,网络表格的价值不仅在于数据本身,还在于数据之间的关系。只有探测出表格之间潜在的关系,方能更好地利用这些结构化数据。因此提出发现网络表格间的快照关系,并给出发现快照关系的框架以及检测与给定表之间满足某种匹配关系的快照表的算法,快照表可用于优化查询以及在大数据环境下实时地返回部分查询结果。提出了基于实体和属性重合度的评分方法,并引入实体新鲜度的概念,使得算法在快照关系的发现过程中更多地关注能提供新鲜实体的表;与此同时,基于Bayes模型的表格内容增强算法能更加准确地判断属性列上值的一致性,从而提高快照关系发现的准确率。大量实验表明,该评分模型能发现高质量的快照表,且在快照的查询精度和召回率上表现出色。
MSP问题NP完全性研究
吴添君 姜新文
计算机科学. 2015, 42 (7): 12-14.  doi:10.11896/j.issn.1002-137X.2015.07.003
摘要 ( 296 )   PDF(277KB) ( 508 )   
参考文献 | 相关文章 | 多维度评价
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
面向军事文本的命名实体识别
冯蕴天 张宏军 郝文宁
计算机科学. 2015, 42 (7): 15-18.  doi:10.11896/j.issn.1002-137X.2015.07.004
摘要 ( 270 )   PDF(437KB) ( 986 )   
参考文献 | 相关文章 | 多维度评价
针对军事文本中的命名实体,提出一种基于条件随机场模型的半监督命名实体识别方法,旨在将人员军职军衔名、军事装备名、军用物资名、军事设施名、军事机构名(含部队番号)以及军用地名等军事命名实体的识别融合到一个统一的技术框架中。该方法针对军事文本的语法特点建立高效的特征集合,建立条件随机场模型对军事命名实体进行识别,并依次使用基于词典的方法和基于规则的方法对识别结果进行校正。实验表明,该方法在军事文本中能够出色地完成命名实体识别任务,在测试语料上的F-值最高达到90.9%,接近通用领域中命名实体识别的水平。
2014’全国理论计算机科学年会
基于GPU加速的定向凝固相场模拟计算研究
胡延苏,高 昂,王志军,慕德俊
计算机科学. 2015, 42 (7): 19-21.  doi:10.11896/j.issn.1002-137X.2015.07.005
摘要 ( 119 )   PDF(332KB) ( 431 )   
参考文献 | 相关文章 | 多维度评价
相场法作为一种极具优势的微观组织数值模拟方法,已经在凝固微观组织演化机制的研究中得到了广泛应用。然而无论是从计算尺度还是微观组织演化时间上考虑,相场模拟计算量均非常大,对计算机有着非常高的要求。相对于传统的中央处理器(CPU)计算,图形处理器(GPU)计算是最近发展的一种高效计算手段。提出了一种基于GPU加速的定向凝固相场模拟计算策略,实现了大尺度条件下的定向凝固界面形态演化的加速计算。计算结果表明,对于单个计算机,GPU计算与CPU计算的加速比可以高达30余倍。GPU加速将为相场模拟的发展及应用带来新的契机。
一种支持多版权的地理数据增量水印方法
廖 璋 熊胜超 彭智勇 彭煜玮
计算机科学. 2015, 42 (7): 22-27.  doi:10.11896/j.issn.1002-137X.2015.07.006
摘要 ( 87 )   PDF(471KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
目前地理数据水印方法有很多,但大都缺少对地理数据同步保护的考虑,同时没有在同步保护的基础上进行多版权水印嵌入的方法。分析了地理数据增量水印和多版权水印的问题,基于量化调制技术,提出了一种能兼顾增量水印和多版权水印的地理数据水印方法。该方法采用基于距离划分的策略,将特征点集划分成两个可重现的不相交子集,通过分别缩放两个子集嵌入双重水印,保证了所有顶点都只在精度范围内修改一次,使保真性得到控制。此外,缩放调制策略使地理数据形状尽可能得到保证。实验表明,该方法能满足增量水印和多版权水印的要求,同时具有很好的鲁棒性。
基于序列的子问题相容性技术
陈德泉 张永刚 辛 颖 刘文壮
计算机科学. 2015, 42 (7): 28-31.  doi:10.11896/j.issn.1002-137X.2015.07.007
摘要 ( 100 )   PDF(366KB) ( 233 )   
参考文献 | 相关文章 | 多维度评价
研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性(SSAC),并给出相应的实现算法。然后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间。通过对随机问题和composed问题的测试表明,所提算法的效率是已有算法SAC-SDS和SAC-3的2~3倍。
基于指向与数值抽象的带指针算术程序的分析方法
尹帮虎,陈立前,王 戟
计算机科学. 2015, 42 (7): 32-37.  doi:10.11896/j.issn.1002-137X.2015.07.008
摘要 ( 127 )   PDF(471KB) ( 262 )   
参考文献 | 相关文章 | 多维度评价
带指针算术的程序往往包含数组越界、缓冲区溢出等运行时错误。单纯的指针分析技术和数值分析技术都无法有效处理指针算术。为了将指针分析与数值分析相结合,首先提出一种新的指针内存模型,然后基于该模型设计了一个刻画指针指向关系和指针偏移量的抽象域。最后在抽象解释框架下,设计并实现了一个面向带指针算术C程序的静态分析工具原型PAA。实验结果表明,PAA能够有效地分析指针程序的指向关系和数值性质,并能够在效率和精度间取得合理的权衡。
BDL模型到UML状态图的可视化方法研究
马 丽,毋国庆,黄 勃,程 铭,崔梦天
计算机科学. 2015, 42 (7): 38-43.  doi:10.11896/j.issn.1002-137X.2015.07.009
摘要 ( 158 )   PDF(984KB) ( 280 )   
参考文献 | 相关文章 | 多维度评价
针对复杂软件系统需求模型难以理解的问题,提出了一种UML状态图描述需求模型的可视化方法。该方法基于行为描述语言(Behavior Description Language,BDL)构建的需求模型,通过定义映射规则,将BDL模型中的行为、行为间关系与UML状态图中的迁移相关联,并将行为执行后产生的状态与UML状态图中状态相关联。然后根据转换算法自动提取各结点信息,输出完整的状态图,从而实现BDL需求模型的可视化。最后通过实例,验证了该方法的有效性。
可计算性逻辑中CoL2系统的可判定性分析
李兴香 栾峻峰
计算机科学. 2015, 42 (7): 44-47.  doi:10.11896/j.issn.1002-137X.2015.07.010
摘要 ( 114 )   PDF(335KB) ( 282 )   
参考文献 | 相关文章 | 多维度评价
可计算性(Computability)即算法有解性,是数学和计算机科学领域中重要的概念之一。可计算性逻辑(Computability Logic,CoL)是关于可计算性的形式理论,是一种交互的资源逻辑。其中,CoL2系统采用博弈的语义,是对经典命题逻辑的扩展,在经典命题逻辑的基础上添加了选择运算和一般原子,比经典命题逻辑更富有表达力,具有更广阔的应用前景,并且有较高的证明效率。分析了CoL2系统的可判定性,即通过提出一个算法来判断任意一个CoL2公式是否是可证明的,并且证明了该算法是多项式空间内运行的。
聚类集成时机的确定
孟晓龙 杨 燕 王红军 肖文超
计算机科学. 2015, 42 (7): 48-51.  doi:10.11896/j.issn.1002-137X.2015.07.011
摘要 ( 119 )   PDF(354KB) ( 255 )   
参考文献 | 相关文章 | 多维度评价
使用集成学习技术可以提高聚类性能。在实验中发现,当各聚类成员聚类迭代到中后期时进行集成所得的结果会优于其迭代完全停止时进行集成所得的结果。利用集成网络泛化能力的偏差-方差分解理论对聚类集成过程中的上述现象进行解释,将提高集成网络间泛化能力的早期停止准则应用于聚类集成过程,并提出聚类集成时机的概念。对比实验表明,基于早期停止准则的聚类集成得到的结果较好,且更节约聚类集成的时间,为寻求聚类集成的最佳时机提供了可行性建议和方法。
基于信息增益的多标签特征选择算法
李 玲,刘华文,徐晓丹,赵建民
计算机科学. 2015, 42 (7): 52-56.  doi:10.11896/j.issn.1002-137X.2015.07.012
摘要 ( 223 )   PDF(416KB) ( 753 )   
参考文献 | 相关文章 | 多维度评价
多标签特征选择是一种提高多标签分类器性能的技术。针对目前这类技术在给出合理特征子集合时无法同时兼顾计算复杂度和标签间的相关性的问题,提出一种基于信息增益的多标签分类算法。该算法假设特征之间相互独立,首先使用单个特征与整个标签集合之间的信息增益来度量这两者的关联程度,再根据阈值删除不相关的特征以得到最优特征子集合。实验表明,该算法能有效地提高多标签分类器的分类性能。
三值量子基本门及其对量子Fourier变换的电路实现
樊富有,杨国武,张 艳,杨 钢
计算机科学. 2015, 42 (7): 57-61.  doi:10.11896/j.issn.1002-137X.2015.07.013
摘要 ( 148 )   PDF(332KB) ( 502 )   
参考文献 | 相关文章 | 多维度评价
理论上可以把量子基本门组合在一起来实现任何量子电路和构建可伸缩的量子计算机。但由于构建量子线路的量子基本门数量庞大,要正确控制这些量子门十分困难。因此,如何减少构建量子线路的基本门数量是一个非常重要和非常有意义的课题。提出采用三值量子态系统构建量子计算机,并给出了一组三值量子基本门的功能定义、算子矩阵和量子线路图。定义的基本门主要包括三值量子非门、三值控制非门、三值Hadamard门、三值量子交换门和三值控制CRk门等。通过把量子Fourier变换推广到三值量子态,成功运用部分三值量子基本门构建出能实现量子Fourier变换的量子线路。通过定量分析发现,三值量子Fourier变换的线路复杂度比二值情况降低了至少50%,表明三值量子基本门在降低量子计算线路复杂度方面具有巨大优势。
一种基于TF-HBPN的复杂系统行为分析方法
陈 倩,佘 维,叶阳东
计算机科学. 2015, 42 (7): 62-67.  doi:10.11896/j.issn.1002-137X.2015.07.014
摘要 ( 122 )   PDF(526KB) ( 268 )   
参考文献 | 相关文章 | 多维度评价
针对大规模复杂系统建模分析时的状态爆炸问题,提出一种扩展了时间因素的分层贝叶斯Petri网模型(Hierarchical Bayesian Petri Net With Time Factor,TF-HBPN),并基于该模型提出一种递归构建方法和递归溯因行为分析方法。该方法首先对观测到的系统行为构造顶层TF-HBPN模型,进而通过分层递归方法将复杂系统并发行为分析问题进行分解,并通过递归溯因推理和时序分析来计算非观测系统行为及其事件链的发生概率,最后将分析结果与正常动作事件链进行对比,分离出干扰信息。实例分析表明,该方法可对大规模复杂系统行为进行快速建模分析,当观测数据存在干扰和缺失时仍能进行系统行为的分析和现象的溯因,分析结果的可信度较高。与其他基于Petri网的复杂系统分析方法相比,该方法建模难度更低,模型表达更为简洁也更易理解。
一种求解置换Flow Shop调度问题的DRPFSP算法
魏嘉银 秦永彬 许道云
计算机科学. 2015, 42 (7): 68-73.  doi:10.11896/j.issn.1002-137X.2015.07.015
摘要 ( 156 )   PDF(781KB) ( 350 )   
参考文献 | 相关文章 | 多维度评价
针对置换Flow Shop调度问题,在对经典启发式算法进行研究的基础上,提出了一种用于求解此类问题的DRPFSP算法。算法首先对加工时间矩阵A进行数据标准化处理;然后通过引入一个概率矩阵P2×m和相应的降维函数fp(A)=PA,将含有m台机器的原问题转化为含2台机器的新问题;再运用Johnson算法对新问题进行求解得到一个调度序列π0;最后结合插入邻域快速评价法对π0进行处理以获得原问题的一个调度方案π。实验结果表明,相对于经典的启发式算法,DRPFSP算法能更有效地对置换Flow Shop调度问题进行求解。
具有数目约束的负载均衡问题
李伟东 李建平
计算机科学. 2015, 42 (7): 74-77.  doi:10.11896/j.issn.1002-137X.2015.07.016
摘要 ( 127 )   PDF(386KB) ( 267 )   
参考文献 | 相关文章 | 多维度评价
考虑了具有数目约束的负载平衡问题的一种特殊情形,称之为2-半匹配问题。分析了此问题在3种目标函数下的计算复杂性,并设计了相应的近似算法。
有向无环图的高效归约算法
侯 睿 武继刚
计算机科学. 2015, 42 (7): 78-84.  doi:10.11896/j.issn.1002-137X.2015.07.017
摘要 ( 131 )   PDF(556KB) ( 517 )   
参考文献 | 相关文章 | 多维度评价
将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。
适用于Android智能手机的灰度均值水印算法
彭 乐 金 聪
计算机科学. 2015, 42 (7): 85-90.  doi:10.11896/j.issn.1002-137X.2015.07.018
摘要 ( 93 )   PDF(1260KB) ( 267 )   
参考文献 | 相关文章 | 多维度评价
提出了一种适用于Android智能手机的灰度均值数字水印算法。在嵌入阶段,将经过像素重新组织的水印图像嵌入载体图像中;在提取阶段,先提取出初始水印,再判断初始水印是否需要区域替换,如果需要,则进行区域替换,否则不进行;最后,将初始水印还原成所需的水印图像。实验表明,该算法在具有良好水印透明性的同时,对JPEG压缩、加噪声、裁剪等常见的攻击具有鲁棒性。
基于补偿事务的业务流程异常处理建模研究
雷义伟 贲可荣
计算机科学. 2015, 42 (7): 91-94.  doi:10.11896/j.issn.1002-137X.2015.07.019
摘要 ( 83 )   PDF(400KB) ( 286 )   
参考文献 | 相关文章 | 多维度评价
对补偿触发条件的判断会影响补偿的正确性,由于业务流程的活动之间具有补偿依赖关系,尤其是并发结构中的补偿依赖,使得流程开发人员在设计补偿流程时容易出错。分析了顺序、选择、并发等几种基本流程结构及其复合结构中的补偿依赖,给出了补偿活动触发条件计算方法和补偿事务的Petri网模型构造过程,并通过实例说明了方法的可行性。
分布式交互应用中服务器放置问题的启发式算法
郑晶晶 张 晶 武继刚
计算机科学. 2015, 42 (7): 95-98.  doi:10.11896/j.issn.1002-137X.2015.07.020
摘要 ( 109 )   PDF(428KB) ( 293 )   
参考文献 | 相关文章 | 多维度评价
分布式交互应用是允许分散在不同地点的多个参与者能实时进行交互的网络系统,它的交互质量在很大程度上取决于网络延迟,而通过对服务器位置的合理布局可以降低网络延迟。因此,服务器放置是影响分布式交互应用的交互性能的关键因素。针对分布式交互应用中服务器放置问题,提出了模拟退火算法和禁忌搜索算法,并与已有的遗传算法进行了比较。通过实验可以看出,尽管在求得较好解的速度方面,遗传算法占据优势,但在求得解的质量方面,提出的模拟退火算法和禁忌搜索算法均优于遗传算法,在服务器数量相同的条件下,延迟平均降低了15.5%和15.2%,更加有效地提高了交互质量。
组合Web服务业务流程访问控制技术研究综述
上超望,刘清堂,王艳凤
计算机科学. 2015, 42 (7): 99-102.  doi:10.11896/j.issn.1002-137X.2015.07.021
摘要 ( 75 )   PDF(374KB) ( 254 )   
参考文献 | 相关文章 | 多维度评价
业务流程访问控制是保证组合Web服务增值安全应用的关键技术,着重论述了组合Web服务业务流程访问控制技术的研究现状及问题。首先对组合Web服务业务流程安全需求进行了分析,然后从组合Web服务业务流程访问控制模型、业务流程运行时访问授权约束、业务流程协同访问授权的一致性检验3个方面分析了业务流程访问控制核心技术的研究进展。最后,结合已有的研究成果,指出了目前研究的挑战以及未来的发展趋势。
基于SPIN的Andrew Secure RPC协议并行攻击模型检测
肖美华 朱 科 马成林
计算机科学. 2015, 42 (7): 103-107.  doi:10.11896/j.issn.1002-137X.2015.07.022
摘要 ( 88 )   PDF(371KB) ( 306 )   
参考文献 | 相关文章 | 多维度评价
Andrew Secure RPC协议具有身份认证和秘钥交换功能,其因简洁明了而被广泛应用于对称密钥加密体系中。模型检测技术具有高度自动化的优点,在协议安全性验证领域得到广泛应用,但模型检测方法只能检测到一轮协议会话中存在的攻击,难以检测到多轮并行会话中存在的并行攻击。针对Andrew Secure RPC协议运行环境中存在的并行性与可能出现的安全隐患,提出了组合身份建模方法。该方法运用著名的SPIN模型检测工具,对Andrew Secure RPC协议进行模型检测, 从而得到攻击序列图,成功发现并行反射攻击和类缺陷攻击。上述组合身份建模方法为复杂环境下协议的模型检测提供了新的方向。
PPI网络的改进马尔科夫聚类算法
胡庆生 雷秀娟
计算机科学. 2015, 42 (7): 108-113.  doi:10.11896/j.issn.1002-137X.2015.07.023
摘要 ( 127 )   PDF(439KB) ( 375 )   
参考文献 | 相关文章 | 多维度评价
蛋白质相互作用(PPI)网络是生物信息学的一个新的研究领域。近年来马尔科夫(MCL)聚类算法在未知蛋白质的功能模块预测方面发挥了重要作用,但是聚类质量不高,为此提出了一种基于突变因子和惩罚因子及重新定义解释聚类结果的MCL聚类算法。该算法采用惩罚因子,惩罚质量较大的吸引子;采用突变因子在算法后期断绝初始转移概率对转移概率的束缚。算法在PPI网络数据集上进行了测试,结果表明该算法不但可以抑制小类的产生,而且聚类结果的质量在Avg.F方面相对于基本MCL算法提高了13.1%。
一种改进的基于粒子群的三维片上网络优化布局算法
宋国治 张大坤 涂 遥 黄 翠 王莲莲
计算机科学. 2015, 42 (7): 114-117.  doi:10.11896/j.issn.1002-137X.2015.07.024
摘要 ( 94 )   PDF(427KB) ( 237 )   
参考文献 | 相关文章 | 多维度评价
提出了一种改进的基于粒子群算法的优化布局算法(Improved Particle Swarm Optimization,IPSO)来替换原有的基于模拟退火(Simulated Annealing,SA)算法的优化布局算法,使其更加适用于大型三维片上网络的仿真。通过比较这两种算法的基本思想,给出了这两种算法的实现步骤并详细介绍了IPSO算法的改进思路。最后利用一款现有的三维片上网络仿真器进行了仿真验证。结果表明,提出的IPSO算法比原来的SA算法更适用于大型三维片上网络的仿真。
基于抽象和组合方法的网络协议验证
陈道喜,张广泉,徐成凯,陈国彬
计算机科学. 2015, 42 (7): 118-121.  doi:10.11896/j.issn.1002-137X.2015.07.025
摘要 ( 114 )   PDF(341KB) ( 270 )   
参考文献 | 相关文章 | 多维度评价
由于模型检测存在状态爆炸问题,多主体的网络协议组合模型检测往往难以进行。为了缓解该问题,分析了通信主体数量增加对状态数量的影响,提出了组合式的抽象验证方法。首先根据所需验证的LTL性质,建立各个通信主体的Kripke结构,再对该Kripke结构进行抽象;然后组合抽象模型;最后运用Spin对组合抽象模型进行检验。为验证该方法的有效性,对NSPK协议进行了检测,结果表明,该方法所需的状态空间向量长度、搜索深度、存贮和遍历的状态数都有明显减少,有利于缓解状态爆炸问题。
基于截断边扩展图的网络可靠度近似分析
孙 云 钟发荣 莫毓昌 潘竹生
计算机科学. 2015, 42 (7): 122-124.  doi:10.11896/j.issn.1002-137X.2015.07.026
摘要 ( 89 )   PDF(223KB) ( 302 )   
参考文献 | 相关文章 | 多维度评价
小型网络可以快速计算出可靠度精确值,但对于大型网络,可靠性精确值的计算非常困难,因此提出一种基于截断边扩展图的网络可靠性近似分析算法。实验结果证明,该算法能够在生成较小边扩展图和等价BDD(Binary Decision Diagrams)的基础上得到误差较小的近似值。
广义模糊集GFScom在模糊综合评判中的应用
张胜礼,李永明
计算机科学. 2015, 42 (7): 125-128.  doi:10.11896/j.issn.1002-137X.2015.07.027
摘要 ( 81 )   PDF(370KB) ( 252 )   
参考文献 | 相关文章 | 多维度评价
针对FScom在刻画模糊性知识及其3种不同否定关系上的一些不足,提出了广义模糊集GFScom,它从哲学层面上更好地刻画了模糊性知识及其3种不同否定之间的关系。在此基础上,给出了基于GFScom的模糊综合评判方法。应用示例表明,GFScom对3种否定的处理不仅使模糊评判的计算更加简便,而且合理有效。
业务过程的自动配置与管理
吴亚洲 杨启帆 蒋建民 张 仕
计算机科学. 2015, 42 (7): 129-133.  doi:10.11896/j.issn.1002-137X.2015.07.028
摘要 ( 110 )   PDF(503KB) ( 298 )   
参考文献 | 相关文章 | 多维度评价
一个可配置的业务过程模型可以通过配置来满足组织的特定要求。配置活动需要自动确定一个可配置过程模型的变体,同时保证该特定过程模型的正确性。然而,很少有方法能够解决此问题。提出一种新方法,即先将可配置的过程模型自动分离成原子子过程模型,再由这些模型组合成需要的过程模型,该方法能保证得到的过程模型的正确性(该过程模型无异常行为问题)。与现有的方法相比,新方法与特定的语言无关,而且避免了独立处理配置活动,降低了计算复杂度。
两类量子游走组成的非确定型量子程序的终止验证
雷红轩
计算机科学. 2015, 42 (7): 134-137.  doi:10.11896/j.issn.1002-137X.2015.07.029
摘要 ( 80 )   PDF(276KB) ( 279 )   
参考文献 | 相关文章 | 多维度评价
首先给出了C4空间中由量子游走组成的非确定型量子程序的概念,其次讨论了它们从初态运行时在不同的测量算子下的可达集合、终止集合和发散集合。研究表明:非确定型量子程序的终止、发散和可达集合、发散集合与选取的测量算子有密切的关系。程序在不同测量算子作用下从同一个初态运行时可能终止,也可能发散;并且,同一个初态的可达集合中终态和发散态共存。
网络与通信
一种双网同步搜索的虚拟网络映射算法
彭利民
计算机科学. 2015, 42 (7): 138-141.  doi:10.11896/j.issn.1002-137X.2015.07.030
摘要 ( 66 )   PDF(336KB) ( 225 )   
参考文献 | 相关文章 | 多维度评价
针对虚拟网络映射中的资源分配问题,通过建立双网同步搜索映射模型,采用普里姆最小生成树算法思想,同步搜索虚拟网络中的待映射虚拟节点和物理网络中的可映射物理节点,将相邻的虚拟节点依次映射到邻接的物理节点上,协调完成节点及其邻接链路的映射操作,使虚拟网络映射具有拓扑一致性。仿真实验表明,提出的DS-VNM算法能有效地降低虚拟链路的映射路径长度,提高网络收益与网络代价比、虚拟网络请求接受率,获得了较好的资源分配性能。
改进的OFDM双向中继功率分配策略
潘沛生 赵喜凤
计算机科学. 2015, 42 (7): 142-145.  doi:10.11896/j.issn.1002-137X.2015.07.031
摘要 ( 99 )   PDF(396KB) ( 315 )   
参考文献 | 相关文章 | 多维度评价
针对放大转发(AF)模式下正交频分复用(OFDM)双向中继网络如何提高系统总容量的问题,提出了一种低复杂度的以系统总速率最大化为目标的最优功率分配策略。该策略先建立用户与中继节点间的最优功率分配比例关系,将三层功率最优化问题简化为一层最优化问题,实现了将节点上的功率优化分配问题转化成一种易于处理的形式,以较小的复杂度获得了各节点上分配的功率占所在子载波对上分配的功率的比重;然后利用原对偶内点法求解各子载波间的功率分配问题;最终,求得各节点最优的功率分配。仿真实验表明,所提算法能显著提升系统总速率,且其性能随子载波数的增多而提升。
基于弱连接理论的GitHub网络的分形特征分析
匡 立,易云飞,李元香
计算机科学. 2015, 42 (7): 146-149.  doi:10.11896/j.issn.1002-137X.2015.07.032
摘要 ( 125 )   PDF(302KB) ( 391 )   
参考文献 | 相关文章 | 多维度评价
研究者发现许多真实网络中存在分形特征,并广泛认为网络的异配性导致了分形性。因此,具有同配性的社交网络的分形特征很少被研究。针对开源合作平台中存在许多大型项目的开发者之间未必有实际的合作关系的现象,引入了边的权重来移除弱连接的边。通过重整化群分析,发现GitHub网络在移除弱连接的边之后,其网络结构从小世界变化为分形网络。此外,对网络的Pearson相关系数和邻居相关度进行分析后,发现网络具有很强的同配性,验证了之前对分形起源的理论分析。
基于JBPM的服务动态编排及迁移方案
王 勇,常静波,强保华,王玉峰,张学庆
计算机科学. 2015, 42 (7): 150-155.  doi:10.11896/j.issn.1002-137X.2015.07.033
摘要 ( 129 )   PDF(463KB) ( 537 )   
参考文献 | 相关文章 | 多维度评价
为了适应复杂环境下动态多变的业务需求,对以服务为核心的流程动态编排和再造提供支持,提出了基于JBPM工作流的流程动态编排与迁移方案,该方案分析了目前工作流在流程编排方面的局限性;结合柔性工作流的特点,给出了流程动态编排的模型,并对流程变更所产生的4类操作做了形式化的描述,通过对流程变更引发的流程进行迁移继而实现接续执行这一问题的研究,提出一种流程迁移算法。最后通过实例和性能测试工具验证了算法的可行性和高效性。
面向网络行为的CDN缓存分配策略
冯 翔 杨 昙 李 松
计算机科学. 2015, 42 (7): 156-161.  doi:10.11896/j.issn.1002-137X.2015.07.034
摘要 ( 130 )   PDF(486KB) ( 293 )   
参考文献 | 相关文章 | 多维度评价
撒谎行为的存在会破坏CDN缓存分配的公平性。 使用博弈论对服务器在缓存分配过程中的自私撒谎行为进行了研究。经分析发现,服务器撒谎行为的本质就是当缓存不足时,额外多申请一定量缓存;而当缓存充足时,则诚实地申请所需缓存量。针对这种撒谎行为,提出了一种公平分配算法,在计算服务器的缓存申请量时,考虑其历史缓存申请量,并根据不同阶段申请量的有效性不同引入年龄因子,(重新)计算得到服务器的当前有效缓存申请量,使得撒谎的服务器与诚实的服务器相比受到更多损失,以此来促使其停止撒谎行为。同时,公平算法还保证了系统的最大吞吐量,并引入了价格机制来保证诚实的服务器得到更高的需求满足度。仿真实验结果表明,公平算法对于上述撒谎行为有很好的改善效果。
基于时间序列的自适应采样机制策略研究
杨明霞,王万良,邵鹏飞
计算机科学. 2015, 42 (7): 162-164.  doi:10.11896/j.issn.1002-137X.2015.07.035
摘要 ( 130 )   PDF(310KB) ( 391 )   
参考文献 | 相关文章 | 多维度评价
在传感器网络中,节点对同一事件采集的数据间存在一定的时空相关性。若有效利用数据相关性,动态调整采样间隔,则能够减少不必要的采样,从而相应地减少采样、计算、传输所耗费的能源,延长网络寿命。采用二次指数平滑法进行预测,参考TCP拥塞控制思想,快速调整采样间隔。实验证明,与普通算法相比,该算法能同时降低错误丢失率和采样率。
基于扰动特征分解和前馈调制的网络波动跳变信号抑制算法
陈卫军,睢 丹
计算机科学. 2015, 42 (7): 165-169.  doi:10.11896/j.issn.1002-137X.2015.07.036
摘要 ( 115 )   PDF(417KB) ( 327 )   
参考文献 | 相关文章 | 多维度评价
在网络切换和数据通信中,会产生一种网络波动下的时频跳变谐振信号,需要对这种网络波动跳变信号进行抑制,以提高网络稳定性。提出一种基于扰动特征分解和前馈调制的网络波动跳变信号抑制算法,构建网络波动跳变信号谐振数学模型,采用射线模型对网络跳变单频脉冲中的波动信号进行传播损失估计,基于多普勒频移算法提取扰动特征,利用混响慢变包络切片把波动跳变信号的能量聚集在扰动方向,在希尔伯特空间上对网络波动跳变信号进行扰动特征分解。设计前馈调制滤波器,实现对网络波跳变信号的前馈调制抑制。仿真结果表明,该算法能有效抑制网络波动跳变中的谐振信号,避免了信息损失,数据传输丢包率得到降低,实时性好,解决了大规模混合组网中启动滞后、服务器负载、颤抖等问题。
基于雾计算的医院信息服务系统
程冬梅,李 志
计算机科学. 2015, 42 (7): 170-173.  doi:10.11896/j.issn.1002-137X.2015.07.037
摘要 ( 152 )   PDF(471KB) ( 255 )   
参考文献 | 相关文章 | 多维度评价
针对移动应用对本地信息的需求和云计算框架在支持移动应用方面的不足,提出了一种基于“智能前端化”思想的雾计算框架。该框架在云计算框架的云服务和移动终端之间扩展一个“雾层”,以便将云服务器上的数据和计算服务更快更经济地提供给移动终端。针对医院场景,设计并研发了能提供就医时相关信息浏览服务、排队时长查询服务和多媒体点播服务等的信息服务系统,并提出了多频段负载均衡接入和基于本地信息融合的排队时长查询两项关键技术。通过真实场景中的测试实验验证了系统的可用性和关键技术的高效性。
基于分数阶Fourier变换的云存储系统重复数据删除算法
徐奕奕,唐培和
计算机科学. 2015, 42 (7): 174-177.  doi:10.11896/j.issn.1002-137X.2015.07.038
摘要 ( 111 )   PDF(671KB) ( 232 )   
参考文献 | 相关文章 | 多维度评价
云存储系统的重复数据作为大量冗余数据的一种,对其有效及时地删除能保证云存储系统的稳定与运行。由于云存储系统中的干扰数据较多,信噪比较低,传统的重删算法会在分数阶Fourier域出现伪峰峰值,不能有效地对重复数据进行检测滤波和删除处理,因此提出一种改进的基于分数阶Fourier变换累积量检测的云存储系统重复数据删除算法。首先分析云存储系统重复数据删除机制体系架构,定义数据存储点的适应度函数,得到云存储节点的系统子集随机概率分布;采用经验约束函数对存储节点中的校验数据块分存,通过分数阶Fourier变换对云存储系统中的幅度调制分量进行残差信号滤波预处理。采用4阶累积量切片后置算子,把每个文件分为若干个块,针对每个文件块进行重删,进行重复数据检测后置滤波处理,实现存储资源上的重复数据检测及其删除。仿真实验表明,该算法能提高集群云存储系统计算资源的利用率,重复数据准确删除率较高,有效避免了数据信息流的干扰特征造成的误删和漏删,性能优越。
信息安全
基于Seal演算的分布式系统安全模型
黄 勇 吴尽昭
计算机科学. 2015, 42 (7): 178-181.  doi:10.11896/j.issn.1002-137X.2015.07.039
摘要 ( 106 )   PDF(338KB) ( 236 )   
参考文献 | 相关文章 | 多维度评价
针对目前分布式计算安全模型存在的不足,以能有效描述位置和移动性的形式化模型Seal演算为工具,将系统安全属性的刻画归结为系统进程在给定计算环境下的位置互模拟等价,提出一种无干扰安全模型,其可以方便地刻画不同的安全性质。为满足实际安全需求,提出了一种可复合的安全属性,并给出了相应的证明。最后,通过实例分析表明了模型的有效性。
基于3D混沌映射和细胞自动机的图像加密方案
李敬医 陈炬桦
计算机科学. 2015, 42 (7): 182-185.  doi:10.11896/j.issn.1002-137X.2015.07.040
摘要 ( 133 )   PDF(388KB) ( 299 )   
参考文献 | 相关文章 | 多维度评价
为设计高效的、加密性能好的图像加密系统,充分结合混沌映射细胞自动机的良好加密性能,提出了一种基于3D混沌映射和2D二阶细胞自动机的图像加密方案。该算法先利用3D混沌映射对图片像素进行置乱,然后利用2D二阶细胞自动机对图像在比特级别进行更进一步的混淆。该算法属于对称密钥加密,具有较大的密钥空间和并行化的加解密过程。实验结果证明,该算法可以在较小的迭代次数内达到良好的加密效果,不会导致密文扩张,且加密结果能够抵御常见的暴力破解攻击、统计分析攻击和差分攻击,具有较高的安全性。
WSN中基于非双线性对的无证书群组密钥协商协议
钱琦锋 程春玲
计算机科学. 2015, 42 (7): 186-190.  doi:10.11896/j.issn.1002-137X.2015.07.041
摘要 ( 142 )   PDF(415KB) ( 342 )   
参考文献 | 相关文章 | 多维度评价
针对无线传感网(Wireless Sensor Network,WSN)群组密钥协商协议计算开销较大的问题,提出一种基于非双线性对的无证书群组密钥协商协议。在系统初始化阶段,协议通过无证书加密体制的密钥生成中心生成节点部分私钥,各个节点依据秘密值与对应的部分密钥相乘产生私钥;在节点认证阶段,协议基于椭圆曲线上的点乘运算提出节点认证机制,利用节点的部分私钥与具有身份信息的临时公钥进行点乘运算来确定节点的身份信息;在生成会话密钥阶段,通过点乘运算生成会话密钥,以降低节点的计算开销。最后,分析了协议的计算开销和通信开销。结果表明,所提出的群组密钥协商协议能保证群组节点通信的安全性,并有效降低群组节点通信的计算开销。
SMS4算法的不可能差分攻击研究
孙翠玲 卫宏儒
计算机科学. 2015, 42 (7): 191-193.  doi:10.11896/j.issn.1002-137X.2015.07.042
摘要 ( 121 )   PDF(299KB) ( 290 )   
参考文献 | 相关文章 | 多维度评价
为研究分组加密算法SMS4抵抗不可能差分攻击的能力,使用了14轮不可能差分路径,给出了相关攻击结果。基于1条14轮不可能差分路径,对16轮和18轮的SMS4算法进行了攻击,改进了关于17轮的SMS4的不可能差分攻击的结果,将数据复杂度降低到O(269.47)。计算结果表明:攻击16轮SMS4算法所需的数据复杂度为O(2103),时间复杂度为O(292);攻击18轮的SMS4算法所需的数据复杂度为O(2104),时间复杂度为O(2123.84)。
基于自动机监控的二维降密策略
金 丽,朱 浩
计算机科学. 2015, 42 (7): 194-199.  doi:10.11896/j.issn.1002-137X.2015.07.043
摘要 ( 77 )   PDF(488KB) ( 216 )   
参考文献 | 相关文章 | 多维度评价
降密策略静态实施机制具有限制性过强的缺陷:它将降密策略语义条件判定为安全的程序排斥在外。为了建立更加宽容的实施机制,基于自动机理论,建立了二维降密策略的动态监控机制。程序执行中的命令事件被抽象为自动机的输入,自动机根据这些输入信息跟踪程序执行过程中的信息流,禁止违反降密策略的程序命令的执行。最后,证明了自动机监控机制的可靠性。
网络安全态势感知中D-S证据理论冲突证据的修正研究
寇 广,汤光明,徐梓椋
计算机科学. 2015, 42 (7): 200-203.  doi:10.11896/j.issn.1002-137X.2015.07.044
摘要 ( 81 )   PDF(334KB) ( 253 )   
参考文献 | 相关文章 | 多维度评价
D-S证据理论是不确定推理的一种重要方法,在许多方面都得到了广泛的应用。针对D-S证据理论在网络安全态势感知的数据融合过程中的应用,就多源数据的证据组合结果与直觉相悖的问题进行深入研究,提出了一种新的解决方案。该方案通过支持度的思想对冲突证据源进行修正以达到解决证据冲突的目的。最后,以网络安全态势感知环境为背景进行数值算例,证明了所提方法的可行性。
一种基于时空混沌系统的彩色图像自适应位级加密算法
柴秀丽,甘志华
计算机科学. 2015, 42 (7): 204-209.  doi:10.11896/j.issn.1002-137X.2015.07.045
摘要 ( 118 )   PDF(1014KB) ( 251 )   
参考文献 | 相关文章 | 多维度评价
基于时空混沌系统,提出了一种新的自适应的在位级进行操作的彩色图像加密策略。首先将原始明文图像转化为R、G、B 3个分量,接着采用自适应方法进行加密,即先用B加密R得到R′,用R′加密G得到G′,用G′加密B得到B′,用B′加密R′得到R″,如此循环一轮即得到加密后的密文图像。加密操作包括置乱和扩散,使用时空混沌系统CML对原始图像在位级进行置乱,然后采用Logistic系统对置乱后的二值图像进行扩散。混沌系统的初始值受明文信息的影响,使得算法对明文敏感。对密钥空间、图像直方图、密钥敏感性、相关性、信息熵、明文敏感性、密码攻击进行的测试和分析,证明了算法的安全性和高效性,其在图像保密通信领域具有巨大的应用潜力。
一种属性可撤销的安全云存储模型
张柄虹,张串绒,焦和平,张欣威
计算机科学. 2015, 42 (7): 210-215.  doi:10.11896/j.issn.1002-137X.2015.07.046
摘要 ( 113 )   PDF(524KB) ( 324 )   
参考文献 | 相关文章 | 多维度评价
针对云存储服务中数据用户权限撤销粒度较粗及现有方案密钥分发计算量大等问题,基于双系统加密的思想,在合数阶双线性群上提出了一种新的细粒度权限撤销的安全云存储模型。数据拥有者同时也作为属性分发机构,保证了对自身数据的绝对控制,确保了在云服务商不可信情况下开放环境中的云端存储数据的安全。从模型架构和属性密钥分发两个方面对模型进行了研究,并用严格的数学方法证明了本方案是适应性安全的。云存储模型的数据访问策略根据实际需要可灵活设置,适用于云存储等开放式环境。
网络隐蔽信道实现机制及检测技术研究
董丽鹏 陈性元 杨英杰 石 旺
计算机科学. 2015, 42 (7): 216-221.  doi:10.11896/j.issn.1002-137X.2015.07.047
摘要 ( 175 )   PDF(870KB) ( 1335 )   
参考文献 | 相关文章 | 多维度评价
网络隐蔽信道利用正常网络协议传递隐蔽信息,能够为木马、间谍软件等恶意通信规避安全检测提供载体。针对现有隐蔽信道数量众多、特征繁杂、检测不便等问题,在分析其通信模型及应用模式的基础上,提出了一种基于实现机制的分类方法,从协议和字段的根本特点出发研究了隐蔽信道的异常特征,分析了现有检测方法及其缺陷,给出了下一步的研究方向。
软件与数据库技术
一种基于故障扩展SysML活动图的安全性验证框架研究
仵志鹏 黄志球 王珊珊 曹德建
计算机科学. 2015, 42 (7): 222-228.  doi:10.11896/j.issn.1002-137X.2015.07.048
摘要 ( 121 )   PDF(855KB) ( 249 )   
参考文献 | 相关文章 | 多维度评价
随着嵌入式系统在能源、交通等安全关键领域的广泛应用,针对嵌入式软件的安全性分析与验证方法一直是学术界和工业界的研究热点之一。使用扩展了故障树语义信息的SysML活动图来统一系统的功能模型与安全需求分析模型,并在保留故障树和SysML活动图两种模型语义描述的基础上,提出了一种基于故障扩展SysML活动图的安全性验证框架,包括:首先利用故障树最小割集提取故障信息并给出故障树逻辑门的转换规则;然后给出故障扩展SysML活动图的构建步骤;最后使用Promela对故障扩展SysML活动图进行建模,并使用模型检测工具SPIN对其进行分析验证。通过一个燃气灶控制系统验证了此方法的有效性。
SIMD向量指令的非满载使用方法研究
徐金龙 赵荣彩 赵 博
计算机科学. 2015, 42 (7): 229-233.  doi:10.11896/j.issn.1002-137X.2015.07.049
摘要 ( 129 )   PDF(927KB) ( 304 )   
参考文献 | 相关文章 | 多维度评价
大规模SIMD体系结构提供了更强的向量并行硬件支持,但是,大量迭代次数不足的循环由于不能提供足够的并行性,难以用等价的向量方式实现。为了更有效地利用SIMD,提出了一种非满载地使用SIMD指令的向量化方法。研究了向量寄存器的使用方式,基于非满载的向量寄存器使用方式实现了非满载的向量操作和短循环的向量化,并将非满载的向量化方法用于一般循环的向量化。提供了收益分析方法来为本向量化方法作精确指导。实验结果表明了该方法的有效性,所选测试用例的目标循环被向量化,平均加速比达到1.2。
基于关键词的RDF数据图查询模型研究
郑志蕴 刘 博 李 伦 王振飞
计算机科学. 2015, 42 (7): 234-239.  doi:10.11896/j.issn.1002-137X.2015.07.050
摘要 ( 114 )   PDF(569KB) ( 303 )   
参考文献 | 相关文章 | 多维度评价
随着语义网数据的海量涌现,人们更加关注RDF图的数据查询效率,通过关键词匹配直接查询RDF数据图成为一个研究热点。针对关键词查询中普遍存在的结果冗余与偏离等问题,提出了一种基于关键词的RDF数据图查询模型。该模型首先采用提出的基于迭代的图查询算法(ISGR)对所查询关键词进行子图匹配,得到唯一且最大的结果子图集合;然后根据关键词图与结果子图之间的结构信息,利用统计语言模型,给出了一种结果子图排序方法(SimLM)。对比实验表明,提出的查询模型及排序方法在一致性和相关性方面的性能优于传统模型。
基于地理时间意图和偏好的个性化Web搜索框架GTWSearch
杨 丹,申德荣,陈 默
计算机科学. 2015, 42 (7): 240-244.  doi:10.11896/j.issn.1002-137X.2015.07.051
摘要 ( 137 )   PDF(430KB) ( 292 )   
参考文献 | 相关文章 | 多维度评价
基于Web查询的地理位置、时间查询意图和用户偏好的个性化Web搜索可以改善Web搜索结果,更好地满足不同用户的信息需求。提出了GT-WSearch个性化Web搜索框架,它通过挖掘搜索结果、用户点击数据和对查询进行分析得到的用户概貌和查询概貌,来捕捉用户的地理-时间的意图和偏好,提高搜索质量。用户概貌表明了查询自身的地理-时间的特性。 GT-WSearch框架在排序函数中利用文档的地理位置、时间的相关度来进行个性化搜索。 最后将使用线性的相关度排序函数进行重新排序的搜索结果返回给用户。大量实验结果表明,所提出的个性化方法在提高Web搜索结果的质量中取得了明显的效果。
人工智能
时空域深度卷积神经网络及其在行为识别上的应用
刘 琮 许维胜 吴启迪
计算机科学. 2015, 42 (7): 245-249.  doi:10.11896/j.issn.1002-137X.2015.07.052
摘要 ( 115 )   PDF(960KB) ( 516 )   
参考文献 | 相关文章 | 多维度评价
近年来深度卷积神经网络在静态图像识别上取得了较大进展,但在行为视频上建模运动信息的能力较弱。但是,运动信息是行为识别区别于静态图像识别的关键。基于滤波器响应积提出了时空域深度卷积神经网络。该网络先将相邻帧对应的卷积核分为两组,近似地形成傅里叶基函数对,后续的乘法层将不同帧产生的响应两两相乘后再输入加法层求和,从而将相邻帧映射到变换矩阵的特征值对应的不变子空间上,依靠相邻帧在不变子空间上的旋转角度检测它们之间的运动特征。理论分析证明,网络既对运动敏感,又对内容敏感。实验表明,该网络能对行为视频做出更准确的分类,并与近年出现的其他6种算法进行比较,结果体现了本算法的优越性。
两种基于树结构的基因选择算法
谢倩倩,李订芳,章 文
计算机科学. 2015, 42 (7): 250-253.  doi:10.11896/j.issn.1002-137X.2015.07.053
摘要 ( 124 )   PDF(359KB) ( 245 )   
参考文献 | 相关文章 | 多维度评价
癌症诊断是生物信息学领域的重要课题,其中从基因表达数据中选择与癌症相关的基因子集是癌症诊断的关键。随机森林是近年来很热门的算法,它能够评估分类中特征的重要性(该方法简称为PBM)。受此启发,提出了两种基于树结构的基因选择方法FBM和ABM,分别以树结构中特征出现的频率和重要性打分的平均值作为属性重要性的指标。数值实验中,使用提出的方法选取特征子集,并建立随机森林分类器,通过AUC结果评估基因选择的优劣。实验结果表明,当PBM的AUC值不低于0.900时,其在Leukemia数据集上至少需要26个基因,在Colon Cancer数据集上至少需要48个基因。而在仅选取前10 个基因时,FBM和ABM在Leukemia数据集的AUC值均达到0.989,在Colon Cancer数据集的AUC值达到0.900。此外,与其它典型的基因选择方法mRMR和ECRP等相比,提出的方法也有较高的精度,这对癌症的精确诊断和及早治疗具有重要的现实意义。
基于加权核范数最小化的矩阵填充模型
张玮奇,张宏志,左旺孟,崔梦天
计算机科学. 2015, 42 (7): 254-257.  doi:10.11896/j.issn.1002-137X.2015.07.054
摘要 ( 186 )   PDF(385KB) ( 403 )   
参考文献 | 相关文章 | 多维度评价
协同过滤是目前推荐系统最常用的技术之一,相比于传统的推荐技术具有一定优势,但其缺点是受用户对商品评价的稀疏性制约,现阶段一般利用矩阵填充技术来解决这一问题。主要研究了基于低秩的矩阵填充模型,针对原有模型解对所有奇异值用同一值收缩的问题,提出了一种加权核范数最小化模型以提高核范数灵活度,给出了该模型用收缩算子可得到全局最优解的相关定理及证明,同时对模型的另一种形式在求解过程中的迭代收敛性进行了证明。用凸优化主流算法在两种真实数据集上进行的实验表明,改进后的模型一定程度上提高了计算速度与准确性。
一种基于拥塞发现的强化学习P2P网络视频点播预取策略
沈项军,姚 银,查正军
计算机科学. 2015, 42 (7): 258-261.  doi:10.11896/j.issn.1002-137X.2015.07.055
摘要 ( 115 )   PDF(408KB) ( 251 )   
参考文献 | 相关文章 | 多维度评价
在P2P(Peer to Peer)网络视频点播中设计合理的视频内容预取策略,可以有效地解决视频观看中出现的缓冲等待时间过长、服务器负载过大等问题。而现有的P2P网络视频预取方法往往考虑了视频内容的发现而忽略了节点本身的状态监控,在网络拥塞发生时存在视频播放观看不佳的情况。提出了一种基于拥塞发现的强化学习P2P网络视频点播预取策略,通过监测节点的拥塞状况以及带宽等参数,采用Q-learning学习算法综合评估网络节点,引导视频预取节点的选择,减少了对网络拥塞节点视频内容的预取。实验结果表明,该方法能提高视频播放流畅性,避免用户在节点发生拥塞时等待时间过长,提高了视频播放效率。
基于蛋白质进化配对的残基间距离约束挖掘方法
王彩霞,吕 强,李海鸥,罗 升
计算机科学. 2015, 42 (7): 262-264.  doi:10.11896/j.issn.1002-137X.2015.07.056
摘要 ( 85 )   PDF(354KB) ( 217 )   
参考文献 | 相关文章 | 多维度评价
蛋白质的进化配对是指在进化过程中残基对之间形成的相对稳定的相互作用。基于已被发现的进化配对,采用机器学习的分类技术,将其转换成残基对之间的距离约束,从而将一种定性的残基对之间的相互作用挖掘为定量的距离约束,这为蛋白质的结构预测提供了新的指导。
基于位置语言模型的中文信息检索系统的研究
陈雅兰,胡小华,涂新辉,何婷婷
计算机科学. 2015, 42 (7): 265-269.  doi:10.11896/j.issn.1002-137X.2015.07.057
摘要 ( 90 )   PDF(450KB) ( 349 )   
参考文献 | 相关文章 | 多维度评价
在大多数现有的检索模型中常常忽略了如下事实:一个文档中匹配到的查询词项的近邻性和打分时所基于的段落检索也可以被用来促进文档的打分。受此启发,提出了基于位置语言模型的中文信息检索系统,首先通过定义位置传播数的概念,为每个位置单独地建立语言模型;然后通过引入KL-divergence检索模型,并结合位置语言模型给每个位置单独打分;最后由多参数打分策略得到文档的最终得分。实验中还重点比较了基于词表和基于二元两种中文索引方法在位置语言模型中的检索效果。在标准NTCIR5、NTCIR6测试集上的实验结果表明,该检索方法在两种索引方式上都显著改善了中文检索系统的性能,并且优于向量空间模型、BM25概率模型、统计语言模型。
基于稳健模糊粗糙集模型的多标记文本分类
张 晶,李德玉,王素格,李 华
计算机科学. 2015, 42 (7): 270-275.  doi:10.11896/j.issn.1002-137X.2015.07.058
摘要 ( 146 )   PDF(494KB) ( 226 )   
参考文献 | 相关文章 | 多维度评价
针对多标记数据的不确定性以及噪声数据的存在,提出了一种新的多标记稳健模糊粗糙分类模型。该模型是处理单标记分类问题的k-mean稳健统计量模糊粗糙分类模型的扩展应用。对于每个待分类数据,首先根据相似性计算方法,得到它们相对于各标记的隶属度;然后根据隶属度定义待分类数据与各标记的相关度;最后为每一组相关度赋予合适的阈值,得到相关的标记集合。在3个标准多标记数据集和1个真实多标记文本数据集上的实验结果表明,对于多标记文本分类问题,所提模型在 6个常用的多标记评测指标上较常用的ML-kNN和rank-SVM多标记学习方法具有更高的准确率。
中文事件时序关系的标注和分类方法
郑 新 李培峰 朱巧明
计算机科学. 2015, 42 (7): 276-279.  doi:10.11896/j.issn.1002-137X.2015.07.059
摘要 ( 171 )   PDF(414KB) ( 1148 )   
参考文献 | 相关文章 | 多维度评价
事件时序关系的研究在问答系统、信息抽取和文本自动摘要等自然语言处理领域起着重要的作用。首先借鉴英文的标注方法,将中文事件的时序关系分为4类,并给出了具体的标注方法。然后给出了一个中文时序关系的分类方法。最后,在标注语料库上测试了中文事件时序关系分类的性能,结果表明该方法优于规则方法。
基于稀疏约束的半监督非负矩阵分解算法
胡学考,孙福明,李豪杰
计算机科学. 2015, 42 (7): 280-284.  doi:10.11896/j.issn.1002-137X.2015.07.060
摘要 ( 268 )   PDF(997KB) ( 427 )   
参考文献 | 相关文章 | 多维度评价
矩阵分解因可以实现大规模数据处理而具有十分广泛的应用。非负矩阵分解(Nonnegative Matrix Factorization,NMF)是一种在约束矩阵元素为非负的条件下进行的分解方法。利用少量已知样本的标注信息和大量未标注样本,并施加稀疏性约束,构造了一种新的算法——基于稀疏约束的半监督非负矩阵分解算法。推导了其有效的更新算法,并证明了该算法的收敛性。在常见的人脸数据库上进行了验证,实验结果表明CNMFS算法相对于NMF和CNMF等算法具有较好的稀疏性和聚类精度。
缺失数据数据集的组增量式特征选择
王 锋 魏 巍
计算机科学. 2015, 42 (7): 285-290.  doi:10.11896/j.issn.1002-137X.2015.07.061
摘要 ( 158 )   PDF(460KB) ( 260 )   
参考文献 | 相关文章 | 多维度评价
实际应用中获取到的数据集通常是动态增加的,且随着数据获取工具的迅速发展,新数据通常会一组一组地增加。为此,针对含有缺失数据的动态数据集,基于粗糙集理论,提出了一种组增量式的粗糙特征选择算法。首先分析、证明了信息熵的组增量计算公式,并以信息熵作为特征重要度的度量,在此基础上设计了基于信息熵的可有效处理含有缺失数据的动态数据集的组增量式特征选择算法。实验结果进一步证明了新算法的可行性和高效性。
基于贝叶斯模型的复句关系词自动识别与规则挖掘
杨进才 郭凯凯 沈显君 胡金柱
计算机科学. 2015, 42 (7): 291-294.  doi:10.11896/j.issn.1002-137X.2015.07.062
摘要 ( 115 )   PDF(417KB) ( 310 )   
参考文献 | 相关文章 | 多维度评价
复句是汉语语法的重要实体单位,关系词的自动识别是复句标识的基础,对复句的标识以及篇章的研究有重要意义。在对汉语复句语料库进行广泛分析的基础上,从复句关系词所在的环境和关系词的组合搭配方面进行特征的提取,对提取的特征进行形式化描述。采用互信息和信息增益相结合的方式进行特征选择以及冗余特征的消除;使用贝叶斯模型对特征集合进行训练和测试;将基于统计过程的结果转化为规则,形成规则库,并根据规则进行关系词自动识别。实验结果显示,本方法获得了较高的识别正确率,具有可行性和有效性。
基于云网格集成调度的防拥堵车辆路径规划算法
薛 明 许德刚
计算机科学. 2015, 42 (7): 295-299.  doi:10.11896/j.issn.1002-137X.2015.07.063
摘要 ( 105 )   PDF(946KB) ( 307 )   
参考文献 | 相关文章 | 多维度评价
在道路交通路网中,车辆拥堵问题是流量与路网结构之间相互作用的一个复杂动态过程,通过车辆路径规划,实现对路网网格集成调度,从而提高路网通行吞吐量。传统方法采用并行微观交通动态负载平衡预测算法实现车辆拥堵调度和车辆路径规划,不能准确判断路面上的车辆密度,路径规划效益不好。提出一种基于云网格集成调度的防拥堵车辆路径规划算法,即构建基于Small-World模型的云网格路网模型,采用RFID标签信息进行路况信息采集,实现交通网络拥堵评估信息特征的提取,采用固有模态函数加权平均求得各车道的车辆拥塞状态函数,对所有车道内车辆密度取统计平均可获得簇内的车辆密度。设计交通路网拥堵检测算法来对当前个体道路信息进行一维邻域搜索,从而实现车辆路径规划控制目标函数最佳寻优。通过动态博弈的方式求得车辆防拥堵路径的近似最优轨迹,实现路径规划算法的改进。仿真结果表明,该算法能准确规划车辆路径,实现最优路径控制,从而提高严重拥堵路段的车流速度和路网吞吐性能,性能优越。
图形图像与模式识别
面向连续叠写的高精简中文手写识别方法研究
苏统华,戴洪良,张 健,马培军,邓胜春
计算机科学. 2015, 42 (7): 300-304.  doi:10.11896/j.issn.1002-137X.2015.07.064
摘要 ( 162 )   PDF(681KB) ( 402 )   
参考文献 | 相关文章 | 多维度评价
连续手写识别是中文手写输入技术的核心,自然、快捷地输入中文信息一直是模式识别乃至人工智能领域追求的目标。提出了一种有效克服小屏幕限制的连续叠写汉字识别方法。该方法基于切分-识别集成的解码框架,先使用过切分算法处理输入的书写轨迹;然后启用一种新颖的感知机算法判定字符的边界;随后采用来自字符分类模型、几何模型和语言模型的多种上下文信息进行路径解码。为适应不同类型的移动终端,特别提出了一种高效压缩字符分类模型的方法,以有效减少字符识别过程对存储和内存的占用。该识别方法已在Android平台上部署,并进行了大规模的测试实验。实验结果证实了该识别方法的性能和效率。
软组合概率神经网络分类器人脸识别方法
翟俊海 赵文秀
计算机科学. 2015, 42 (7): 305-308.  doi:10.11896/j.issn.1002-137X.2015.07.065
摘要 ( 85 )   PDF(314KB) ( 224 )   
参考文献 | 相关文章 | 多维度评价
概率神经网络分类器具有学习速度快、易于实现的特点,而且其输出是后验概率, 使得分类器的软组合变得容易。利用概率神经网络的这些特点,提出了软组合概率神经网络分类器人脸识别方法,该方法包括3步:(1)对人脸图像做不完全小波包分解;(2)用包含低频成分的小波子空间图像训练概率神经网络分类器;(3)用模糊积分组合训练好的分类器。将该方法与3种基于矩阵子空间的人脸识别方法在JAFFE、YALE、ORL和FERET 4个人脸数据库上进行了实验比较,结果表明,提出的方法在识别精度和CPU时间两方面均优于其他3种方法。
基于SC-AdaBoost的图像目标检测
张朝晖,刘永霞,雷 倩
计算机科学. 2015, 42 (7): 309-313.  doi:10.11896/j.issn.1002-137X.2015.07.066
摘要 ( 83 )   PDF(447KB) ( 249 )   
参考文献 | 相关文章 | 多维度评价
基于AdaBoost分类器的图像/视频目标检测系统具有检测精度高、检测速度快的特点,但当训练样本数目多、样本描述的特征维数高时,分类器的训练过程将会异常缓慢。为有效改善分类器训练的时间性能,从限制弱分类器训练样本规模的角度,提出了一种改进的boosting分类器训练模型,即基于SC-AdaBoost的分类器训练模型。基于VOC2006数据集的车辆检测实验表明,在不损失分类器检测性能的前提下,SC-AdaBoost训练模型可明显减少分类器的训练时间。
图像引导的二阶总广义变分稀疏深度图的稠密重构
吴少群 袁红星 安 鹏 程培红
计算机科学. 2015, 42 (7): 314-319.  doi:10.11896/j.issn.1002-137X.2015.07.067
摘要 ( 99 )   PDF(954KB) ( 263 )   
参考文献 | 相关文章 | 多维度评价
利用图像颜色信息进行深度图重构,可以恢复对象边界处的深度不连续性,但无法保证对象内部的深度均匀性。为解决该问题,提出图像引导下总广义变分正则化的深度图重构模型。该模型利用扩散张量将图像提供的边缘信息引入二阶总广义变分正则项,使得重构深度在保持对象边缘的同时逼近分段仿射平面,从而保证恢复深度既保持对象边界处的不连续性,又具有对象内部的均匀性。通过Legendre-Fenchel变换将模型转换成等效的凸凹鞍点问题,从而得到高效的一阶原始对偶求解算法。实验结果表明,该方法能够恢复尖锐的对象边缘,同时保持对象内部的深度均匀性。与现有算法相比,所提方法具有更高的峰值信噪比、归一化互协方差和更低的平均绝对误差。