Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2006年 第43卷 第5期    出版日期:2006-05-15
论文
文本检索的统计语言建模方法综述
丁国栋 白 硕 王 斌
2006, 43(5):  769-776. 
摘要 ( 580 )   HTML ( 0)   PDF (429KB) ( 908 )  
相关文章 | 计量指标
统计语言建模技术(statistical language modeling, SLM)已逐渐成为当前语言信息处理的主流技术之一.近几年的研究和实验表明,SLM技术在文本检索领域有着广阔的发展前景和拓展空间.对基于SLM的文本检索方法(SLMTR)进行了综述,重点论述SLMTR的主要方法和关键技术.首先对查询似然检索模型进行形式化的描述;然后详细论述语言模型的估计和数据平滑问题;并讨论了平滑对检索性能的影响;之后简要介绍了对查询似然模型的一些主要的扩展和改进工作;最后的总结部分讨论了SLMTR所面临的一些挑战.
基于模型的软件成本估计方法
何晓阳 王亚沙
2006, 43(5):  777-783. 
摘要 ( 580 )   HTML ( 1)   PDF (357KB) ( 497 )  
相关文章 | 计量指标
准确的估计是进行有效的项目计划、跟踪和控制的基础.基于模型的成本估计方法是软件成本估计研究的重点,它可分为算法驱动式模型、数据驱动式模型以及复合式模型.依照该分类模式,介绍了典型的软件成本估计方法,并从内部属性及外部评价两个维度共计11个指标对每类方法的假设前提、适用范围、优势及局限性进行深入的分析.最后,对软件成本估计研究的未来发展进行探讨.
关于覆盖组播中拓扑发现的研究
曹 佳, 鲁士文,
2006, 43(5):  784-790. 
摘要 ( 537 )   HTML ( 0)   PDF (381KB) ( 464 )  
相关文章 | 计量指标
覆盖组播的主机自己完成拓扑发现和构建转发树的工作.其中一个重要问题就是上层传输路径在底层可能是迂回的.如果拓扑发现可以揭示足够的底层拓扑信息,那么就可以尽力减小迂回程度.主要探讨在随机拓扑发现策略中上述迂回程度和k值的关系.发现每个主机至少随机选择Θ(logn)个不同的其他主机进行测试,就能保证在测试拓扑中从源到任意主机是可达的;至少随机选择2.997×n\-\{0.5312\}个不同的其他主机就能保证从发送源到任意主机的路径长度最多是直接采用单播传输的2倍.最后通过模拟实验验证了当满足上述条件时,再增大k值已不会使覆盖组播传输路径的迂回程度有十分明显的改善.
移动Agent在网格中的路径优化算法研究
张至柔, 罗四维, 陈 歆, 钟晶晶,
2006, 43(5):  791-796. 
摘要 ( 427 )   HTML ( 1)   PDF (313KB) ( 466 )  
相关文章 | 计量指标
用移动Agent作为访问网格服务的任务载体,代表服务或者应用程序在各种网格服务间智能地移动,能充分发挥移动Agent的优势,达到提高效率、减少开销的目的.因为网格环境具有自己的特点,因此提出了动态市场旅行商问题(TSP)模型来充分描述移动Agent在网格环境中行为方式,以及移动Agent在该模型中的路径优化算法,这对于指导不同类型移动Agent在网格中的路径选择是很有实用价值的.
一种基于任务全局迁移的静态调度算法
梁洪涛, 袁由光, 方 明,
2006, 43(5):  797-804. 
摘要 ( 467 )   HTML ( 1)   PDF (572KB) ( 488 )  
相关文章 | 计量指标
任务调度是分布实时系统中的一个关键问题. TDS等典型算法在优化条件下可得到该问题调度长度上的最优解.但是TDS等算法在节点分配时存在节点选择范围和节点执行时间范围的局限,无法最小化算法所需处理器数目.任务全局迁移调度算法GTT(global task-transferring)在保证调度长度最优的前提下,从全局范围内选择并调度任务节点,有效利用了处理器,可最小化调度所需处理器数目.优化条件下对各种算法的调度实验表明,GTT算法在加速比和效率上比TDS等同类算法有显著提高. GTT算法的时间复杂度是O(d|V|2).这里|V|是DAG图中的节点数,d是图中各节点入度或出度的最大值.
一种基于混合模型的实时网络流量预测算法
李 捷, 刘瑞新, 刘先省, 韩志杰,
2006, 43(5):  806-812. 
摘要 ( 681 )   HTML ( 3)   PDF (475KB) ( 802 )  
相关文章 | 计量指标
流量预测是流量工程、拥塞控制和网络管理的核心问题.网络流量由大量的非线性变化部分和少量的但不可忽略的线性变化部分组成.现有的网络流量预测算法只是单一采用线性或者非线性的方法进行处理,这种片面性造成预测的准确度和实时性难以保证.针对网络流量的特点,提出了一种基于卡尔曼滤波和小波分析混合的流量预测算法.通过对网络流量的线性部分和非线性部分进行区分对待,从而提高预测的准确度和实时性.仿真结果表明,该算法与单一的线性预测算法和非线性预测算法相比,具有较高的预测精度和较好的实时性.
基于EDF调度策略的端到端实时系统可调度性分析算法
沈卓炜 汪 芸
2006, 43(5):  813-820. 
摘要 ( 560 )   HTML ( 0)   PDF (395KB) ( 508 )  
相关文章 | 计量指标
端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能.
ChinaGrid图像处理网格平台中的语义信息服务研究
何儒汉 金 海 廖振松 章 勤
2006, 43(5):  821-827. 
摘要 ( 341 )   HTML ( 0)   PDF (408KB) ( 420 )  
相关文章 | 计量指标
在网格中要实现更加准确有效的服务发现、查询及其动态分配和替换,需要在语法匹配的基础上进一步实现语义匹配.介绍了在图像处理网格平台上开发的、基于语义的信息服务组件;描述了该组件的设计框架结构,并给出该组件的核心算法即网格服务语义匹配算法的描述.该组件能有效实现对图像处理网格服务的语义查询和工作流构建时的自动语义匹配以及工作流执行中网格服务的动态分配和替换.与传统语义服务匹配算法相比,所提出的网格服务匹配算法显著提高了网格服务的匹配准确度.
一种基于固定网络的移动对象运动轨迹索引模型
李国徽 钟细亚
2006, 43(5):  828-833. 
摘要 ( 333 )   HTML ( 0)   PDF (346KB) ( 490 )  
相关文章 | 计量指标
实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化. IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作. IMTFN由一个管理固定网络的2D R\+*-Tree、一组管理移动对象运动轨迹的1D R\+*-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.
高维数据流子空间聚类发现及维护算法
周晓云 孙志挥 张柏礼 杨宜东
2006, 43(5):  834-840. 
摘要 ( 414 )   HTML ( 0)   PDF (419KB) ( 624 )  
相关文章 | 计量指标
近年来由于数据流应用的大量涌现,基于数据流模型的数据挖掘算法研究已成为重要的应用前沿课题.提出一种基于Hoeffding界的高维数据流的子空间聚类发现及维护算法——SHStream.算法将数据流分段(分段长度由Hoeffding界确定),在数据分段上进行子空间聚类,通过迭代逐步得到满足聚类精度要求的聚类结果,同时针对数据流的动态性,算法对聚类结果进行调整和维护.算法可以有效地处理高维数据流和对任意形状分布数据的聚类问题.基于真实数据集与仿真数据集的实验表明,算法具有良好的适用性和有效性.
一种求解约束优化问题的演化规划算法
董红斌, 黄厚宽, 何 军, 侯 薇,
2006, 43(5):  841-850. 
摘要 ( 371 )   HTML ( 1)   PDF (538KB) ( 519 )  
相关文章 | 计量指标
提出了一种新的求解约束优化问题的演化算法——基于混合策略求解约束优化问题的演化规划算法(CMSEP).借鉴了Mezura-Montes的算法中直接比较的约束处理方法,为求解位于边界附近的全局最优解采用多样性保护机制,允许一定比例最好不可行解进入下一代种群,混合策略变异机制用于指导算法快速搜索过程.标准测试函数的实验结果验证了算法的通用性和有效性.
面向Option的k-聚类Subgoal发现算法
王本年, 高 阳, 陈兆乾, 谢俊元, 陈世福,
2006, 43(5):  851-855. 
摘要 ( 456 )   HTML ( 0)   PDF (350KB) ( 432 )  
相关文章 | 计量指标
在学习过程中自动发现有用的Subgoal并创建Option,对提高强化学习的学习性能有着重要意义.提出了一种基于k-聚类的Subgoal自动发现算法,该算法能通过对在线获取的少量路径数据进行聚类的方法抽取出Subgoal.实验表明,该算法能有效地发现所有符合要求的Subgoal,与Q-学习和基于多样性密度的强化学习算法相比,用该算法发现Subgoal并创建Option的强化学习算法能有效提高Agent的学习速度.
基于EM算法的对传网络学习及应用
郝 玉, 叶世伟,
2006, 43(5):  856-861. 
摘要 ( 323 )   HTML ( 1)   PDF (419KB) ( 454 )  
相关文章 | 计量指标
为克服“胜者全得”对传网络的缺陷,提出使用基于软竞争机制的对传网络.这样增加了网络的训练复杂度.为此,把竞争层中隐单元的输出作为未观察到的缺省随机变量,使用EM算法对基于软竞争的对传网络进行训练,降低训练复杂度,加快网络的收敛速度.在实现EM算法的M步时,根据基于软竞争机制对传网络竞争层的特点,对EM算法实现进行改进,没有使用常用的迭代重新加权最小二乘算法,而利用样本加权平均求取隐层单元的权值向量,使EM算法更加简单易行,收敛速度快.仿真实验结果表明,基于软竞争机制的对传网络具有很好的泛化性能,特别在模式分类上具有很好的实际应用价值.
CMAC神经网络碰撞问题解决方法的研究
苏小红 张明杰 马培军 王亚东
2006, 43(5):  862-866. 
摘要 ( 414 )   HTML ( 2)   PDF (324KB) ( 403 )  
相关文章 | 计量指标
针对CMAC神经网络学习算法存在因使用Hash编码技术而产生的实际映射空间地址碰撞问题,提出了一种基于设置权值溢出区解决地址完全碰撞问题的方法,与传统的依靠增加实际映射空间大小解决完全碰撞问题的方法相比,该方法节省了网络的实际权值存储空间,并且在实际地址空间大小相同条件下提高了网络学习的精度.最后,将该方法应用于非线性系统辨识与色彩匹配的样本训练中,实验结果验证了该方法的有效性.
基于Agent的模式识别框架APRF的研究
唐云廷, 程显毅,
2006, 43(5):  867-873. 
摘要 ( 487 )   HTML ( 5)   PDF (441KB) ( 418 )  
相关文章 | 计量指标
模式识别过程就是对输入模式的分类过程,类是模式的本质,一般认为特征向量是模式的概括,基于这一认识,使得计算机准确地识别模式为某一类是困难的,问题在于人类的识别活动从不基于什么概括的特征向量,而是基于对输入模式的某一侧面的认识,然后利用相似、融合、协同进行识别.这一机制与Agent的工作原理极其相似,通过分析概括模式对模式识别所带来的困难,基于协同学中序参量的概念,给出了基于Agent的模式识别框架APRF(agent orientation patten recognition frame).
类型系统的λω×\-≤等式理论及其语义的合理性
周晓聪
2006, 43(5):  874-880. 
摘要 ( 421 )   HTML ( 3)   PDF (435KB) ( 522 )  
相关文章 | 计量指标
类型系统在研究程序设计语言的理论基础方面起着十分重要的作用,特别地,带子类型的多态类型系统可刻画面向对象程序设计语言核心概念,如子类型、多态性等.为研究面向对象程序设计语言的形式理论基础,探讨了一个命名为类型系统λω×\-≤的带高阶子类型的多态类型系统,并利用插入子和fibration理论,引入λω×\-≤ fibration作为该类型系统的语义模型.进一步,讨论了类型系统λω×\-≤的等式理论,特别是与受限全称量词有关的等式,并利用插入子的性质,证明了对于该等式理论,λω×\-≤ fibration是合理的语义模型.
考虑测试环境和实际运行环境的软件可靠性增长模型
赵 靖 刘宏伟 崔 刚 杨孝宗
2006, 43(5):  881-887. 
摘要 ( 303 )   HTML ( 0)   PDF (401KB) ( 582 )  
相关文章 | 计量指标
软件可靠性增长模型中测试阶段和操作运行阶段环境的不同导致了两个阶段故障检测率的不同.非齐次泊松过程类软件可靠性增长模型是评价软件产品可靠性指标的有效工具.在一些非齐次泊松过程类模型中,有些学者提出了常量的环境因子,用来描述测试环境和运行环境的差别.实际上,环境因子应该是随时间变化的变量.考虑了运行阶段和测试阶段环境的不同,根据实测数据得到了变化的环境因子,并且根据测试阶段的故障检测率和变化的环境因子,转化得到了操作运行阶段的故障检测率.考虑到故障的排除效率和故障引入率,从而建立了一个既考虑运行环境和测试环境差别,又考虑故障排除效率和故障引入率的非齐次泊松过程类软件可靠性增长模型(PTEO-SRGM).在两组失效数据上的实验分析表明,对这组失效数据,PTEO-SRGM模型比G-O模型等模型的拟合效果和预测能力更好.
支持频繁更新的移动对象混合索引方法
廖 巍 熊 伟 景 宁 陈宏盛 钟志农
2006, 43(5):  888-893. 
摘要 ( 487 )   HTML ( 2)   PDF (381KB) ( 499 )  
相关文章 | 计量指标
TPR-tree是目前广泛使用的移动对象当前及未来位置索引技术,但是其频繁更新性能低下.通过在TPR-tree上增加一个指向索引树中间节点的直接访问表(direct-access table)内存结构和建于叶节点之上的Hash辅助索引结构,提出了一种支持频繁更新的移动对象混合索引HTPR-tree,并提出了基于HTPR-tree的扩展自底向上(EBUU)更新算法.性能分析和实验表明,采用EBUU算法的HTPR-tree动态更新性能大大高于TPR\+*-tree等索引,而查询性能仅仅稍逊.
基于约束的主动规则终止性分析
徐贵红, 张 健,
2006, 43(5):  894-900. 
摘要 ( 351 )   HTML ( 0)   PDF (426KB) ( 377 )  
相关文章 | 计量指标
终止性是主动规则所需的最重要的一个性质,但规则的终止性检查通常是不可判定的.已有的静态分析方法非常保守,SQL3标准也没有提供保证终止的机制,所以商业数据库限制规则级联触发的最大次数确保终止.由于规则可看成数据库状态转换器,而约束能够表示所有可能的数据库状态,基于约束表示的数据库状态及约束求解,模拟规则处理,可得到更精确的终止性结论.
基于活化路径和条件公式的主动规则集可终止性判定方法
熊中敏, 郝忠孝,
2006, 43(5):  901-907. 
摘要 ( 393 )   HTML ( 1)   PDF (386KB) ( 356 )  
相关文章 | 计量指标
支持主动规则机制已经成为现代数据库系统的一个重要特征.主动规则集的可终止性判定是主动数据库中一个核心问题之一,利用触发图和活化图的方法来判定可终止性都存在不同的保守性.为此,提出了为有效活化路径建立条件公式的思想,在此基础上给出了一个新的判定主动规则集可终止性的方法.分析的结果表明,提出的方法较现有方法可以发现更多的可终止性情形,最后给出了相应的算法及其可终止性、正确性证明.
分区动态地形的一种时序模型
陈国军, 赵沁平,
2006, 43(5):  908-913. 
摘要 ( 385 )   HTML ( 0)   PDF (356KB) ( 441 )  
相关文章 | 计量指标
在分布式虚拟环境中,地形因实体作用发生变化.为了使各仿真节点的地形数据保持一致,需要对各节点变化的数据时序化.根据地形局部变化特点,构造了多分区动态地形的时序模型.模型把子区域地形几何数据定义为单纯复合形集,按地形变化时间顺序和空间关系组织成一个偏序集.模型支持地形变化数据动态添加,指定时刻的地形提取.实验表明,基于DAG表示的地形抽取算法利用变化数据间的空间关系提高了计算性能.
有理曲线的均匀区间隐式化
李亚娟 汪国昭
2006, 43(5):  914-919. 
摘要 ( 404 )   HTML ( 0)   PDF (348KB) ( 433 )  
相关文章 | 计量指标
参数式曲线与隐式曲线是CAGD中常用的两种曲线形式,因此需要建立起二者之间相互转换的体制.长期以来,许多工作都集中在利用结式思想,将一个参数式曲线精确转化为一个隐式曲线上,而事实上用隐式曲线精确表示一条参数式曲线不仅非常麻烦,而且往往也没有必要.故此提出了参数式有理曲线均匀区间隐式化的一种新方法,利用区间算术和空间重心坐标的定义,可以用一个低阶区间多项式隐式曲线来逼近所给的参数式有理曲线,同时使一些目标函数最小化,达到用隐式多项式曲线来逼近参数式有理曲线的很好效果,并提供了一些算法和实例.
一种新的基于统计向量和神经网络的边缘检测方法
张 晶 张 权 王 欣
2006, 43(5):  920-926. 
摘要 ( 443 )   HTML ( 0)   PDF (512KB) ( 510 )  
相关文章 | 计量指标
通过构造不同的统计量定量描述了边缘点邻域灰度的分布特征,并将4个统计量组成统计向量.计算训练图像的统计向量作为样本对BP神经网络训练,然后将训练的BP网络直接用于边缘检测.新方法在统计向量的构造上充分考虑了边缘点和噪声点的区别,具有较好的抗噪性能;BP网络的结构和训练都比较简单;而且不需要设定阈值检测边缘.实验表明,新方法抗噪性能好,达到了令人满意的边缘检测效果.
基于大规模语料库的新词检测
崔世起, 刘 群, 孟 遥, 于 浩, 西野文人,
2006, 43(5):  927-932. 
摘要 ( 583 )   HTML ( 0)   PDF (332KB) ( 1048 )  
相关文章 | 计量指标
自然语言的发展提出了快速跟踪新词的要求.提出了一种基于大规模语料库的新词检测方法,首先在大规模的Internet生语料上进行中文词法切分,然后在分词的基础上进行频度统计得到大量的候选新词.针对二元新词、三元新词、四元新词等的常见模式,用自学习的方法产生3个垃圾词典和一个词缀词典对候选新词进行垃圾过滤,最后使用词性过滤规则和独立词概率技术进一步过滤.据此实现了一个基于Internet的进行在线新词检测的系统,并取得了令人满意的性能.系统已经可以应用到新词检测、术语库建立、热点命名实体统计和词典编纂等领域.
基于多分类器决策的词义消歧方法
全昌勤, 何婷婷, 姬东鸿, 余绍文,
2006, 43(5):  933-939. 
摘要 ( 418 )   HTML ( 1)   PDF (433KB) ( 702 )  
相关文章 | 计量指标
词义消歧问题可以形式化为典型的分类问题.通过学习少量带有词义标注的语料构造多个消歧分量分类器,并利用未标语料动态地对这些分类器进行更新,根据最终分量分类器分别对多义词义项的判定结果,组合决策多义词的义项.该方法无需手工构造大规模具有词义标注的语料库,并且具有较高的消歧准确率.
一种Virtex系列FPGA配置数据无损压缩算法
古海云, 李 丽, 许居衍, 高明伦,
2006, 43(5):  940-945. 
摘要 ( 402 )   HTML ( 0)   PDF (398KB) ( 440 )  
相关文章 | 计量指标
随着FPGA规模大幅度提高,配置数据的规模也迅速增加,从而导致FPGA重构时间的增加,并使得存储多个配置的存储器成为基于FPGA的嵌入式系统成本的最大因素.针对Virtex系列FPGA配置数据的结构特点,提出了一种基于LZW改进的配置数据压缩算法,并通过数字信号处理领域和数字通信领域的5个常用模块进行验证,取得了显著的压缩效果.
应用输入向量控制技术降低漏电功耗的快速算法
常晓涛, 范东睿, 韩银和, 张志敏,
2006, 43(5):  946-952. 
摘要 ( 400 )   HTML ( 1)   PDF (383KB) ( 487 )  
相关文章 | 计量指标
随着工艺的发展,为保证电路的性能和噪声容限必须降低阈值电压,这将导致漏电流呈指数增长,漏电功耗因而将逐渐超过动态功耗占据主导地位. CMOS的堆栈效应导致电路在不同向量下的静态功耗不同,因此在电路进入睡眠状态时使用输入向量控制技术是一种低功耗设计的有效方法,如何快速找到一个可降低电路漏电功耗的向量就成了问题的关键.介绍了一种在给定向量集合中查找低功耗向量的快速算法——基于概率传递的标记算法,并为此开发了一个事件驱动的门级组合电路仿真器.通过对ISCAS和龙芯处理器电路的实验结果表明,该算法同传统方法比较可以提高性能3.4倍,误差率仅约0.14%.
基于进程演算和知识推理的安全协议形式化分析
顾永跟, 傅育熙,
2006, 43(5):  953-958. 
摘要 ( 413 )   HTML ( 9)   PDF (332KB) ( 437 )  
相关文章 | 计量指标
安全协议的形式化分析是当前安全协议研究的热点,如何扩充现在已经成熟的理论和方法去研究更多的安全性质,使同一系统中各种安全性质在统一的框架下进行分析和验证是一个亟待解决的问题.进程演算是一强有力的并发系统建模工具,而结合知识推理可以弥补进程演算固有的缺乏数据结构支持的特点,以此提出了一个安全协议形式化分析的一般模型.基于此模型,形式化地定义了一些安全性质,给出了一个实例研究,并指出了进一步完善此模型的研究方向.