软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2017年第02期杂志 文档列表

软件学报杂志算法设计与分析

求解随机时变背包问题的精确算法与进化算法185-202

摘要：随机时变背包问题（randomized time-varying knapsack problem,简称RTVKP）是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.

文件比较算法fcomp在Isabelle/HOL中的验证203-215

摘要：基于机器定理证明的形式验证技术不受状态空间限制,是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法.文件比较算法（file comparison algorithm）是一类成员众多,应用极为广泛,跨越生物信息学、情报检索、网络安全等多个应用领域的基础算法.在交互式定理证明器Isabelle/HOL中对Miller和Myers在1985年提出的基于行的文件比较算法fcomp做了形式化,改正了算法关于边界变量迭代的一个小错误,证明了改正后算法的可终止性和正确性;对算法时间复杂性做了完全形式化的分析,印证了算法的非形式化分析结论,为今后更多文件比较算法的形式验证提供了可供借鉴的经验.

软件学报杂志模式识别与人工智能

描述逻辑εL的二阶线性推理机制216-233

摘要：基于描述逻辑的本体的保守扩充理论、模块抽取理论、通用模块构建理论及其相关算法是本体工程中本体构建、本体融合及重构的核心理论与工具.国际上该领域已有Lutz等人使用形式构模方法证明了ALC的保守扩充判定算法复杂度是二阶时间指数的,而轻量级的系统？L的算法复杂度是一阶时间指数的.但当前文献中的形式构模方法思路复杂,难以把握,几乎不能在实用的工程层面上实现.提出一种面向轻量级的描述逻辑系统家族（DL-Lite family）的统一的二阶线性推理机制,并给出该推理机制的完备性证明.该方法直观,思路清晰,从而在工程中容易实现.同时,该方法对εL,FL0,FLε,v L等DL-Lite家族的所有系统都有效.在该线序推理系统下,可以根据＂空间换时间＂的原则,设计和实现关于保守扩充判定的图推理机制,其复杂性（相对于空间的大小）是多项式的.

一种面向问卷图像的版面分析算法234-245

摘要：针对目前已有的问卷图像版面分析算法无法自动识别信息填写区域和无法处理无固定格式的问卷图像等问题,提出了一种连通区域和神经网络相结合的问卷图像版面分析算法.首先获得扫描得到的问卷图像的中心有效图形,接着提出并应用了一种针对问卷图像的快速倾斜矫正方法,对中心有效图像进行倾斜矫正;再利用水平投影进行行分割得到问卷行;然后提取每个问卷行的首个连通区域判断是否存在表格区域即表格问卷行,若存在表格问卷行,则对其进行表格区域分布分析和表格类型判断,得到可能的答案区域,否则直接对文本问卷行进行分析,得到可能的答案区域;最后利用神经网络判断筛选区域的类型,得到最终的答案填写区域.针对问卷图像的实验结果表明,该算法可以准确地识别各种问卷图像中的信息填写区域.

基于动态主题模型融合多维数据的微博社区发现算法246-261

摘要：随着微博用户的不断增加,微博网络已成为用户进行信息交流的平台.针对由于博文长度受限,传统的社区发现算法无法有效解决微博网络的稀疏性等问题,提出了DC-DTM（discovery community by dynamic topic model）算法.DC-DTM算法首先将微博网络映射为有向加权网络,网络中边的方向反映节点之间的关注关系,利用所提出的DTM（dynamic topic model）计算出节点之间的语义相似度,并将其作为节点间连边的权重.DTM是一种微博主题模型.该模型不仅能够挖掘博客的主题分布,而且能够计算出某一主题中用户的影响力大小.其次,利用所提出的复杂度较低的标签传播算法WLPA（weighted lebel propagation）进行微博网络的社区发现.该算法的初始化阶段将影响力大的用户节点作为初始节点,标签按照节点的影响力从大到小进行传播,避免了传统标签传播算法逆流现象的发生,提高了标签传播算法的稳定性.真实数据上的实验结果表明,DTM模型能够很好地对微博进行主题挖掘,DC-DTM算法能够有效地挖掘出微博网络的社区.

软件学报杂志数据库技术

无监督的中文商品属性结构化方法262-277

摘要：从非结构化商品描述文本中抽取结构化属性信息,对于电子商务实现商品的对比与推荐及用户需求预测等功能具有重要意义.现有结构化方法大多采用监督或半监督的分类方法抽取属性值与属性名,通过文法分析器分析属性值与属性名之间的文法依存关系,并根据关联规则实现属性值与属性名的匹配.这些方法存在以下不足：（1）需要人工标记部分属性值、属性名及它们之间的对应关系;（2）属性值-属性名匹配的准确度受到语言习惯、句意逻辑、语料库及属性名候选集质量的严重制约.提出了一种无监督的中文商品属性结构化方法.该方法借助搜索引擎,基于小概率事件原理分析文法关系来抽取属性值与属性名.同时,提出相对不选取条件概率场,并使用Page Rank算法来计算属性值与属性名的配对概率.该方法无需人工标记的开销,且无论商品描述中是否显式地包含相应的属性名,该方法都能自动抽取到属性值并匹配相应的属性名.使用百度搜索引擎上的真实语料,针对4类商品的中文描述进行了实验.实验结果验证了对于候选属性名的自动生成,所提出的基于搜索引擎搜索属性值,并在包含属性值的搜索结果中抽取一般名词的候选属性名生成方法与只在描述句中抽取一般名词的候选属性名生成方法相比,查全率提高了20%以上;对于非量化类属性,所提出的基于相对不选取条件概率场的属性值-属性名匹配方法与基于依存关联的方法相比,Rank-1的准确率提高了30%以上,平均MRR提高了0.3以上.

基于背景和内容的微博用户兴趣挖掘278-291

摘要：微博用户兴趣挖掘是个性化推荐、社群划分的基础工作.在深入分析微博网络特点的基础上,给出了能够揭示微博网络多模性的描述模型,对面向微博网络的后续研究具有参考价值.根据微博网络的特点,提出了基于背景的用户静态兴趣表示及挖掘方法,以及基于微博的用户动态兴趣表示和挖掘方法.针对微博网络中缺少背景信息、发表微博很少的大量不活跃用户,提出了基于关注的用户兴趣挖掘方法.以新浪微博为例,选取了时尚、企业管理、教育、军事、文化这5个领域进行用户兴趣挖掘及相似度计算的实验分析和比较,结果表明,与主流的兴趣挖掘方法相比,该微博用户兴趣的表示和挖掘方法可以有效地改善微博用户兴趣挖掘的效果.

基于弱匹配概率典型相关性分析的图像自动标注292-309

摘要：针对弱匹配多模态数据的相关性建模问题,提出了一种弱匹配概率典型相关性分析模型（semi-paired probabilistic CCA,简称Semi PCCA）.Semi PCCA模型关注于各模态内部的全局结构,模型参数的估计受到了未匹配样本的影响,而未匹配样本则揭示了各模态样本空间的全局结构.在人工弱匹配多模态数据集上的实验结果表明,Semi PCCA可以有效地解决传统CCA（canonical correlation analysis）和PCCA（probabilistic CCA）在匹配样本不足的情况下出现的过拟合问题,取得了较好的效果.提出了一种基于Semi PCCA的图像自动标注方法.该方法基于关联建模的思想,同时使用标注图像及其关键词和未标注图像学习视觉模态和文本模态之间的关联,从而能够更准确地对未知图像进行标注.

一种针对反向空间偏好top-k查询的高效处理方法310-325

摘要：随着地理位置定位技术的蓬勃发展,基于在线位置服务技术的应用也越来越多.提出一种查询类型——反向空间偏好top-k查询.类似于传统的反向空间top-k查询,对于给定的空间查询对象,该查询返回使该对象满足top-k属性得分的那些用户.但不同的是,该对象的属性不是自身具有的特性,而是通过计算该对象与其他偏好对象之间的空间关系（如距离）而确定.这种查询在市场分析等许多重要领域具有需求,例如,根据查询结果,分析出某个地区中某个设施受欢迎的程度.但是,由于大量空间对象的存在导致对象之间空间关系的计算代价非常高,如何实时地计算出对象的空间属性得分,给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括：数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证,证明了所提出方法的有效性.与普通方法相比,这些方法能够大幅度提高查询处理的执行时间和I/O效率.

基于重叠社区搜索的传播热点选择方法326-340

摘要：随着社交网络的蓬勃发展,信息传播问题由于具有广泛的应用前景而受到广泛关注,影响力最大化问题是信息传播中的一个研究热点.它致力于在信息传播过程开始之前选取能够使预期影响力达到最大的节点作为信息传播的初始节点,并且大多采用基于概率的模型,如独立级联模型等.然而,现有的影响力最大化解决方案大多认为信息传播过程是自动的,忽略了社交网站平台在信息传播过程中可以起到的作用.此外,基于概率的模型存在一些问题,如无法保障信息的有效传播、无法适应动态变化的网络结构等.因此,提出了一种基于重叠社区搜索的传播热点选择方法.该方法通过迭代式推广模型根据用户行为反馈逐步选择影响力最大化节点,使社交网站平台在信息传播过程中充分发挥控制作用.提出了一种基于重叠社区结构的方法来衡量节点影响力,根据这种衡量方式来选择传播热点.提出了解决该问题的两种精确算法（包括一种基本方法和一种优化方法）以及该问题的近似算法.通过大量实验验证了精确及近似算法的效率、近似算法的准确率以及迭代式传播热点选择方法的有效性.

软件学报杂志计算机网络与信息安全

面向表数据隐私保护的贪心聚类匿名方法341-351

摘要：为了防范隐私泄露,表数据一般需要匿名处理后.现有匿名方案较少分类考察准标识属性概化,并缺少同时考虑信息损失量和时间效率的最优化.利用贪心法和聚类划分的思想,提出一种贪心聚类匿名方法：分类概化准标识属性,并分别度量其信息损失,有利于减小并合理评价信息损失.对元组间距离和元组与等价类距离,建立与最小合并概化信息损失值正相关的距离定义,聚类过程始终选取具有最小距离值的元组添加,从而保证信息损失总量趋于最小.按照k值控制逐一聚类,实现等价类均衡划分,减少了距离计算总量,节省了运行时间.实验结果表明,该方法在减少信息损失和运行时间方面是有效的.

Cut-and-Choose双向不经意传输352-360

摘要：不经意传输作为现代密码学的一个基本工具,在安全协议的研究中起着重要作用.近年来,许多功能性更强的不经意传输变种被提出来,以适应不同的需求和环境.提出一个不经意传输变种,称为cut-and-choose双向不经意传输.基于同态加密给出该原语的一轮高效协议构造,且在半诚实模型下形式化证明了该协议的安全性.将cut-and-choose双向不经意传输运用到基于cut-and-choose技术的安全协议（尤其是安全两方计算）中,可以更具模块化地描述协议高层框架,降低协议交互轮数.此外,作为信息安全领域的一个底层基本工具,该原语本身也具有独立的研究意义.

一种随机剔除点的安卓图形解锁方案361-371

摘要：安卓图形解锁（Android unlock pattern,简称AUP）作为目前移动终端上使用最广泛的图形密码方案,实际应用的密码在理论空间上分布很不均匀,导致其实际安全性远低于理论安全性,所暴露出的巨大安全隐患极易被攻击者利用以加快字典攻击与暴力破解的速度.提出一种随机剔除点的安卓图形解锁方案（Android-unlock-pattern scheme through random points exclusion,简称AUP-RPE）.在设置密码阶段通过对原界面作一系列改动以规避用户具有安全隐患的使用习惯,并组织了1 100余人次的用户测试以收集实际应用的图形密码.建模分析发现,在保证与AUP相近的可用性前提下,AUP-RPE的安全性提高了3个以上数量级,证明了该方案具有更高的安全性.

明文编码随机化加密方案372-383

摘要：对著名的最优非对称填充加密方案（RSA-OAEP）及其改进方案进行分析发现：（1）这些方案的明文填充机制均采用Hash函数来隐藏明文统计特性,然而Hash函数特有的属性导致RSA-OAEP及其改进方案的安全性证明难以在标准模型下进行.很多研究工作表明,在标准模型下假定RSA（或者其变形）是困难的,无法证明RSA-OAEP及其改进方案对自适应性选择密文攻击是安全性的;（2）这些方案加密的消息是明文填充随机化处理后的信息,因此被加密信息比实际明文多出k位（设用于填充的随机数为k位）.针对这两个问题,构造了一个基于配对函数编码的RSA型加密方案.该方案具有如下属性：（1）无需Hash运算就可以隐藏明文统计特性,同时使得被加密消息的长度短于实际明文的长度;（2）在标准模型下对自适应选择密文攻击是安全的;（3）该方案应用于签密时不需要额外协商签名模与加密模的大小顺序.

一种基于主动学习的恶意代码检测方法384-397

摘要：现有恶意代码的检测往往依赖于对足够数量样本的分析.然而新型恶意代码大量涌现,其出现之初,样本数量有限,现有方法无法迅速检测出新型恶意代码及其变种.在数据流依赖网络中分析进程访问行为异常度与相似度,引入了恶意代码检测估计风险,并提出一种通过最小化估计风险实现主动学习的恶意代码检测方法.该方法只需要很少比例的训练样本即可实现准确的恶意代码检测,比现有方法更适用于新型恶意代码检测.通过对真实的8 340个正常进程和7 257个恶意代码进程的实验分析,与传统基于统计分类器的检测方法相比,该方法明显地提升了恶意代码检测效果.即便在训练样本仅为总体样本数量1%的情况下,该方法也可以达到5.55%的错误率水平,比传统方法降低了36.5%.

软件学报杂志操作系统

一种灵活高效的虚拟CPU调度算法398-410

摘要：目前,虚拟化已经广泛应用于数据中心,但主流的虚拟CPU调度策略并没有实现对I/O性能的保障,尤其是当延时敏感型负载的虚拟机和计算敏感型负载的虚拟机竞争CPU资源时,其性能显著下降.针对上述问题,提出了一种灵活、高效的虚拟CPU调度算法FLMS（flexible I/O latency and multi-processor sensitive scheduler）.FLMS通过采用虚拟机分类、虚拟CPU绑定、多类时间片等技术降低了虚拟机的响应延时,同时基于多处理器架构重新设计了负载均衡策略,优化了虚拟CPU迁移.FLMS通用于目前主流的虚拟化方案,在软件虚拟化方式下,与最新的优化方案相比,延时降低了30%,带宽有10%的提升;在使用硬件辅助虚拟化的系统中,通过FLMS能够获得接近原生系统的I/O性能,并且保证了整个系统的公平性.

偶发实时系统可调度性分析问题的整数规划方法411-428

摘要：偶发实时任务最早截止期优先（earliest deadline first,简称EDF）可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法（pseudo-polynomail time decision algorithm,简称PTDA）均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U〉0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10~4倍.

基于模型预测控制的数据中心节能调度算法429-442

摘要：如今日益增长的数据中心能耗,特别是冷却系统能耗已日益受到重视,降低系统能耗能够减少数据中心碳排放.提出了一种基于模型预测控制（model prediction control,简称MPC）的节能调度策略,该策略可以有效地减小数据中心冷却能耗.该方法采用动态电压频率调节技术来调整计算节点频率,从而减少节点间的热循环;所有节点的峰值温度可被保持在温度阈值下,在任务的执行中稳态误差较小.该方法可以通过动态频率调节来抑制由于负载类型变化造成的模型不确定性带来的内部扰动,分析结果表明,基于模型预测的温控算法系统开销较小,具有良好的可扩展性.基于该算法设计的控制器能够有效地降低输入温度,提高数据中心能耗效率.通过在实际数据中心内运行的模拟网上书店,该方法与安全最小热传递算法和传统反馈温控算法这两种经典方法相比,无论是在正常条件下还是在扰动存在的情况下都能取得较好的温度抑制效果,系统性能如吞吐率也达到最大.在相同的负载条件下,该方法能够获得最小的输入峰值温度和最小的冷却能耗.