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

软件学报 2009年第09期杂志 文档列表

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

参数计算中核心化技术及其应用2307-2319

摘要：在参数计算与复杂性理论中，一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的．核心化技术是参数化算法设计中应用最为广泛、有效的技术，是参数理论中的一个研究热点．通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法，总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果，展望核心化技术的进一步研究方向并加以分析讨论，针对核心化新技术研究和某些热点问题提出了可能采取的核心优化方法和思路．

流处理器上基于参数模型的长流分段技术2320-2331

摘要：长流分段是提高流处理器上流寄存器文件（stream registerfile，简称SRF）带宽利用率的重要途径之一．其中，量化受段大小影响的程序运行时间是获得最优分段的关键．为此提出了一种基于参数模型的长流分段技术，旨在获得理论上的最优分段以最小化程序运行时间．首先，建立了一个预取和重用优化指导的参数模型，以反映段大小对流处理器上程序性能的影响．然后，基于该模型分析，分别研究了计算密集型程序和访存密集型程序的最优分段策略．最后提出一种面向任意程序的最优分段技术．实验结果表明，该长流分段技术能够有效地避免和隐藏片外访存延迟，从而充分开发流处理器强大的计算能力．

TSP问题的脂肪计算复杂性与启发式算法设计2344-2351

摘要：旅行商问题（traveling salesman problem，简称TSP）是经典的NP．难解组合优化问题之一，求解它的高效启发式算法一直是计算机科学研究的热点．脂肪作为描述TSP结构特征的新工具，对启发式算法设计具有重要意义．目前，TSP问题的脂肪研究还处于初始阶段，缺乏理论分析结果及相关的启发式算法．首先分析了TSP问题的脂肪计算复杂性，通过构造偏移实例的技巧，证明了获取TSP的脂肪是NP-难解的，即在P≠NP的假设下，不存在算法可以在多项式时间内获得完整脂肪．在此基础上，通过分析TSP问题局部最优解与脂肪的关系，给出了求解TSP问题的元启发式算法-动态候选集搜索（dynamic candidate set search，简称DCSS）算法.利用该算法，改进了目前求解TSP问题最好算法之一的LKH．TSPLIB典型实例的实验结果表明，改进后的算法在解的质量上有较为明显的提高．新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值．

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

基于BDD的增量启发式搜索2352-2365

摘要：增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法，通常可以用来解决动态环境下的重规划问题．在人工智能领域，一些实时系统常常需要根据外界环境的变化不断修正自身，这样就会产生一系列变化较小的相似问题，此时应用增量搜索将会非常有效．另外，基于BDD（binarydecision diagram）的启发式搜索，结合了基于BDD的搜索和启发式搜索这两种方法的优点．它既用BDD这一紧凑的数据结构来表示系统的状态空间，又通过使用启发信息来进一步压缩搜索树的大小．在介绍基于BDD的启发式搜索和增量搜索之后，结合这两种方法给出了基于BDD的增量启发式搜索算法-BDDRPA＊．大量的实验结果表明，BDDRPA＊算法是非常有效的，它可以被广泛地应用到智能规划、移动机器人问题等领域中．

一种基于字词联合解码的中文分词方法2366-2375

摘要：近年来基于字的方法极大地提高了中文分词的性能，借助于优秀的学习算法，由字构词逐渐成为中文分词的主要技术路线．然而，基于字的方法虽然在发现未登录词方面有其优势，却往往在针对表内词的切分效果方面不及基于词的方法，而且还损失了一些词与词之间的信息以及词本身的信息．在此基础上，提出了一种结合基于字的条件随机场模型与基于词的Bi-gram语言模型的切分策略，实现了字词联合解码的中文分词方法，较好地发挥了两个模型的长处，能够有效地改善单一模型的性能，并在SIGHAN Bakeoff3的评测集上得到了验证，充分说明了合理的字词结合方法将有效地提高分词系统的性能，可以更好地应用于中文信息处理的各个方面，

基于相对流形的局部线性嵌入2376-2386

摘要：局部线性嵌入算法极大地依赖于邻域是否真实地反映了流形的内在结构，现有方法构造的邻域结构是拓扑不稳定的，对噪音和稀疏数据敏感．根据认知的相对性规律提出了相对变换，并用其构造了相对空间和相对流形．相对变换可以提高数据之间的可区分性，并能抑制噪音和数据稀疏的影响．在构造的相对空间和相对流形上确定数据点的邻域能够更真实地反映流形的内在结构，由此提出了增强的局部线性嵌入算法，明显地提高了性能，特别是基于流形的方法还同时提高了速度．标准数据集上的实验结果验证了该方法的有效性．

一种基于概念的数据聚类模型2387-2396

摘要：在数据挖掘研究领域，现有的大多数聚类算法都受到数据可伸缩性和结果可解释性的限制．为了解决这一难题，提出了一种基于概念的数据聚类模型．该模型从描述数据样本的数据本身出发，首先在预处理后的数据集上提取基本概念，再对这些概念进行概化，形成表示聚类结果的高层概念，最后基于这些高层概念进行样本划分，从而完成整个聚类过程．该模型能够在保证聚类准确性的基础上，彳艮大程度地减少要处理的数据量，提高原算法的可伸缩性．另外，该模型基于概念进行知识的发现与分析，能够提高聚类结果的可解释性，便于与用户交互．实验结果表明，该模型对于聚类结果较好且复杂度较高的算法尤为有效．

一种基于信息检索技术的网络新闻影响力分析方法2397-2406

摘要：利用信息检索领域中的相关算法，分析研究通过信息检索相关技术得到的相关信息，建立了一个网络新闻影响力模型来定量地计算一则新闻的影响力，从而估计它对社会安全产生影响的程度．在对大量实验结果的统计分析中发现，此方法可以有效地对新闻文章进行排序，发现不同新闻类型中最值得关注的新闻，其结果与人的定性判断结果具有较高的一致性．

二维黎曼流形的Voronoi图生成算法2407-2416

摘要：提出采用黎曼流形描述研究对象和基于坐标卡生成Voronoi图的算法思路．讨论了黎曼流形上研究Voronoi图的难点，并给出了存在定理，该定理说明了坐标卡生成Voronoi图的存在条件．按照算法思路和存在定理，详细描述了二维黎曼流形上创建坐标卡的算法，并给出流形上转换函数和混合函数的定义方法．最后描述了基于坐标卡生成Voronoi图的算法，并给出了具体实例．

基于人脸检测与SIFT的播音员镜头检测2417-2425

摘要：播音员镜头的检测是新闻视频结构化的关键步骤之一．提出了一种基于人脸检测与SIFT特征点匹配的播音员镜头自动检测算法孩方法首先利用人脸检测器过滤出具有人脸的候选镜头，然后利用颜色直方图判断镜头是否可能相似,再利用SIFT特征点匹配从候选镜头关键帧中找出相关的镜头组，最后利用各镜头组的信息判断出哪些是播音员镜头．对比传统的方法，该方法除了训练一个通用的人脸检测器外，不需要模板，也不需要针对某类新闻节目训练特别的分类器，可以直接利用算法对新类型的新闻节目提取播音员镜头．实验结果表明，该算法能够广泛地适应于各种不同种类的新闻节目、不同视觉质量的视频，可以有效地应用于新闻视频分析．

软件学报杂志数据库技术

基于R-Tree的高效异常轨迹检测算法2426-2435

摘要：提出了异常轨迹检测算法，通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配，进而检测异常轨迹．算法要点如下：（1）为了有效地表示轨迹的局部特征，以k个连续轨迹点作为基本比较单元，提出一种计算两个基本比较单元间不匹配程度的距离函数，并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念；（2）针对异常轨迹检测算法普遍存在计算代价高的不足，提出了一种基于R-Tree的异常轨迹检测算法，其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对，然后再通过计算距离确定其是否局部匹配，从而消除大量不必要的距离计算．实验结果表明，该算法不仅具有很好的效率，而且检测出来的异常轨迹也具有实际意义．

图结构XML文档上子图查询的高效处理算法2436-2449

摘要：研究了图结构XML数据上子图查询处理，给出了一系列高效的处理算法．基于可达编码，首先提出基于哈希的结构连接算法（HGJoin）来处理图结构XML数据上的可达查询．然后，该算法被扩展来处理特殊的二分图查询．基于这些算法和所给出的代价模型，提出了一般DAG子图查询的处理算法和查询优化策略．这些算法经过简单修改即可有效地处理一般的子图查询．理论分析和实验结果表明，算法具有较高的效率．

基于可判别超平面树的生成模型图像标注方法2450-2461

摘要：图像语义的自动标注是一个具有挑战性的研究课题，目前常见的机器学习方法，如统计生成模型（generative model）与判别模型（discriminative model）都被用于该问题的研究中．然而由于语义鸿沟的存在、图像训练数据的不平衡性以及图像标注的多标签特性等问题，使得上述方法的性能都有待进一步提高．提出一种基于可判别超平面树的生成模型图像标注方法．该方法根据待标注目标图像的高生成概率邻域建立局部超平面分类树，进而利用同层类间可判别信息，按自顶向下的层次分类得到待标注图像的语义相关图像集合．由此得到的相关类信息与新的生成模型框架相结合对待标注图像与语义关键词的联合概率进行估计，实现对目标图像的标注．其特点在于生成模型与判别模型方法得到了有效结合，可判别超平面树对隐含语义聚类的判别分析是对待标注图像的生成“邻域”的逐步求精过程，有效地提高了生成模型标注准确度；而对于判别分析难以解决的多标签分类、训练数据不平衡等问题，此方法通过联合概率估计自然地实现目标图像的多标签分配．在常用的包含5000幅图像的ECCV2002数据集进行了实验，结果表明，与目前已知的具有较好标注效果的基于生成模型的MBRM模型（采用图像分割方法）以及基于辨别分析的ASVM-MIL相比，此方法的，F1因子分别提高了14％和13％．

一种空间更优的数据流查询包含编码区间索引2462-2469

摘要：给出一种基于CEI（containment-encoded intervals）的存储优化的数据流查询区间索引结构．在数据流处理中涉及到大量的数值型区间查询操作，构造一个基于主存并支持快速查询的区间索引结构十分必要．对CEI索引结构而言，虽然支持高速查询，但存储利用率较低．针对该问题，提出了索引结构ACEI（advanced-CEI）．在CEI索引结构的基础上，通过数据结构调整和参数优化，ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O（R＋N·W/L＋Z-log（L））降为O（sqrt（R·N）＋N·sqrt（W）．实验结果表明，ACEI结构可以极大地提高索引结构的存储利用率，并且可以用于大端点值域下的区间索引．

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

网络距离预测技术2470-2482

摘要：首先概述了网络距离预测的基本概念，从不同角度对网络距离预测技术进行了分类讨论．然后根据预测机理的差异将现有网络距离预测技术划分为基于虚拟坐标的预测技术、基于网络拓扑结构的预测技术以及网络邻近度估计技术．在对典型的预测技术进行分析对比后，详细综述了网络距离预测的研究现状，对现有的各种预测技术以及研究成果进行了分析，指出了需要进一步研究的问题．最后探讨了网络距离预测技术的未来发展方向．

关于推荐2009年度《中国计算机学会王选奖》的通知2482-2482

摘要：《中国计算机学会王选奖》是由中国计算机学会设立的计算机科学技术创新和进步奖，奖励在计算机理论研究、技术创新和应用等方面做出成就的项目。本奖项旨在推动中国计算机及相关领域的科技创新和进步，促进科研成果的转化，促进IT产业的发展，推动科技界学术共同体评价体系的建立。本奖项代表了国内同行的专业评价和认可，并得到国家科学技术奖励工作办公室的批准。从2008年起，北大方正集团每年出资20万元人民币奖励获奖人员，体现了对科技创新的支持和高度社会责任感。

无线传感器网络中基于协同压缩方法的MAC协议2483-2494

摘要：基于无线信号的广播本质，利用传统MAC协议所忽略的串音（overhearing）数据，提出一种方法以在媒介访问控制层去除数据的空间相关性．根据串音所接收到的数据，事件监测节点间协同地对自身的数据进行压缩后再发送，从而在链路层减少冗余信息的传输．首先针对节点间的协同数据压缩问题进行量化，建立线性规划模型；进而提出一种近似最优的、更低时间复杂度（O（N^2））的启发式节点筛选算法．在此基础上，设计一种能量有效的、基于协同压缩方法的MAC协议（CCP-MAC），可分布式地控制节点实现该节点筛选算法，相应节点可从筛选出的被压缩节点子集中接收串音数据，融合冗余数据以后再进行发送．实验结果表明，CCP-MAC利用串音数据协调节点进行数据压缩，可在很大程度上节约能量，延长网络的生命周期．

基于层次角色委托的服务网格授权执行模型2495-2510

摘要：针对网格应用中对委托限制的多方面需求，提出了基于层次角色委托的服务网格授权执行模型．模型支持委托角色授予与撤销功能以及相应的关联性限制特性通过加入信任度，细化了关联性限制的表达粒度．通过定义角色树作为委托授权的基本单位并对角色树进行剪枝，改善了部分委托实现的难度通过定义带信任度的委托传播树，细化了对委托传播限制的控制．提出的委托凭证全面支持了角色委托的临时性、关联性、部分性、传播性限制需求．对模型中的委托授权执行规则作了形式化描述，并证明了执行规则能够细粒度地控制委托授权的执行过程．实例展示表明，模型能够满足网格应用对委托限制多方面的需求．