摘要:具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(strict pattern matching with generalgaps and length constraints,简称SPANGLO).该问题具有如下4 个特点:它是一种严格的精确模式匹配;允许序列中任意位置的字符被多次使用;模式串中可以包含多个一般间隙;对出现的总体长度进行了约束.最坏情况下,一个SPANGLO 实例将转换出指数个非负间隙的严格模式匹配实例.为了有效地解决该问题,提出了子网树及其相关概念和性质.在此基础上提出了求解算法Subnettree Spanglo(SETS),并给出算法的正确性和完备性证明,同时指出该算法的空间复杂度与时间复杂度分别为O(m×MaxLen×W)和O(MaxLen×W×m²×n),其中,m,n,MaxLen和W分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性.

摘要:首先给出了量子最弱自由前置条件(weakest liberal precondition,简称wlp)wlp (A,B,C)-可交换的定义,研究了wlp (A,B,C)-可交换的充分必要条件;其次,得到了wlp 不是良好的谓词转换,验证了wlp 是比量子最弱前置条件(weakest precondition,简称wp)更弱的谓词转换,揭示了wlp 和wp 的本质区别;最后证明了wlp 的序列合成、并行合成和块结构等性质.

摘要:基于构件的软件构建方法目前被广泛使用在软件开发中,用于减少软件开发的工程成本和加快软件开发进度.面向构件的系统主要由第三方提供的可重用构件或者内建的可重用构件组成,因此,系统的质量好坏和维护的难易程度依赖于构件的品质.一个软件修改会给其他构件甚至整个系统带来影响,而修改影响分析是控制和消除这类影响的有效手段.然而,现有的研究很少涉及构件软件的修改影响分析,尤其缺少对系统层面的修改影响分析研究.提出了一种基于模型的系统化修改影响分析方法,该方法的基本思路是:首先提出构件及系统层面的修改影响分析模型,然后根据分析模型分别从构件和系统两个层面对构件软件修改前后的版本进行修改识别,并且利用“防火墙”方法进行影响分析.理论分析和实验结果表明,该方法是可行的,也是有效的.

摘要:研究的目的是在获取用户需求和领域描述的基础上规约出对软件规格的描述.提供了一种实现从用户需求到软件规约的平滑和可推理的变换方法.在深入研究问题框架方法的基础上,采用Hoare 的通信顺序进程语言CSP及Lai的最弱环境演算符实现了整个问题图的变换,且导出的软件规格是具有高抽象粒度的程序代码模型,能够被FDR模型检测工具所验证.该工作为实现嵌入式软件开发从需求到软件代码、文档的自动转化及验证等奠定了理论基础.此外,把该理论与模型检测工具FDR联合起来会有助于提高嵌入式软件开发的效率和准确性.

摘要:传统的软件错误定位技术通常利用测试覆盖信息计算程序语句发生错误的可疑度进行软件错误定位,但是这种定位技术没有充分考虑程序本身固有的依赖信息,缺乏语句筛选,从而使错误定位的精度受限.提出了一种基于层次切片谱的错误定位技术,以提高面向对象程序中的错误定位效率.这种技术首先分析程序不同粒度层次元素(包、类、方法以及语句)之间的依赖信息,对可能发生错误的元素进行筛选,缩小错误查找范围;在此基础上,建立了层次切片谱模型,并定义了一种可疑度度量方法;最后根据该可疑度结果从大到小的顺序进行错误定位.通过实验验证了基于层次切片谱的错误定位技术的有效性,且比基于程序谱的Tarantula 技术、Union 技术、Intersection 技术效率更高.

摘要:流程化简技术是一种重要的商业流程模型分析方法.已有的非形式化化简方法因缺乏理论基础而无法保证完备性.基于Petri 网的化简方法应用范围不针对流程模型因而不能保证可靠性.提出了针对自由选择工作流网的一个可靠完备化简规则集,可靠性保证化简过程中这类模型的行为正确性被保持,完备性保证任意一个正确的此类工作流网最终都能被化简为最简形式.基于化简规则集给出可靠完备的合成规则集,用于流程模型的设计与精化.

摘要:在自然语言处理和计算语言学相关技术支撑下,研究基于网络的动态多文档文摘系统框架,重点描述动态多文档文摘系统框架的相关内容,介绍利用矩阵子空间方法进行动态演化建模,利用相似度和质心整体优选计算方法进行信息过滤,并利用动态流形排序方法进行句子加权的动态多文档文摘生成系统.按照多文档文摘生成步骤的划分,对3 种创新的模型方法进行融合,综合起来从不同侧重点考虑,形成互补,提高系统性能.在网络环境下,此框架保证了动态演化的多文档文摘具有较高的信息新颖性和历史信息的演化性.

摘要:隐式篇章关系识别是篇章结构分析中最具有挑战性的任务之一.传统的方法注重篇章中的概念和意义特征,导致系统的性能不高.系统地探索了篇章中的浅层语义信息和以态度韵为导向的句子级情感等平面特征的有效性,同时提出了一种简单而有效的树核方法,最后采用复合核方法加以集成.在Penn Discourse Treebank(PDTB) 2.0语料库上的实验结果表明,引入浅层语义和情感等信息后,准确率得到显著提升.

摘要:为了自动区分中文主观词和客观词,采用主观性线索和汉字的主观性两种手段对动词和形容词进行主观性度量.主观性的线索进一步被分成级差(gradability)线索和主体(subject)线索;根据这些线索,使用基于图的算法进行评级(ranking).在汉语主观性词表构建中,提出使用主体线索和汉字主观性.5 个标注人员对随机选择的500 个单词进行主观性标注,据此构建主客观标准集,并将其用于各种设置下的实验结果评估.实验结果显示,当被标注的单词出现频率较高时,所提出的方法能够超过或者匹配人工标注.此外,尽管文中只使用了无标注的数据,但还有更多的先验知识(如语义词典等)可以被引入到该方法中.

摘要:开放领域新词发现研究对于中文自然语言处理的性能提升有着重要的意义.利用条件随机场(condition random field,简称CRF)可对序列输入标注的特点,将新词发现问题转化为预测已分词词语边界是否为新词边界的问题.在对海量规模中文互联网语料进行分析挖掘的基础上,提出了一系列区分新词边界的统计特征,并采用CRF方法综合这些特征实现了开放领域新词发现的算法,同时比较了K-Means 聚类、等频率、基于信息增益这3 种离散化方法对新词发现结果的影响.通过在SogouT 大规模中文语料库上的新词发现实验,验证了所提出的方法有较好的效果.

摘要:随着智能规划的发展,其所面对的问题规模越来越大,而且可以预见以后会更大.现有的研究大多用二级存储扩展空间,其终极形式应该是用数据库进行存储.此外,有很多同一领域的规划问题,其所包含的常量几乎一致,其中必然有可重用信息来帮助加速求解.要更好地利用这些可重用信息也需要数据库.考虑到以上两个问题,首次提出规划领域描述语言PDDL(planning domain description language)的ER 模型(entity relationship model),并基于此模型用存储过程来编写规划器SPP(stored procedure planner).SPP 是完全在数据库内部运行的最优规划器,存取效率高,可充分利用数据库的各种功能.在国际规划大赛IPC(Int’l planning competition)基准领域上的实验结果表明,在有限的机器配置下,SPP 可以求解传统最优规划器不能求解的问题.该工作迈出了在数据库中求解规划问题,从而彻底解决空间问题的第一步.

摘要:软件定义网络(software-defined networking,简称SDN)技术分离了网络的控制平面和数据平面,为研发网络新应用和未来互联网技术提供了一种新的解决方案.综述了基于OpenFlow 的SDN 技术发展现状,首先总结了逻辑控制和数据转发分离架构的研究背景,并介绍了其关键组件和研究进展,包括OpenFlow交换机、控制器和SDN技术,然后从4 个方面分析了基于OpenFlow 的SDN 技术目前所面临的问题和解决思路.结合近年来的发展现状,归纳了在校园网、数据中心以及面向网络管理和网络安全方面的应用,最后探讨了未来的研究趋势.

摘要:移动Ad hoc 网自组织、移动性等特性为组网带来便利的同时也增加了路由管理的难度.针对现有可靠路由算法解决问题具有局限性以及获取链路评价信息低效等问题,在DSR(dynamic source routing)协议基础上提出了基于本地信任系统的可靠路由协议(reliable routing protocol based on local trust system,简称TR-DSR).TR-DSR 协议选择路由时,综合考虑路由上各节点和各链路的可靠信任度,并在路由建立过程中利用这些信息,在确保找到可靠路由的基础上降低寻路开销.同时,为了防止自私节点对信任系统评价正确性的影响,提出了基于GTFT(generous tit fortat)策略的激励节点推荐响应行为的DFR(decide forwarding recommendation)算法.仿真实验结果表明,在节点频繁移动和存在大量自私节点的网络中,该协议的性能优势明显,验证了TR-DSR 协议的可靠性.

摘要:Salsa20 流密码算法是Estream 最终胜出的7 个算法之一.结合非线性方程的求解及Salsa20 的两个3 轮高概率差分传递链,对5 轮Salsa20 算法进行了代数-截断差分攻击.计算复杂度不大于O(2¹⁰⁵),数据复杂度为O(2¹¹),存储复杂度为O(2¹¹),成功率为97.72%.到目前为止,该攻击结果是对5 轮Salsa20 算法攻击最好的结果.

摘要:用户界面描述语言是实现模型驱动的用户界面开发的重要方式.当前的用户界面描述语言一方面在对不同物理特性的交互设备上的用户界面的描述能力不足;另一方面,缺乏可扩展性及界面描述的组成部分的可复用性.针对上述问题,设计出一种界面描述语言——E-UIDL(extensible user interface description language).该语言遵循层次化、模块化的设计原则,能够支持多设备、多通道的用户界面的描述,并通过实例说明描述语言对笔式用户界面开发、多设备界面自动生成以及自适应用户界面开发的支持,深入地阐述了E-UIDL 的特性.

摘要:为了实现对线性空间不变的模糊图像的盲复原,提出了一种基于稀疏性和平滑特性的多正则化约束的模糊图像盲复原方法.首先,根据自然图像边缘的稀疏特性,运用了一种权重的全变差范数(weighted total variation norm,简称WTV-norm)对复原图像进行正则化约束;然后,从运动模糊的点扩散函数(motion point spread function,简称MPSF)的特性出发,提出一种能够适用于多种模糊情况的多正则化约束;最后,提出了一种改进的变量分裂(modified variable splitting,简称MVS)方法来得到清晰的复原图像,同时准确地估计出相应的模糊退化函数.大量的实验结果表明,该方法能够较好地复原多种不同类型的模糊(例如运动模糊、高斯模糊、均匀模糊、圆盘模糊).与近几年提出来的一些具有代表性的模糊图像盲复原方法相比,该方法不仅主观的视觉效果得到了较为明显的改进,而且客观的信噪比增量也增加了1.20dB~4.22dB.

摘要:传统的局部保持降维方法追求最低的识别错误率,即假设每一类的错分代价都是相同的.这个假设在真实的人脸识别应用中往往是不成立的.人脸识别是一个多类的代价敏感和类不平衡问题.例如,在人脸识别的门禁系统中,将入侵者错分成合法者的损失往往高于将合法者错分成入侵者的损失.因此,每一类的错分代价是不同的.另外,如果任一类合法者的样本数少于入侵者的样本数,该类合法者和入侵者就是类别不平衡的.为此,将错分代价融入到局部保持的降维模型中,提出了一种错分代价最小化的局部保持降维方法.同时,采用加权策略平衡了各类样本对投影方向的贡献.在人脸数据集AR,PIE,Extended Yale B 上的实验结果表明了该算法的有效性.