基于广义似然比的自适应在线配准算法

针对机载雷达配准时出现的偏差跳变问题,提出一种基于广义似然比(GLR)的在线配准算法.该算法通过对配准公式的测量残差进行检验,可以自适应地估计偏差跳变量.Monte Carlo仿真实验表明,与传统的配准算法相比,在偏差发生跳变时,该算法能迅速检测到跳变发生时刻并正确估计出跳变量的大小,偏差估计值可在较短的时间内收敛到跳变后的真实值,且估计精度较高,接近CR下界.     

Precedence parsing using domolki's algorithm

A parsing Algorithm for the class of precedence grammars is described, using Domolki's algorithm. The main strategy of the algorithm is that with the detection of the right‐end of the handle of a right sentential form, the determination of the production rule necessary for reducing the string (thus the handle) is complete.     

基于GLR算法的新型概率句法分析器

为了提高句法分析器的分歧能力和分析准确率,结合上下文无关概率模型PCFG和头驱动概率模型HDSM各自的优点,提出了一种新型的概率模型PCFG_HDSM,并基于GLR算法,实现了一个新型的汉语句法分析器。在词性标注阶段,通过对助词的详细标注使部分歧义在规则阶段就被去除掉,提高了系统消歧的能力。经过开放测试,准确率和回归率分别达到82.8%、74.7%,与其他分析器分析结果比较有了较大提高,证明新模型PCFG_HDSM确实提高了分析器的分歧能力。     

基于期待类型的Chart句法分析算法

Chart算法是目前句法分析中应用最广泛的算法之一,但该算法的计算效率仍有待提高。通过对两种常用Chart算法的分析,提出一种以由底向上的Chart算法为基础,结合自顶向下Chart算法的预测能力的算法。算法按严格从左到右、由底向上的方向进行,根据已有活动边的活动角色类型和句法规则,产生当前词位置上的期待类型表,并以此限制后续边的生成。对比实验的结果表明,分析速度较普通Chart算法提高了约24%,同时也减少了一半以上因边池溢出而导致的分析失败的语句。     

基于浅层剖析的CYK改进算法

现代汉语句法与英语句法不同,具有明显复杂性,一是不容易获得完整的规则集,二是整句剖析所得结果含有大量的歧义结构难以消除。使用分治的策略将句法剖析任务分为不同层面的小任务,逐层进行句法剖析是一种可行有效的方法。其基本思想是:首先采用多层马尔可夫模型对句子进行短语组块剖析,将整个句子分割为名词组块、动词组块等短语语块,然后在此基础上运行CYK剖析算法,剖析组块间的依存关系,最终实现对完整语句的句法分析,浅层剖析简化了CYK算法规则集,在一定程度上降低了句法剖析难度。     

基于语法功能匹配的汉语句法分析算法

以语法功能匹配作为句法分析的基本方法,以100万词清华973树库作为语法功能调查的主要资源,实现了一种基于语法功能匹配的句法分析算法。该算法能有效减少伪歧义,具有良好的分析效率,其分析结果包含了丰富而准确的语法信息。实验表明,短语正确率与召回率在封闭测试和开放测试中分别达到75.17%、73.69%和65.06%、56.55%。     

A crowding multi-objective genetic algorithm for image parsing

Image parsing is a process of understanding the contents of an image. The process normally involves labeling pixels or superpixels of a given image with classes of objects that may exist in the image. The accuracy of such labeling for the existing methodologies still needs to be improved. The parsing method needs to be able to identify multiple instances of objects of different classes and sizes. In our previous work, a novel feature representation for an instance of objects in an image was proposed for object recognition and image parsing. The feature representation consists of the histogram vector of 2 g of visual word ids of the two successive clockwise neighbors of any superpixels in the object instance and the shape vector of the instance. Using the feature representation, the instance can be classified with very high accuracy by the per class support vector machines (SVMs). A multi-objective genetic algorithm is also proposed to find a subset of image segments that would best constitute an instance for a class of objects, i.e., maximizing the SVM classification score and the size of the instance. However, the genetic algorithm can only identify a single instance for each class of objects, despite the fact that many instances of the same class may exist. In this paper, a crowding genetic algorithm is used instead to search for multiple optimal solutions and help alleviate this deficiency. The experimental results show that this crowding genetic algorithm performs better than the previously proposed method as well as the existing methodologies, in terms of class-wise and pixel-wise accuracy. The qualitative results also clearly show that this method can effectively identify multiple object instances existing in a given image.     

基于改进GLR算法的智能识别英语翻译模型设计

GLR算法模型翻译识别结果存在数据点重合的情况,精确度无法得到有效保障。为了准确的识别短语,设计了基于改进GLR算法的短语智能识别算法,该算法构建标记规模约74万个英汉单词的短语语料库,使短语具备可搜索功能,通过短语中心点构建短语结构,可获得词性识别结果,依据解析线性表的句法功能校正词性识别结果中的英汉结构歧义,最终获得识别的内容。实际测评结果显示,该算法克服了GLR的弊端,相对统计算法和动态记忆算法提高了运算速度和处理性能,更加适合机器翻译任务,为在智能机器翻译领域提供了新的思路。     

An efficient all-parses systolic algorithm for general context-free parsing

The problem of outputting all parse trees of a string accepted by a context-free grammar is considered. A systolic algorithms is presented that operates inO(m·n) time, wherem is the number of distinct parse trees andn is the length of the input. The systolic array usesn ² processors, each of which requires at mostO(logn) bits of storage. This is much more space-efficient that a previously reported systolic algorithm for the same problem, which requiredO(n logn) space per processor. The algorithm also extends previous algorithms that only output a single parse tree of the input.Research squpported in part by NSF Grant DCR-8420935 and DCR-8604603.     

基于SCNF和概率CYK算法的最佳剖析树

对基于纯规则(chart)的自底向上方法进行句法剖析后出现的大量无法消解的歧义现象,通过引入概率型Chomsky范式(SCNF)在一定程度上消除部分句法结构歧义;在利用Inside-Outside算法进行参数自动训练,并通过语法示例验证Inside-Outside算法的收敛性后,最后采用概率CYK算法得到句子的最佳剖析树.     

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log²n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.     

A “yo-yo” parsing algorithm for a large class of van Wijngaarden grammars

An algorithm is described for parsing a large class of van Wijngaarden grammars in polynomial time. The algorithm is based on Earley's context-free parsing algorithm, with the addition of a bottom-up component and a mechanism for implementing consistent substitution. In contrast to earlier algorithms, this algorithm works for grammars which are both non-left-bound and non-right-bound.     

基于依存句法分析与分类器融合的触发词抽取方法

事件检测与分类是事件抽取的关键环节,触发词抽取是完成事件检测与分类的主流方法。提出了一种事件触发词抽取方法,该方法针对单一触发词抽取方法没有充分利用依存句法分析信息且召回率不高的问题,通过综合利用依存句法分析信息和其他信息抽取触发词-实体描述对的方法来提高触发词抽取的召回率,然后将触发词-实体描述对抽取结果与单一触发词抽取结果相融合以避免召回率提高所带来的准确率下降问题。在ACE2005中文语料上进行实验,该方法在事件检测与分类任务中取得较好效果,F值分别达到了69.0%和66.2%。     

Incremental parsing without a parser

This article describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. Consider, for example, changing a “ + ” operator to a “1” operator or adding a short subexpression at a syntactically but not structurally correct position, such as inserting “) 1 (d“ at the # mark in” (a + b # + c)”. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This article describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. This algorithm is significantly different from other incremental parsing algorithms in that it does not involve modifications to a traditional parsing algorithm or the overhead of maintaining a parser stack or any data structure other than the syntax tree. Instead, the algorithm applies tree transformations, in real-time as each token is inserted or deleted, to maintain a correct syntax tree.     

三次插值频率估计的改进算法

对正弦信号频率估计的几种插值算法进行了研究,重点介绍了一种精度较高的三次插值算法,针对其估计误差仍然较大,而且在频率接近某一区域时精度下降的情况,提出了一种修正算法,仿真结果证明该算法在只增加少量计算量的情况下性能非常优越。     

一种三次非均匀B样条曲线的细分算法

近几年来,以B样条曲线为代表的曲线细分已成为计算机图形学领域的一项重要研究内容。提出一种基于对分方式的细分算法,能均匀地细分曲线,并用较少的细分次数得到对曲线较好的逼近效果。采用该细分算法,方便而快速地在计算机上绘制B样条曲线,对给定参数做出更加优良的控制动作,并提高控制系统的运动速度和曲线的显示速度,实例表明了该算法的有效性。     

Syntactic parsing: A survey

Syntactic parsing: A survey