2012年 第49卷 第4期
摘要：
为方便P2P网络的内容投递,Kademlia协议作为一个鲁棒性强的分布式Hash表协议,被BitTorrent和eMule等P2P文件共享应用部署.在此,将这些被部署的基于Kademlia协议的网络称为K网络.K网络中每个节点拥有唯一的IP地址(或ID)是至关重要的,因为K网络中的“节点查询”和“资源搜索”都依赖于此.然而,据分析发现,K网络中相当一部分节点存在IP重复与ID别名.为深入理解IP重复与ID别名的分布特征,提出了几个度量IP重复与ID别名的测度.基于这些测度和Rainbow采集器,对K网络中的IP重复与ID别名进行了测量,发现了许多有助于P2P网络挖掘研究的IP重复与ID别名特征.
为方便P2P网络的内容投递,Kademlia协议作为一个鲁棒性强的分布式Hash表协议,被BitTorrent和eMule等P2P文件共享应用部署.在此,将这些被部署的基于Kademlia协议的网络称为K网络.K网络中每个节点拥有唯一的IP地址(或ID)是至关重要的,因为K网络中的“节点查询”和“资源搜索”都依赖于此.然而,据分析发现,K网络中相当一部分节点存在IP重复与ID别名.为深入理解IP重复与ID别名的分布特征,提出了几个度量IP重复与ID别名的测度.基于这些测度和Rainbow采集器,对K网络中的IP重复与ID别名进行了测量,发现了许多有助于P2P网络挖掘研究的IP重复与ID别名特征.
摘要：
随着移动通信和Web技术的不断突破,以微博为代表的在线社会网络在中国广泛发展起来,越来越多的人开始使用微博进行信息分发和舆论传播.为了了解中国微博网络中的拓扑结构特征和用户行为特征等内在信息,对国内最大的微博系统——新浪微博——开展了主动测量,并结合已有的在线社会网络测量结果,对新浪微博的网络拓扑和用户行为特征进行了分析和比较.主要发现包括:1)新浪微博网络具有小世界特性;2)新浪微博网络的入度分布属于幂次分布,而出度分布表现为某种分段幂率函数;3)与类似社会网络相比,新浪微博网络的出入度不具有相关性;4)新浪微博网络属于同配网络;5)新浪微博用户发博时间具有明显的日分布和周分布模式;6)新浪微博用户博文数目分布表现为威布尔分布;7)新浪微博用户博文的转发和评价行为具有很强的相关性,且博文转发概率要高于评价概率.这些测量研究和发现不仅有助于设计出符合中国微博网络结构特征的数学模型和计算模型,也是实现对微博舆论的监测、引导、控制等方面的重要依据和基础.
随着移动通信和Web技术的不断突破,以微博为代表的在线社会网络在中国广泛发展起来,越来越多的人开始使用微博进行信息分发和舆论传播.为了了解中国微博网络中的拓扑结构特征和用户行为特征等内在信息,对国内最大的微博系统——新浪微博——开展了主动测量,并结合已有的在线社会网络测量结果,对新浪微博的网络拓扑和用户行为特征进行了分析和比较.主要发现包括:1)新浪微博网络具有小世界特性;2)新浪微博网络的入度分布属于幂次分布,而出度分布表现为某种分段幂率函数;3)与类似社会网络相比,新浪微博网络的出入度不具有相关性;4)新浪微博网络属于同配网络;5)新浪微博用户发博时间具有明显的日分布和周分布模式;6)新浪微博用户博文数目分布表现为威布尔分布;7)新浪微博用户博文的转发和评价行为具有很强的相关性,且博文转发概率要高于评价概率.这些测量研究和发现不仅有助于设计出符合中国微博网络结构特征的数学模型和计算模型,也是实现对微博舆论的监测、引导、控制等方面的重要依据和基础.
摘要：
针对传统摆渡路由中使者调度和协作的问题,设计一种交叉区域的多使者摆渡路由协议.将网络划分成若干横向区域和纵向区域,每个区域内存在一个使者轮询节点.通过单个使者或一个横向区域使者与一个纵向区域使者的协作实现数据的传递.从理论上分析了提出协议的期望延时,并从延时和容错性两个方面对协议进行了改善.仿真评估结果表明,交叉区域摆渡路由在平衡网络负载和端到端的延时的同时,具有单一使者的容错能力,是一种合理有效的多使者调度方法.
针对传统摆渡路由中使者调度和协作的问题,设计一种交叉区域的多使者摆渡路由协议.将网络划分成若干横向区域和纵向区域,每个区域内存在一个使者轮询节点.通过单个使者或一个横向区域使者与一个纵向区域使者的协作实现数据的传递.从理论上分析了提出协议的期望延时,并从延时和容错性两个方面对协议进行了改善.仿真评估结果表明,交叉区域摆渡路由在平衡网络负载和端到端的延时的同时,具有单一使者的容错能力,是一种合理有效的多使者调度方法.
摘要：
针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性，分析了骨干网路由表前缀重叠特征，提出了一种基于阈值的IP路由缓存方法，该方法结合了地址缓存和前缀缓存技术，无需进行前缀扩展，克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题，在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势；仿真实验表明对于路由条目超过260 000的路由表，缓存空间大小为30 000，选择阈值K=4时97%以上的节点可实现1∶1缓存，其余节点采用地址缓存，缓存失效率小于0.02，可以用小的缓存空间实现高速线速转发.
针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性，分析了骨干网路由表前缀重叠特征，提出了一种基于阈值的IP路由缓存方法，该方法结合了地址缓存和前缀缓存技术，无需进行前缀扩展，克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题，在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势；仿真实验表明对于路由条目超过260 000的路由表，缓存空间大小为30 000，选择阈值K=4时97%以上的节点可实现1∶1缓存，其余节点采用地址缓存，缓存失效率小于0.02，可以用小的缓存空间实现高速线速转发.
摘要：
复杂网络中各种自组织现象的涌现给网络脆弱性挖掘和网络免疫自推进带来了启示.一个完整的免疫资源配置过程可以分为4个阶段：信息收集、扫描、漏洞修复和自我推进.网络主机脆弱性分布的实证分析表明，脆弱主机在网络中呈现明显的幂律分布特性，这就意味着盲目扫描将耗费大量资源在非脆弱或不存在的主机上，而一个有效的网络免疫策略应该利用这种非均匀的网络脆弱性分布特性.静态偏好性的扫描方法在初期能取得良好的推进效果，但并不能将这种有效性贯穿整个免疫过程.为此，提出了一种新的基于扫描方式的网络免疫自推进策略.该策略能够在不知道网络结构的条件下，通过一种动态适应的偏好扫描方法，高效命中脆弱主机实施免疫修复.经过传播模型推导及计算机仿真分析，设计的网络免疫策略能够很好地抑制危害传播，提高网络的安全性.
复杂网络中各种自组织现象的涌现给网络脆弱性挖掘和网络免疫自推进带来了启示.一个完整的免疫资源配置过程可以分为4个阶段：信息收集、扫描、漏洞修复和自我推进.网络主机脆弱性分布的实证分析表明，脆弱主机在网络中呈现明显的幂律分布特性，这就意味着盲目扫描将耗费大量资源在非脆弱或不存在的主机上，而一个有效的网络免疫策略应该利用这种非均匀的网络脆弱性分布特性.静态偏好性的扫描方法在初期能取得良好的推进效果，但并不能将这种有效性贯穿整个免疫过程.为此，提出了一种新的基于扫描方式的网络免疫自推进策略.该策略能够在不知道网络结构的条件下，通过一种动态适应的偏好扫描方法，高效命中脆弱主机实施免疫修复.经过传播模型推导及计算机仿真分析，设计的网络免疫策略能够很好地抑制危害传播，提高网络的安全性.
摘要：
社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.
社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.
摘要：
针对数据分类问题提出一种新型高效的特征选择和规则提取方法.首先通过减少初始区间数量改进Chi-Merge离散化方法,再采用改进的Chi-Merge离散化连续型特征变量;特征离散化后,统计样本数据在每个特征子集划分下的频数表,并根据频数表计算数据不一致率,再利用顺序前向最优搜索的方法,快速确定特征数量由小到大的每一个最优特征子集;根据特征子集对应的数据不一致率差异最小化原则,完成特征个数最小化的最优特征子集筛选;根据最优特征子集的数据频数表,可直接提取数据分类规则.实验表明,快速提取的规则可获得较好的分类效果.基于该特征选择方法,提出一种面向分布式同构数据的快速分类模型,不但具有良好的分类效果,还支持对样本数据内容的隐私保护.
针对数据分类问题提出一种新型高效的特征选择和规则提取方法.首先通过减少初始区间数量改进Chi-Merge离散化方法,再采用改进的Chi-Merge离散化连续型特征变量;特征离散化后,统计样本数据在每个特征子集划分下的频数表,并根据频数表计算数据不一致率,再利用顺序前向最优搜索的方法,快速确定特征数量由小到大的每一个最优特征子集;根据特征子集对应的数据不一致率差异最小化原则,完成特征个数最小化的最优特征子集筛选;根据最优特征子集的数据频数表,可直接提取数据分类规则.实验表明,快速提取的规则可获得较好的分类效果.基于该特征选择方法,提出一种面向分布式同构数据的快速分类模型,不但具有良好的分类效果,还支持对样本数据内容的隐私保护.
摘要：
核矩阵计算是求解支持向量机的关键，已有精确计算方法难以处理大规模的样本数据.为此，研究核矩阵的近似计算方法.首先，借助支持向量机的凸二次约束线性规划表示，给出支持向量机和多核支持向量机的二阶锥规划表示.然后，综合Monte Carlo方法和不完全Cholesky分解方法，提出一个新的核矩阵近似算法KMA-α，该算法首先对核矩阵进行Monte Carlo随机采样，采样后不直接进行奇异值分解，而是应用具有对称置换的不完全Cholesky分解来计算接近最优的低秩近似.以KMA-α输出的近似核矩阵作为支持向量机的输入，可提高支持向量机二阶锥规划求解的效率.进一步，分析了KMA-α的算法复杂性，证明了KMA-α的近似误差界定理.最后，通过标准数据集上的实验，验证了KMA-α的合理性和计算效率.理论分析与实验结果表明，KMA-α是一合理、有效的核矩阵近似算法.
核矩阵计算是求解支持向量机的关键，已有精确计算方法难以处理大规模的样本数据.为此，研究核矩阵的近似计算方法.首先，借助支持向量机的凸二次约束线性规划表示，给出支持向量机和多核支持向量机的二阶锥规划表示.然后，综合Monte Carlo方法和不完全Cholesky分解方法，提出一个新的核矩阵近似算法KMA-α，该算法首先对核矩阵进行Monte Carlo随机采样，采样后不直接进行奇异值分解，而是应用具有对称置换的不完全Cholesky分解来计算接近最优的低秩近似.以KMA-α输出的近似核矩阵作为支持向量机的输入，可提高支持向量机二阶锥规划求解的效率.进一步，分析了KMA-α的算法复杂性，证明了KMA-α的近似误差界定理.最后，通过标准数据集上的实验，验证了KMA-α的合理性和计算效率.理论分析与实验结果表明，KMA-α是一合理、有效的核矩阵近似算法.
摘要：
CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.
CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.
摘要：
针对FastSLAM 1.0中机器人缺乏自身定位测量修正引起的累积误差和FastSLAM 2.0引入测量修正引起算法复杂度增加的问题，提出一种改进的基于辅助测量的多机器人协作实时FastSLAM算法，使用双机器人协同工作，领头机器人负责完成同时定位与地图构建任务，辅助机器人通过静态相对位置测量为领头机器人提供实时定位测量修正.该辅助测量方法不仅为SLAM任务执行机器人提供较准确的定位测量值，同时也避免了FastSLAM 2.0算法中额外的算法复杂度问题.实验结果表明算法既可以获得较高的精度，而且方便可行，具有较高实用价值.
针对FastSLAM 1.0中机器人缺乏自身定位测量修正引起的累积误差和FastSLAM 2.0引入测量修正引起算法复杂度增加的问题，提出一种改进的基于辅助测量的多机器人协作实时FastSLAM算法，使用双机器人协同工作，领头机器人负责完成同时定位与地图构建任务，辅助机器人通过静态相对位置测量为领头机器人提供实时定位测量修正.该辅助测量方法不仅为SLAM任务执行机器人提供较准确的定位测量值，同时也避免了FastSLAM 2.0算法中额外的算法复杂度问题.实验结果表明算法既可以获得较高的精度，而且方便可行，具有较高实用价值.
摘要：
提出了一种最大向量夹角间隔MAMC分类方法,其核心思想是在样本特征空间中寻找一个尽可能靠近训练样本中心的向量c,进而强化更小的VC维,同时未知样本点可以根据向量c和训练样本点之间的最大向量夹角间隔ρ进行分类.提出的MAMC方法可以通过核化提高算法的灵活性,而在MAMC方法的实现上,只需解决一个对应的二次凸优化问题,实现简单.同时,MAMC的v×v\-1参数属性构成了支持向量个数的下界和错分训练样本数的上界;而其所对应的硬划分版本可以等价于一种特殊和核化的最小包含球,因此能够训练较大样本.最后,人造和真实数据集实验结果表明,MAMC整体上具有较好的性能优势.
提出了一种最大向量夹角间隔MAMC分类方法,其核心思想是在样本特征空间中寻找一个尽可能靠近训练样本中心的向量c,进而强化更小的VC维,同时未知样本点可以根据向量c和训练样本点之间的最大向量夹角间隔ρ进行分类.提出的MAMC方法可以通过核化提高算法的灵活性,而在MAMC方法的实现上,只需解决一个对应的二次凸优化问题,实现简单.同时,MAMC的v×v\-1参数属性构成了支持向量个数的下界和错分训练样本数的上界;而其所对应的硬划分版本可以等价于一种特殊和核化的最小包含球,因此能够训练较大样本.最后,人造和真实数据集实验结果表明,MAMC整体上具有较好的性能优势.
摘要：
提出一种新的人脸描述及识别方法，首先对归一化后的人脸图像进行多方向多尺度Gabor变换；然后对人脸区域进行分块，以块为单位统计Gabor系数的均值和方差，求得块特征矢量(block feature vector, BFV)，按先行后列的顺序将各块的BFV拼接，构成整幅人脸图像特征矢量(face feature vector, FFV).在分类器设计阶段，引入两两比对和投票机制，用多个两类分类器组合成多类分类器.在训练某个具体的两类分类器时，根据隶属训练样本计算FFV中每项的分辨力，以分辨力大小为依据选出最优特征子集(best subset feature vector, BSFV).基于Yale人脸数据集展开实验，与已发表的算法和结果进行对比，证明了该方法的有效性.
提出一种新的人脸描述及识别方法，首先对归一化后的人脸图像进行多方向多尺度Gabor变换；然后对人脸区域进行分块，以块为单位统计Gabor系数的均值和方差，求得块特征矢量(block feature vector, BFV)，按先行后列的顺序将各块的BFV拼接，构成整幅人脸图像特征矢量(face feature vector, FFV).在分类器设计阶段，引入两两比对和投票机制，用多个两类分类器组合成多类分类器.在训练某个具体的两类分类器时，根据隶属训练样本计算FFV中每项的分辨力，以分辨力大小为依据选出最优特征子集(best subset feature vector, BSFV).基于Yale人脸数据集展开实验，与已发表的算法和结果进行对比，证明了该方法的有效性.
摘要：
概率XML文件是概率数据的网络数据交换和表示标准，元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型，定义了概率XML文件树的基本路径和扩展路径，提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法，根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法，并通过实验进行了比较分析.实验结果表明：这两种方法是有效的；与前一种方法比较，后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询，计算过程较简单.
概率XML文件是概率数据的网络数据交换和表示标准，元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型，定义了概率XML文件树的基本路径和扩展路径，提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法，根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法，并通过实验进行了比较分析.实验结果表明：这两种方法是有效的；与前一种方法比较，后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询，计算过程较简单.
摘要：
极区计算对全球数值预报模式设计的重要性主要体现在2个方面：模式动力框架中的极区处理和极区并行数据划分带来的并行负载不平衡问题.其中后者是全球数值预报模式大规模并行计算的性能瓶颈，对此提出一种新的基于加权等积的球面数据划分算法.该算法以球带数目和权函数为参数，将南北两极分别划分到单独的子区域，形成极点通区，使从极点到赤道方向每个纬度对应的子区域数目逐渐增多，灵活地实现球面网格的高质量划分.从理论上分析该算法的划分质量后，以基于球谐谱的浅水波模式PSTSWM为实验平台，验证了提出的划分算法具有很好的并行划分性能以及可扩展性.结合我国自主设计的GRAPES全球模式，展望了该算法的应用前景.
极区计算对全球数值预报模式设计的重要性主要体现在2个方面：模式动力框架中的极区处理和极区并行数据划分带来的并行负载不平衡问题.其中后者是全球数值预报模式大规模并行计算的性能瓶颈，对此提出一种新的基于加权等积的球面数据划分算法.该算法以球带数目和权函数为参数，将南北两极分别划分到单独的子区域，形成极点通区，使从极点到赤道方向每个纬度对应的子区域数目逐渐增多，灵活地实现球面网格的高质量划分.从理论上分析该算法的划分质量后，以基于球谐谱的浅水波模式PSTSWM为实验平台，验证了提出的划分算法具有很好的并行划分性能以及可扩展性.结合我国自主设计的GRAPES全球模式，展望了该算法的应用前景.
摘要：
超平面覆盖问题是计算几何领域中一类典型的NP难问题，在实际生活中有着广泛的应用.针对NP难问题的难解性，人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性，不能满足实际应用中的各种需求，人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征，并利用深度有界搜索树的方法，提出了一个时间复杂度为O(k\+3(0.736k)\+k+n log k)的确定性参数算法，极大地改进了当前最好的结果O((k2.2)\+{2k}+n log k).通过对上述算法在高维空间中的进一步扩展，提出了关于超平面覆盖问题时间复杂度为O(dk\+{d+1}(dk)!/((d!)\+kk!)+n\+{d+1})确定性参数算法，对当前的最好结果O(k\+{d(k+1)}+n\+{d+1})有较大改进.
超平面覆盖问题是计算几何领域中一类典型的NP难问题，在实际生活中有着广泛的应用.针对NP难问题的难解性，人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性，不能满足实际应用中的各种需求，人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征，并利用深度有界搜索树的方法，提出了一个时间复杂度为O(k\+3(0.736k)\+k+n log k)的确定性参数算法，极大地改进了当前最好的结果O((k2.2)\+{2k}+n log k).通过对上述算法在高维空间中的进一步扩展，提出了关于超平面覆盖问题时间复杂度为O(dk\+{d+1}(dk)!/((d!)\+kk!)+n\+{d+1})确定性参数算法，对当前的最好结果O(k\+{d(k+1)}+n\+{d+1})有较大改进.
摘要：
有效预测RNA二级结构是生物信息学中的重要研究领域.提出一种基于隐Markov模型预测RNA二级结构的新方法.首先，应用前后缀匹配算法快速找到所有可能(包括假结)的茎区，建立RNA-HMM，寻找最优的茎区组合方法，得到包含假结的RNA二级结构.实验结果表明，提出的新方法降低了计算复杂性，提高了预测的特异性和敏感性，具有较高的准确率，可以预测RNA的假结结构.
有效预测RNA二级结构是生物信息学中的重要研究领域.提出一种基于隐Markov模型预测RNA二级结构的新方法.首先，应用前后缀匹配算法快速找到所有可能(包括假结)的茎区，建立RNA-HMM，寻找最优的茎区组合方法，得到包含假结的RNA二级结构.实验结果表明，提出的新方法降低了计算复杂性，提高了预测的特异性和敏感性，具有较高的准确率，可以预测RNA的假结结构.
摘要：
基于多核体系下的系统运行效率越来越受到各行业的关注,一个系统往往是由若干软件子模块构成的.一个完整的系统可以由Tomcat,Httpd以及Lucene这3个软件模块构成.这些软件本身均进行了一定的优化,各自运行效率都良好,可是如果将它们整合成一个系统,其效率的提高仍需要从整体多方面考虑.从不同软件的子任务之间的关系入手,通过分析它们的特点,提出苦干提高整体性能的方案.研究贡献在于以下3个方面:1)线程间同步操作的消除;2)通过多任务重排提高并行度;3)系统调用的单线程化.结果表明系统整体性能得到了提高,同时,每个子任务完成的功能更加清晰明了.
基于多核体系下的系统运行效率越来越受到各行业的关注,一个系统往往是由若干软件子模块构成的.一个完整的系统可以由Tomcat,Httpd以及Lucene这3个软件模块构成.这些软件本身均进行了一定的优化,各自运行效率都良好,可是如果将它们整合成一个系统,其效率的提高仍需要从整体多方面考虑.从不同软件的子任务之间的关系入手,通过分析它们的特点,提出苦干提高整体性能的方案.研究贡献在于以下3个方面:1)线程间同步操作的消除;2)通过多任务重排提高并行度;3)系统调用的单线程化.结果表明系统整体性能得到了提高,同时,每个子任务完成的功能更加清晰明了.
摘要：
为了满足应用软件对图形用户界面(graph user interface, GUI)快速变更的需求，提出了基于深度递归和广度递归思想的持久化和解析算法，设计了基于XML和XSD(XML schema description language)的GUI生成器.该生成器包括设计器和解析器，支持层次化的界面样式语义以及组、联合、枚举等数据模型语义.最后，给出了应用示例，使用Java和C#语言分别解析了采用该生成器定制的某网络入侵检测系统的路由器对象，同时可以验证用户输入数据是否符合约束语义.
为了满足应用软件对图形用户界面(graph user interface, GUI)快速变更的需求，提出了基于深度递归和广度递归思想的持久化和解析算法，设计了基于XML和XSD(XML schema description language)的GUI生成器.该生成器包括设计器和解析器，支持层次化的界面样式语义以及组、联合、枚举等数据模型语义.最后，给出了应用示例，使用Java和C#语言分别解析了采用该生成器定制的某网络入侵检测系统的路由器对象，同时可以验证用户输入数据是否符合约束语义.
摘要：
李未教授提出了R-演算系统，它是形式理论的修正演算系统，是OPEN过程模式和GUINA过程模式的基础.R-演算在这2种过程模式中的核心作用是，当一个形式理论与事实产生矛盾时，找出矛盾的必要前提，从而获得一个协调的子理论.通过3种不同的方法细致刻画R-演算的基本概念“必要前提”，第1种方法来自R-演算，第2种方法基于极大协调子集与极小非协调子集的，最后一种方法是对于R-必要前提的归纳定义.通过比较这3种方法，指出各自的优缺点，并从第3种方法推演出一个可靠并且相对完全的系统.在比较这3种方法的同时，还细致地探讨了R-终止式的上下界以及极大协调子集的不可枚举性.其中极大协调的不可枚举性在一定程度上表明了不存在一种同时满足可靠并且完全的系统.
李未教授提出了R-演算系统，它是形式理论的修正演算系统，是OPEN过程模式和GUINA过程模式的基础.R-演算在这2种过程模式中的核心作用是，当一个形式理论与事实产生矛盾时，找出矛盾的必要前提，从而获得一个协调的子理论.通过3种不同的方法细致刻画R-演算的基本概念“必要前提”，第1种方法来自R-演算，第2种方法基于极大协调子集与极小非协调子集的，最后一种方法是对于R-必要前提的归纳定义.通过比较这3种方法，指出各自的优缺点，并从第3种方法推演出一个可靠并且相对完全的系统.在比较这3种方法的同时，还细致地探讨了R-终止式的上下界以及极大协调子集的不可枚举性.其中极大协调的不可枚举性在一定程度上表明了不存在一种同时满足可靠并且完全的系统.
摘要：
缓冲区溢出目前已成为最常见的软件安全漏洞之一，从源代码形式来看，常见的缓冲区溢出漏洞主要有两种类型：数据拷贝和格式化字符串造成的缓冲区溢出.分析了常见缓冲区溢出漏洞发生的原因，给出了格式化字符串存储长度的计算方法，介绍了一种基于源代码静态分析的缓冲区溢出检测算法，该算法首先对源代码进行建模，构造其抽象语法树、符号表、控制流图、函数调用图，在此基础上运用区间运算技术来分析和计算程序变量及表达式的取值范围，并在函数间分析中引入函数摘要来代替实际的函数调用.最后使用该方法对开源软件项目进行检测，结果表明该方法能够有效地、精确地检测缓冲区溢出.
缓冲区溢出目前已成为最常见的软件安全漏洞之一，从源代码形式来看，常见的缓冲区溢出漏洞主要有两种类型：数据拷贝和格式化字符串造成的缓冲区溢出.分析了常见缓冲区溢出漏洞发生的原因，给出了格式化字符串存储长度的计算方法，介绍了一种基于源代码静态分析的缓冲区溢出检测算法，该算法首先对源代码进行建模，构造其抽象语法树、符号表、控制流图、函数调用图，在此基础上运用区间运算技术来分析和计算程序变量及表达式的取值范围，并在函数间分析中引入函数摘要来代替实际的函数调用.最后使用该方法对开源软件项目进行检测，结果表明该方法能够有效地、精确地检测缓冲区溢出.
摘要：
图像自动标注是计算机视觉与模式识别等领域中的重要问题.针对现有模型未对文本关键词的视觉描述形式进行建模，导致标注结果中大量出现与图像视觉内容无关的标注词等问题，提出了基于相关视觉关键词的图像自动标注模型VKRAM.该模型将标注词分为非抽象标注词与抽象标注词.首先建立非抽象标注词的视觉关键词种子，并提出了一个新方法抽取非抽象标注词对应的视觉关键词集合；接着根据抽象关键词的特点，运用提出的基于减区域的算法抽取抽象关键词对应的视觉关键词种子与视觉关键词集合；然后提出一个自适应参数方法与快速求解算法用于确定不同视觉关键词的相似度阈值；最后将上述方法相结合并用于图像自动标注中.该模型能从一定程度上解决标注结果中出现的大量无关标注词问题.实验结果表明，该模型在大多数指标上相比以往模型均有所提高.
图像自动标注是计算机视觉与模式识别等领域中的重要问题.针对现有模型未对文本关键词的视觉描述形式进行建模，导致标注结果中大量出现与图像视觉内容无关的标注词等问题，提出了基于相关视觉关键词的图像自动标注模型VKRAM.该模型将标注词分为非抽象标注词与抽象标注词.首先建立非抽象标注词的视觉关键词种子，并提出了一个新方法抽取非抽象标注词对应的视觉关键词集合；接着根据抽象关键词的特点，运用提出的基于减区域的算法抽取抽象关键词对应的视觉关键词种子与视觉关键词集合；然后提出一个自适应参数方法与快速求解算法用于确定不同视觉关键词的相似度阈值；最后将上述方法相结合并用于图像自动标注中.该模型能从一定程度上解决标注结果中出现的大量无关标注词问题.实验结果表明，该模型在大多数指标上相比以往模型均有所提高.
摘要：
把U-正交变换应用到图像无损编码中,研究U-正交矩阵的基本三角可逆矩阵(TERM)分解与单行基本可逆矩阵(SERM)分解.一个N阶U-正交矩阵的TERM分解由N－1个自由变量决定,用区间收缩方法可以搜索到TERM分解的局部近似最优解.如果用行交换方法搜索正交矩阵的SERM分解,那么一个8阶的正交矩阵最多只有40320种可能的SERM分解,用穷举法即能找到SERM的近似最优分解.最后,用U-正交矩阵的可逆分解对图像进行无损编码,实验表明可逆U-正交变换的无损编码的码率与浮点U-正交变换的近似无损编码的码率基本相同,SERM分解要比TERM分解更有效,三次U-正交变换的编码效果与离散余弦变换的编码效果几乎完全相同.因此,在图像无损编码中，可用三次U-正交变换代替DCT.
把U-正交变换应用到图像无损编码中,研究U-正交矩阵的基本三角可逆矩阵(TERM)分解与单行基本可逆矩阵(SERM)分解.一个N阶U-正交矩阵的TERM分解由N－1个自由变量决定,用区间收缩方法可以搜索到TERM分解的局部近似最优解.如果用行交换方法搜索正交矩阵的SERM分解,那么一个8阶的正交矩阵最多只有40320种可能的SERM分解,用穷举法即能找到SERM的近似最优分解.最后,用U-正交矩阵的可逆分解对图像进行无损编码,实验表明可逆U-正交变换的无损编码的码率与浮点U-正交变换的近似无损编码的码率基本相同,SERM分解要比TERM分解更有效,三次U-正交变换的编码效果与离散余弦变换的编码效果几乎完全相同.因此,在图像无损编码中，可用三次U-正交变换代替DCT.
摘要：
过高的测试功耗和过长的测试应用时间是基于伪随机内建自测试(BIST)的扫描测试所面临的两大主要问题.提出了一种基于扫描子链轮流扫描捕获的BIST方法.在提出的方法中，每条扫描链被划分成N(N>1)条子链，使用扫描链阻塞技术，同一时刻每条扫描链中只有一条扫描子链活跃，扫描子链轮流进行扫描和捕获，有效地降低了扫描移位和响应捕获期间扫描单元的翻转频率.同时，为检测抗随机故障提出了一种适用于所提出测试方法的线性反馈移位寄存器(LFSR)种子产生算法.在ISCAS’89基准电路上进行的实验表明，提出的方案不但降低约(N-1)/N的平均功耗和峰值功耗，而且显著地减少随机测试的测试应用时间和LFSR重播种的种子存储量.
过高的测试功耗和过长的测试应用时间是基于伪随机内建自测试(BIST)的扫描测试所面临的两大主要问题.提出了一种基于扫描子链轮流扫描捕获的BIST方法.在提出的方法中，每条扫描链被划分成N(N>1)条子链，使用扫描链阻塞技术，同一时刻每条扫描链中只有一条扫描子链活跃，扫描子链轮流进行扫描和捕获，有效地降低了扫描移位和响应捕获期间扫描单元的翻转频率.同时，为检测抗随机故障提出了一种适用于所提出测试方法的线性反馈移位寄存器(LFSR)种子产生算法.在ISCAS’89基准电路上进行的实验表明，提出的方案不但降低约(N-1)/N的平均功耗和峰值功耗，而且显著地减少随机测试的测试应用时间和LFSR重播种的种子存储量.
摘要：
日益增加的集成电路测试成本变得越来越难以接受，因而提出了一种简单而有效的解决方案.该方案把循环移位技术应用到测试数据压缩中，比起一般的移位技术，该方案更能有效地利用测试集中无关位.结合异或逻辑运算，所提方案累积无关位，进一步提高测试向量与其参考向量的相容性和反向相容性.在编码过程中对各种可能移位状态进行统计，建立Huffman树，找出最优化编码形式，因而可以增加短码字的利用率，减少长码字的使用频次.通过给出的分析和实验，说明了所提方案在附加硬件成本很低的情况下既能够提高测试数据压缩率，又能够减少测试时间，优于已发表的游程编码方案和其他同类型的编码压缩技术.
日益增加的集成电路测试成本变得越来越难以接受，因而提出了一种简单而有效的解决方案.该方案把循环移位技术应用到测试数据压缩中，比起一般的移位技术，该方案更能有效地利用测试集中无关位.结合异或逻辑运算，所提方案累积无关位，进一步提高测试向量与其参考向量的相容性和反向相容性.在编码过程中对各种可能移位状态进行统计，建立Huffman树，找出最优化编码形式，因而可以增加短码字的利用率，减少长码字的使用频次.通过给出的分析和实验，说明了所提方案在附加硬件成本很低的情况下既能够提高测试数据压缩率，又能够减少测试时间，优于已发表的游程编码方案和其他同类型的编码压缩技术.
摘要：
由被测电路自己施加测试向量的内建自测试方法把被测电路视为一种可利用的资源，而不仅仅是被测试的对象.通过将被测电路内部一些节点“反馈”连接到电路的输入端，被测电路可以在由外部加载初始测试向量之后，利用反馈顺序地产生并加载一组测试向量.对这种技术中的分组方法和反馈节点选取方法进行了改进，提出一种附加信息矩阵的面向多个特殊有向图的深度优先公共路径搜索方法和一种贪婪式反馈节点选取方法.对ISCAS85电路和MinTest测试集的仿真实验结果表明，这些方法可以有效减少硬件代价，并提高故障效率.
由被测电路自己施加测试向量的内建自测试方法把被测电路视为一种可利用的资源，而不仅仅是被测试的对象.通过将被测电路内部一些节点“反馈”连接到电路的输入端，被测电路可以在由外部加载初始测试向量之后，利用反馈顺序地产生并加载一组测试向量.对这种技术中的分组方法和反馈节点选取方法进行了改进，提出一种附加信息矩阵的面向多个特殊有向图的深度优先公共路径搜索方法和一种贪婪式反馈节点选取方法.对ISCAS85电路和MinTest测试集的仿真实验结果表明，这些方法可以有效减少硬件代价，并提高故障效率.
摘要：
在对象存储系统中，如何有效地在对象存储设备上分布对象是其面临的重大挑战.需要一个能够常数时间内定位对象，同时能公平地分布对象以及自适应存储规模变化的对象布局算法.目前大部分布局算法只能适应单层模式，少数的多层模式对设备配置有严格的要求，而且无法在常数时间内定位对象，自适应性较差.提出了一种新的分层对象布局算法，首先使用最大最小聚类算法将设备集合进行分类，支持灵活的设备配置.然后使用提出的EFAH Hashing算法在集群间和集群内分布对象.理论和实验证明，新的分层对象布局算法可以在常数时间内定位对象，从而减轻元数据服务器的计算量.同时可以在设备之间较公平地分布对象，达到I/O负载均衡的目的.而且在设备集合变化时，迁移较少的对象数以满足对象再次分布的公平性.
在对象存储系统中，如何有效地在对象存储设备上分布对象是其面临的重大挑战.需要一个能够常数时间内定位对象，同时能公平地分布对象以及自适应存储规模变化的对象布局算法.目前大部分布局算法只能适应单层模式，少数的多层模式对设备配置有严格的要求，而且无法在常数时间内定位对象，自适应性较差.提出了一种新的分层对象布局算法，首先使用最大最小聚类算法将设备集合进行分类，支持灵活的设备配置.然后使用提出的EFAH Hashing算法在集群间和集群内分布对象.理论和实验证明，新的分层对象布局算法可以在常数时间内定位对象，从而减轻元数据服务器的计算量.同时可以在设备之间较公平地分布对象，达到I/O负载均衡的目的.而且在设备集合变化时，迁移较少的对象数以满足对象再次分布的公平性.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
