基于Earley算法的关联文法语法分析的并行处理

关联文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算。该文法比上下文无关文法具有更强的生成能力。通过对该文法深入的分析,提出了一种在并行环境下基于Earley算法的语法分析和识别算法。通过实例描述了算法并行处理的过程,验证算法的可行性和正确性。     

连接文法在并行环境下的语法分析和识别

连接文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算.连接文法比上下文无关文法具有更强的生成能力.通过对连接文法深入的分析,提出了一种在并行环境下的语法分析和识别算法,算法事实是以上下文无关文法并行识别算法为基础提出的.最后以实例详细描述了算法并行处理过程并验证其算法的可行性.     

确定有限自动机到正则表达式转换的并行处理

有限自动机和正则表达式都是描述语言重要方法,二者的转换具有重要意义.针对确定有限自动机模型做了深入的分析,在并行环境,提出了一种确定有限自动机到正则表达式的并行转换算法,并以实例详细描述了算法并行处理过程并验证了其算法的可行性.     

基于LL(1)分析表的布尔文法语法分析算法

布尔文法是针对特定的形式语言提出的一种新的描述形式,文法以上下文无关文法为基础,在形式规则中加入集合论的相关运算。传统的LL算法只能处理上下文无关文法,通过对布尔文法深入的分析,提出了一种基于LL(1)分析表的布尔文法的语法分析算法。通过实例详细描述了算法处理的过程,验证算法的可行性和正确性。     

正则式上右线性文法生成算法

本文旨在给出一种由正则式RE生成有限自动机再生成右线性文法的算法。     

基于完备剩余格值逻辑的下推自动机与上下文无关文法

引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。     

基于掩模的畸变棋盘格角点检测与排序

针对当前棋盘格角点检测算法对畸变棋盘格角点检测不足的问题,提出了一种基于掩模的畸变棋盘格角点检测与排序的方法。对所采集的畸变棋盘格图像,依次经过预处理,图像降噪,闭操作和Canny边缘检测以明确其在背景中的位置。然后,采用改进的Shi-Tomasi角点检测算法识别并提取棋盘格的所有角点(包括边缘角点),再通过递归排序算法获取棋盘格行列角点的坐标信息。实验仿真结果验证了所提出的方法的有效性,且相比于基于传统的Harris角点检测,Shi-Tomasi角点检测的算法,对具有一定畸变的棋盘格图像角点,具有更优的检测识别能力。     

回溯法求解多约束分配问题

回溯法是解决多约束条件下合理分配问题的重要方法之一,经过认真分析研究,提出了解决这类问题的一种新的有效算法——基于矩阵存储的回溯算法,并以学生宿舍合理分配问题为背景,给出了算法的具体实现过程,最后讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,实际应用的结果验证了该算法在多约束分配问题中更具合理性和有效性．     

C-TERN: 一种基于CFSA的军事新闻文本时间信息处理算法

提出一种基于层叠有限状态自动机(CFSA)的中文军事文本时间表达式识别与规范化算法C-TERN。C-TERN首先利用成熟的分词工具识别出文本中的时间词, 然后将从通用语言和军事语言中提取的时间表达式规则分成多层, 逐层进行时间信息的精细识别。在规范化过程中, 通过4个步骤分别对特殊时间表达式、简单时间表达式、时间段表达式和绝对/相对时间表达式进行推理计算和规范化。算法考虑了规则集提取的正确性、规则之间冲突的消解以及匹配方式的合理性。在多个数据集上的实验结果显示, C-TERN不但能有效地识别标准时间、偏移时间和不确定性时间表达式, 而且能完成对简单、特殊以及隐含的时间点、时间段和偏移时间的推理与规范化, 能够满足军事文本时间信息处理的需要。     

有限状态自动机识别过程的一个图论描述及算法

对于一个给定的有限状态自动机A，总试图通过某种途径来得到A所识别的字（w∈A*）的全体即L（A）。借助图论工具给出了有限状态自动机识别过程中一些关键步骤的详细描述，并在此基础上给出了有限状态自动机识别过程的一个算法。     

元胞自动机中斑图复制的识别算法

给出了元胞自动机中斑图复制识别的一种算法。通过定义每个元胞的特征数,将两个斑图统一放入一个区域内比较它们的特征数,从而判定是否出现复制现象。数值例子表明,该算法是有效的。     

实值形式背景下概念格的渐进式并行构造算法

经典的形式概念分析主要应用于属性值为布尔值的形式背景中,然而在很多实际应用领域,由于问题的复杂性,更多的形式背景中属性值为普通实值。这种实值虽然更为适合用来刻画实际问题的不确定性,但由于算法的复杂性大,当数据背景比较大时,传统意义上的算法并不能有效地解决概念的抽取问题。随着高性能并行技术的发展与成熟,并行计算机的成本与费用越来越低,通过适当的并行化手段,将其应用于形式概念分析领域可以显著提高算法的效率。文中基于实值形式背景,提出了一种构造实值概念格的渐进式算法,且通过对渐进式构造过程的分析,将算法并行化。通过数值实验对比了串行与并行算法的运算时间,给出了该算法并行化的加速效率。     

基于多阈值判断的单线激光雷达草丛识别方法

本文基于单线激光雷达提出了一种对于草丛障碍物的识别方法。首先对草丛特征进行分析,阐述了草丛障碍物与其他连续体障碍物的特征区别,由特征分析提出了一种多阈值草丛特征识别算法,通过候选框对单线激光雷达点云识别保留,最后通过试验进行验证该多阈值草丛识别方法。试验结果表明该算法能够充分利用单线激光雷达点云数据量小、计算时间短、鲁棒性强等优点,弥补了特殊环境下视觉识别适应性差、识别失效等问题,更好地发挥了单线激光雷达的作用。     

关于Fuzy语言的隶属度问题

讨论由Ｆｕｚｚｙ文法和Ｆｕｚｙ自动机生成的Ｆｕｚｙ语言的隶属度问题．引入概率和乘积型Ｆｕｚｚｙ文法与自动机的概念，并证明了概率和乘积型Ｆｕｚｙ文法与自动机的关系．通过举例比较３种不同形式的Ｆｕｚｙ语言的隶属度，指出概率和乘积型Ｆｕｚｚｙ文法具有的实际意义     

关联文法语法推导树的并行构造算法

通过对关联文法语法推导树的详细分析,提出了具有共享子树的语法推导树算法。该算法实现了不仅叶子节点可以共享,其中任意相同子树均可以共享,有效节省了存储空间。针对共享子树的特点,提出了并行构造共享子树的算法,并通过实例详细描述了算法并行处理过程,验证了算法的可行性和正确性。     

基于扩展有限元和改进海豚回声优化算法的损伤识别方法

提出了一种基于扩展有限元和改进海豚回声算法的方法,对结构中损伤的位置和尺寸进行识别。该方法在获得实际结构测量响应后,运用改进海豚回声算法对实际响应与扩展有限元模拟结构响应之差进行最小化,优化损伤参数,实现对损伤的估计和识别。在改进的海豚回声算法中,提出了一种搜索范围动态变化的寻优机制,增加了初搜索、精搜索、平移搜索、回溯搜索和重搜索等五个过程,相比原算法有较高的效率和较好的收敛性能。通过数值仿真方法验证了所提出的改进算法以及损伤识别方法的合理性和有效性。     

一种改进的分布约束优化算法MULBS+

完备算法虽然能够求得分布式约束优化问题最优解,但要消耗大量资源及时间,相反,非完备算法通过求得次优解来提高效率.MULBS作为一个有效的非完备算法,虽然在求解质量和时间上有所提高,但在解决赋值冲突时采用的回溯策略及并行搜索方面存在不足.通过对该算法的深入分析,本文针对上述问题进行了改进,提出其改进算法MULBS+.通过在回溯策略中引入最小冲突选择机制,以及在约束图密度较大时采用基于动态子图划分的并行搜索策略,进一步提高了算法的性能.实验表明,该算法除增加一定的通信信息外,其执行时间及求解质量均优于原算法.     

黑白棋盘格角点检测算法

分析了现有棋盘格角点检测算法存在的不足,提出了一种新的棋盘格角点检测算法.该算法定义4个特征方向,并通过黑白检测算子(BW)检测特征方向上像素的灰度分布特征,获得像素级精度的角点坐标位置;再根据局部窗口内响应值的相似度与影响因子对角点坐标加以修正,实现了亚像素级精度的角点坐标定位.该算法对图像的旋转和亮度变换具有鲁棒性.将本方法应用于实际拍摄的棋盘格图像,证明了其对棋盘格角点检测的有效性和实用性.     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法.算法分为预处理阶段和匹配阶段两个部分,预处理阶段对所有待匹配的模式进行分析,构造一个关于这些模式的树型有限状态自动机,匹配阶段利用这个模式自动机,对文本串进行一次性的搜索,查找文本是否包含模式集中的模式.为了提高了匹配速度,算法利用已匹配的字符串信息实行跳跃式的比较,避免了文本扫描指针的回溯.     

一种针对网络流式文本数据的匹配算法

本文描述了一种对网络流式数据实时监控的搜索算法，应用有限自动机的原理．实现对任意长度数据流进行多关键字无回溯单遍匹配扫描，且加入概率计算，在一定程度上实现文本的简单模糊语义分析。该算法已被网络过滤软件使用，并有良好表现。