• 2006年第17卷第12期文章目次
    全 选
    显示方式: |
    • >综述文章
    • 多模式匹配算法及硬件实现

      2006, 17(12):2403-2415.

      摘要 (8936) HTML (0) PDF 721.77 K (9666) 评论 (0) 收藏

      摘要:介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法--Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.

    • 一种主动容错的序列流并行分析算法

      2006, 17(12):2416-2424.

      摘要 (4236) HTML (0) PDF 635.14 K (5035) 评论 (0) 收藏

      摘要:提出一种主动容错的序列流并行分析算法--FTPSA算法(proactive fault-tolerant parallel sequence stream analysis algorithm),以解决噪声环境下大规模序列流的自适应分析问题.算法利用学习网络描述流序列,并存于0-1矩阵中;将低比例和高比例不良数据分层考虑,分别采用基于容错和基于结构优化的学习方法;同时,经过全局筛选,有效地减少了中间结果集合,降低了内存和通信消耗.真实数据集上的实验结果表明,FTPSA算法准确率高,占用的存储空间小,并有良好的容错性和扩展性.

    • 高性能低功耗的容错编译技术:错误流压缩算法

      2006, 17(12):2425-2437.

      摘要 (4703) HTML (0) PDF 842.78 K (5220) 评论 (0) 收藏

      摘要:在许多关键应用中,计算机的高性能、低功耗和高可靠性是必须同时满足的要求.传统的软件容错技术频繁使用和比较分支指令检测错误,带来了巨大的性能和功耗的开销.提出了基于计算数据流模型的错误流模型,并设计了错误流压缩算法.在错误流压缩算法中,利用附加计算压缩了错误流的直径,显著减少了分支指令的数量,而总指令数不变.针对StreamIT提供的快速傅立叶变换测试程序,采用Wattch对错误流压缩算法进行模拟测试.实验结果表明,当循环参数n=225时,与传统的EDDI算法相比,使用错误流压缩算法可减少分支指令24%以上,IPC提高超过12%,同时,功耗减少了将近5%.给出的推算表明:在该实验中,如果内层循环体的存储指令数量为8,分支指令的减少可以达到43%以上.

    • 失效区域紧致性对适应性随机测试的性能影响

      2006, 17(12):2438-2449.

      摘要 (4957) HTML (0) PDF 1.01 M (4957) 评论 (0) 收藏

      摘要:适应性随机测试是一种增强的随机测试方法.已有的研究发现:失效区域的紧致程度是影响适应性随机测试性能的几个基本因素之一,并仅在失效区域为长方形的情形下验证了上述猜想.采用仿真实验的方法进一步研究失效区域的紧致程度与适应性随机测试的性能之间的精确关系.研究了几种基本规则形状的和不规则形状的失效区域.实验结果表明:适应性随机测试方法的性能随着失效区域的紧致程度的增强而提高.该研究进一步地揭示了适应性随机测试优于随机测试的基本条件.

    • 一种风险驱动的迭代开发需求优先级排序方法

      2006, 17(12):2450-2460.

      摘要 (4488) HTML (0) PDF 690.81 K (5688) 评论 (0) 收藏

      摘要:需求优先级排序是指系统参与者为需求指定实现的优先次序,是迭代开发过程中开发者制定项目迭代计划的基础.现存的需求优先级排序方法对系统参与者之间的协商和调整优先级的支持能力不足,导致根据需求优先级所制定的迭代计划难以作出符合需求变更和环境改变的调整.提出一种风险驱动的需求优先级自适应排序方法.该方法将自适应计划方法学与风险驱动相结合,将风险作为排序决策的依据,以自适应的过程为迭代开发排序需求优先级.该方法能够改善需求优先级排序过程中系统参与者之间的协商和调整需求优先级的能力,增强在迭代开发中对需求的控制,降低因需求导致项目失败的可能性.

    • 一个组织间松散耦合跨组织工作流的仿真模型

      2006, 17(12):2461-2470.

      摘要 (6876) HTML (0) PDF 702.65 K (5615) 评论 (0) 收藏

      摘要:为了解决松散耦合跨组织工作流的仿真建模问题,以染色Petri网为理论基础,将颜色集、染色函数、资源库所、等待库所、忙库所、开始变迁、结束变迁、角色、组织、时间函数、资源函数和变迁函数引入到IOWF(inter-organizational workflow),提出了染色多维跨组织工作流网CMD/IOWF(colored multi-dimension/IOWF).基于CMD/IOWF,讨论了组织间松散耦合跨组织工作流中多个不同项目工作流实例通过资源共享和活动同步相互耦合以及与仿真相关的资源约束和时间的建模问题.通过定义输入/输出、状态、事件、时间推进函数和状态转移函数,给出了一个组织间松散耦合的多个跨组织工作流的仿真模型.基于该模型的仿真分析可以求解组织间松散耦合跨组织工作流的关键性能指标,包括:对应项目工作流实例的平均执行时间、平均执行成本及其关于组织的分布,各项目的资源利用率.最后,以一个实例验证了提出模型的有效性.

    • 一种基于特征编组的直线立体匹配全局算法

      2006, 17(12):2471-2484.

      摘要 (4280) HTML (0) PDF 829.94 K (6020) 评论 (0) 收藏

      摘要:由于直线断裂、遮挡以及共面空间直线投影等因素的影响,从左右图像中提取出来的直线之间会出现"一配多"甚至"多配多"的匹配情况,然而目前很少有算法能可靠地处理这些情况.提出了一种基于特征编组的匹配算法来解决它.与已有方法不同,该方法是在由两幅图像共同组成的直线集上进行编组.每个特征编组包含了内部直线之间的匹配关系.这样,直线匹配的问题就转化为从直线集中提取一些相互兼容的特征编组的问题.整个算法分为两步:首先在几何和辐射约束的前提下构建所有可能的特征编组,并计算每个特征编组的匹配度,然后从所有可能的特征编组中寻找一个特征编组子集,在保证直线集中的每条直线最多属于该子集中一个特征编组的前提下,使得该子集中特征编组的匹配度之和最大.为了解决这个整数规划问题,设计了一种分两阶段的算法:首先将整个问题分为多个子问题,然后对于每个子问题,利用分支定限法寻找最优解.将所提出的算法应用于实际的立体图像对中,取得了满意的结果.

    • 有界模型检测同步多智体系统的时态认知逻辑

      2006, 17(12):2485-2498.

      摘要 (5038) HTML (0) PDF 1.00 M (5370) 评论 (0) 收藏

      摘要:提出在同步的多智体系统中验证时态认知逻辑的有界模型检测(bounded model checking,简称BMC)算法.基于同步解释系统语义,在时态逻辑CTL*的语言中引入认知模态词,从而得到一个新的时态认知逻辑ECKLn.通过引入状态位置函数的方法获得同步系统的智能体知识,避免了为时间域而扩展通常的时态认知模型的状态及迁移关系编码.ECKLn的时态认知表达能力强于另一个逻辑CTLK.给出该算法的技术细节及正确性证明,并用火车控制系统实例解释算法的执行过程.

    • 细粒度扩展视频均等质量流化算法

      2006, 17(12):2499-2507.

      摘要 (4612) HTML (0) PDF 711.22 K (5135) 评论 (0) 收藏

      摘要:细粒度扩展(fine-granularity-scalability,简称FGS)编码具有很强的灵活性和较好的视频流化性能,故已被MPEG-4和H.26L等标准所采用.FGS编码的一个突出特点是可以随意裁减以适应网络带宽的变化.但是,简单的裁减方法容易造成连续图像质量抖动过大,而用户通常希望流化视频的图像质量尽可能地平滑.在相关研究的基础上,针对非实时流化应用,分别讨论了在无损和有损条件下进行FGS编码均等质量流化的算法.该算法基于FGS的分段线性率失真模型和滑动窗口,在无损条件下,使用二分法,在当前窗口中的所有帧之间进行速率分配,以实现均等质量流化;在有损条件下,通过自适应的启发式算法,并结合前向纠错(forward error correction,简称FEC)技术来达到同样的目的.实验结果表明:在两种情况下,该算法均可以获得较好的流化效果,使流化视频的图像质量更加平滑.

    • 基于局部Gabor变化直方图序列的人脸描述与识别

      2006, 17(12):2508-2517.

      摘要 (6220) HTML (0) PDF 690.62 K (6102) 评论 (0) 收藏

      摘要:提出了一种在Gabor变换幅值域内提取局部变化模式空间直方图序列(histogram sequence of local Gabor binary patterns,简称HSLGBP)的人脸描述及其识别方法.鉴于Gabor特征对光照、表情等变化比较鲁棒,并已在人脸识别领域得到成功应用,首先对归一化的人脸图像进行多方向、多分辨率Gabor小波滤波,并提取其对应不同方向、不同尺度的多个Gabor幅值域图谱(Gabor magnitude map,简称GMM),然后在每个GMM上采用局部二值模式(local binary pattern,简称LBP)算子抽取局部邻域关系模式,最后由这些模式的区域直方图形成的序列来描述人脸.Gabor变换、LBP、空间区域直方图的采用使得该方法对光照变化、表情变化、误配准等具有良好的鲁棒性.而且,这种人脸建模方法不需要基于训练集合进行统计学习,因而不存在推广性问题.同时,进一步探讨了如何在分类器设计阶段与统计方法进行结合的问题,提出了统计Fisher加权的HSLGBP匹配方法.在通过FERET人脸库光照、表情和时间变化测试集上与已发表的实验结果进行对比,充分验证了该方法的有效性.

    • 偏好推理的逻辑链实现

      2006, 17(12):2518-2528.

      摘要 (4351) HTML (0) PDF 915.71 K (5473) 评论 (0) 收藏

      摘要:以定性偏好描述语言LPD(logic preference description)为基础,提出把定性偏好表示为基于命题逻辑的逻辑链,主要工作包括:(1)提出一个带有偏好的决策过程的一般性框架,在此框架内,详细介绍了LPD偏好描述语言;(2)提出基于LPD偏好算子的逻辑链构造方法.从而把LPD语言中偏好推理转化为相应的逻辑链构造过程,便于偏好重用.最后总结全文并提出需要进一步研究解决的问题.

    • 基于粒子滤波的人脸图像超分辨率重建方法

      2006, 17(12):2529-2536.

      摘要 (4400) HTML (0) PDF 560.51 K (5944) 评论 (0) 收藏

      摘要:将人脸图像超分辨率重建描述为人脸混合模型的纹理和位置参数的贝叶斯概率估计问题,将超分辨率重建的图像配准和像素融合这两个过程置于统一的概率估计框架下,并利用基于粒子滤波的参数估计算法,同时估计纹理和位置参数,从而实现人脸图像的超分辨率重建.包含灰度和位置两种先验信息的人脸混合模型,同时用于超分辨率重建的两个过程中,提高了图像配准精度和重建算法的性能,避免了通常方法在获得准确鲁棒的运动场估计时需要清晰的高分辨图像,而获得清晰的高分辨图像时又需要准确鲁棒运动场估计的困境.正面人脸合成序列图像实验结果表明,该方法获得的重建结果较为理想.

    • 基于信任和K臂赌博机问题选择多问题协商对象

      2006, 17(12):2537-2546.

      摘要 (4933) HTML (0) PDF 687.07 K (6260) 评论 (0) 收藏

      摘要:Agent之间的多问题协商(multi-issue negotiation)是一个复杂的动态交互过程.解决协商之前的对象选择问题在电子商务中有着重要的应用价值.为了提高多问题协商的准确性和购物Agent的效用,主要解决协商前的销售Agent的选择问题.为了充分利用协商历史,实现探索(exploration)和利用(exploitation)的折衷,把销售Agent的选择问题转变成K臂赌博机问题(K-armed bandit problem)来求解.提出了信任和声誉的度量模型,结合K臂赌博机问题的求解技术,采用学习机制,提出了几个确定奖励分布的改进算法.最后,以模拟协商过程为基础,将改进算法、信任和声誉有机地结合起来,提高了选择销售Agent的准确性和实用性.几个实验都说明了该工作在应用中的有效性.

    • 语音识别确认中的置信特征和判定算法

      2006, 17(12):2547-2553.

      摘要 (4798) HTML (0) PDF 435.67 K (5611) 评论 (0) 收藏

      摘要:提出了一种基于支持向量机的联合多种置信特征进行语音识别确认的判定方法.从待确认语音中提取出分段的后验概率和线性预测编码识别结果置信特征,其中后验概率根据垃圾模型近似计算得到;设计支持向量机分类器联合多种置信特征给出最终确认结果.实验结果表明,所提出的置信特征和支持向量机分类器取得了很好的确认效果.

    • 面向事件处置的信息服务集成调度模型

      2006, 17(12):2554-2564.

      摘要 (4555) HTML (0) PDF 618.04 K (5034) 评论 (0) 收藏

      摘要:以电子政务、电子商务等城市应用为背景,针对这些应用中跨领域事件处置所涉及的异构、分布式资源、服务集成调度以及跨领域知识共享问题,提出了一个面向事件处置的、基于规则的信息服务集成调度模型.该集成调度模型具有4个分层结构,包括资源层(resource layer)、知识层(knowledge layer)、业务层(business layer)和表示层(representation layer).重点就知识层形式化业务规则的定义、资源和服务的引用以及规则引擎等给出了详细的设计和实现.最后,对该模型进行了验证,实现了一个城市应急联动应用中的统一接警事件处置原型系统.

    • 基于地址转发表的交换式以太网拓扑发现方法

      2006, 17(12):2565-2576.

      摘要 (4911) HTML (0) PDF 758.90 K (7019) 评论 (0) 收藏

      摘要:提出一种称为连接推理技术(connections reasoning technique)的谓词逻辑推理方法推导节点间的连接关系.该方法把交换机地址转发表翻译为一组谓词公式,把拓扑发现问题转变为一个谓词逻辑推理的数学问题,借助数学工具对拓扑发现问题进行研究.基于连接推理技术提出了一种拓扑发现算法,与现有方法相比:(1)该方法能够更充分地利用不完整地址转发表的冗余信息,只需一小部分转发表就可以把整个网络拓扑构建出来;(2)该方法完全适用于多子网交换域的拓扑发现.此外,还提出了一种开销很小的动态网络拓扑发现方法.该算法成功地应用在社区宽带综合业务网络管理系统中.

    • 传感器网络安全研究

      2006, 17(12):2577-2588.

      摘要 (5427) HTML (0) PDF 658.43 K (5437) 评论 (0) 收藏

      摘要:由于传感器网络自身的一些特殊需求,加上其节点资源非常有限和网络特征的多样性,其安全问题在很大程度上不同于传统网络.给出了传感器网络的安全体系结构,力图对该领域的研究进行整体的描述.讨论了3个方面的问题:1)所采用的密码体制,如SKE,MAC,PKC等;2)密钥管理中的多种密钥建立算法;3)路由、能耗和容错等多因素相关的综合考虑.最后,简要介绍了其他一些安全问题以及该领域今后的研究热点.

    • 并行机间歇过程生产调度的遗传局部搜索算法

      2006, 17(12):2589-2600.

      摘要 (4485) HTML (0) PDF 847.80 K (6469) 评论 (0) 收藏

      摘要:研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.

    • 弱硬实时系统约束规范

      2006, 17(12):2601-2608.

      摘要 (4652) HTML (0) PDF 551.44 K (5244) 评论 (0) 收藏

      摘要:从弱硬实时系统定义出发,概述现有弱硬实时约束规范及其相互关系,提出了一种约束规范(m,p),与已有的约束规范作了严格性强弱的比较,并给予了证明;同时修正了Bernat提出的一个约束强弱比较的定理.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号