一种有效的结点标号上下文无关图文法分析算法

本文讨论了上下文无关图文法的性质，并证明了图文法推导具有独立性．本文还给出了一种有效的上下文无关图文法分析算法，它具有多项式时间复杂性，并给出了算法的正确性证明．该算法已经用Ｃ语言实现．     

一个上下文无关文法的构造定理及其在推断中的应用

递归概念可以在句子中重复派生、循环出现。对这样的句子推断时,若为递归概念的每一个派生部分引进一个递归概念来描述,将推断出多个与之有相似的产生式结构的递归概念,同时也构造出一个新文法。本文先给出新文法的形式化构造方法,证明了新文法与原文法的等价性。在文章的后部,通过实例,介绍该定理在简化复杂文法推断中的应用。     

基于PRAM模型的CFGs并行识别与语法分析的扩充算法

本文介绍了一种PRAM模型上的上下文无关文法的并行识别和改进的并行语法分析方法金字塔结构,并对该方法进行了修改和补充,使其对非Chomsky规范形式,即文法的产生式右部候选式（即规则）有两个以上的非终结符连接的,或者候选式中既有非终结符,又有终结符的情况,扩充的算法也能识别和分析。     

采用预测策略的Earley算法

在自然语言处理中,句法分析主要有基于统计的方法和基于规则的方法。Earley算法是一种基于规则的方法,可以分析任意上下文无关文法(CFG),而不需要对文法进行修改。详细分析了Earley算法的特点。在通常的Earley算法中增加了多种预测机制,这些预测机制借鉴了LL,LR以及SLR等确定性分析算法的一些思想,并对这几种不同的预测机制及其组合在相同条件下进行了中文句法分析实验。结果显示,引入这些预测机制通常可以减少产生项目的数量,从而节省存储空间,减少运行时间。     

获取上下文无关文法的一种交互式算法

本文提出一种交互式的上下文无关语言的学习算法，该算法是专门为ＳＡＱ系统设计的，所得到的文法能够自然地反映句子的内部结构，从而很容易刻划句子的含义（语义）。     

基于神经网络的GLR句法分析算法

提出并实现了一种基于神经网络的GLR(Generalized LR)句法分析算法,该算法结合神经网络自学习、自组织和并行分布处理等优点,以BP神经网络结构模型取代了GLR算法的分析表,模拟其移进和归约动作,通过计算网络输出来分析句法结构。该分析算法较好地解决了GLR算法对于存在多个移进归约冲突动作时,复制分析栈会使得动作表变得很大的缺点,实验结果表明,这种算法具有较好的泛化能力。     

一种处理结构化输入输出的中文句法分析方法

中文句法结构复杂,特征维数较高,目前已知最好的汉语句法分析效果与其他西方语言相比还有一定的差距。为进一步提高中文句法分析的效率和精度,该文提出一种采用二阶范数软间隔优化的结构化支持向量机(StructuralSupportVectorMachines,StructuralSVMs)方法对基于短语结构的中文句法进行分析,通过构造结构化特征函数ψ(x,y),体现句法树的输入信息,并根据中文句子本身具有的强相关性,在所构造的ψ(x,y)中增加中文句法分析树中父节点的信息,使ψ(x,y)包含了更加丰富的结构信息。在宾州中文树库PCTB上的实验结果表明,该文方法与经典结构化支持向量机方法以及BerkeleyParser相比可取得较好的效果。     

一种新型递归函数的求值算法

上下文无关语言上递归函数(recursive functions on context-free languages,简称CFRF)是为描述计算机上用的非数值算法而提出的一种新型递归函数.该函数的一个重要研究方面是函数的求值算法研究.对此问题的一些研究结果进行了总结.在讨论计算和语法分析的结合方式之后,对主要算法按照算法适用范围从小到大的顺序(同时也是算法研究和提出的顺序)做了较为全面的介绍,着重介绍一种通用的新的高效求值算法,即面向树的求值算法.同时对把CFRF扩充为多种类递归函数后的求值方法进行了说明.CFRF的几个求值算法均已在机器上实现,得到了实践的检验.     

一种基于文法演化自动拟合非线性数据的蜂群算法

将文法演化方法引入蜂群算法, 基于上下文文法定义多种数学函数, 提出了自动拟合非线性数据的蜂群算法BCGE, 并给出了通过基因截断、基因增补及利用领域知识加速BCGE的方法。基于文法演化的BCGE比基于文法规划的其他算法更为简洁, 且存储基因型所需的空间也远比其他算法存储语法树所需的空间少。通过五个测试函数的实验表明, BCGE能够有效地拟合非常复杂的非线性数据。     

一种基于结构划分概率的口令攻击方法

选择有效的口令结构是提高口令字典攻击命中率的有效方法.人们在记忆口令时,通常不会一次性进行整体记忆,而是将口令划分成块分别记忆的.基于此,文中分析了已有的口令结构,提出了依据划分概率对口令结构进行再次划分的口令攻击方法.该方法将攻击口令的焦点放在高概率的口令结构上,通过对高概率的口令结构进行再次划分,产生更有效的口令结构,并用它们来产生候选口令,从而提高攻击命中率.最后通过真实口令测试数据对该方法进行了验证,实验结果表明,给定相同数目的高概率口令具体结构,通过划分,文中的方法与Matt Weir方法相比能够多恢复20%~30%的口令.根据攻击结果,文中的方法还可以更新所使用的字典,以达到学习的目的,提高后续攻击效率.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

基于线性阵列网络的并行语法分析算法设计

本文提出了线性阵列LA(Linear Array)连接状态中上下文无关文法(CFG)的并行语法分析算法的设计思想,指出对形如[i,j,B→η·]的项目传递时环形拓扑结构的冗余,并以实例详细描述了线性陈列连接结构中分析存储信息的演变过程。     

LR分析的教学法探讨

LR分析法是编译程序语法分析中最常用且有效的自下而上的分析方法,理论较完善,适用于大多数上下文无关语言的分析。本文主要探讨LR分析的教学方法,采用"启发+关联式"教学法,引导学生理解LR分析的内涵。     

结合结构下文及词汇信息的汉语句法分析方法

针对句法分析中上下文无关语法模型对句子信息利用的不足,通过融入结构下文和部分词汇信息,提出两种基于概率上下文无关语法模型的短语结构消歧方法,以达到消解结构歧义的目的;引入分层分析的算法,通过损失一定的时间效率使得在提高分析准确率的同时保证分析结果的全面性。实验结果表明,融入结构下文及词汇信息的汉语句法分析方法,利用了更多的句子信息,与上下文无关语法相比有着更强的消歧能力。     

层级分类概率句法分析

对已有的句法分析中引入知识的方法进行了归纳分析,认为多种句法分析方法都可被看作是基于特征标记的分类,然后分析了其中的欠分类和过分类问题.在此基础上,提出一种层级分类短语结构文法和一种层级分类概率句法分析方法(hierarchically classified probabilistic context-free grammar),并设计了一种通过对实例进行聚类来消除句法规则的分类歧义方法.还进一步将层级分类扩展到概率上下文相关句法分析方法,利用上下文相关性的层级分类来解决引入上下文相关时的数据稀疏性问题.通过上述一系列方法有效地克服了过分类与前分类之间的矛盾.     

中文语义依存关系分析的统计模型

该文提出了一个统计语义分析器,它能够发现中文句子中的语义依存关系．这些语义依存关系可以用于表示句子的意义和结构．语义分析器在1百万词的标有语义依存关系的语料库(语义依存网络语料库,SDN)上训练并测试,文中设计、实现了多个实验以分析语义分析器的性能．实验结果表明,分析器在非限定领域中表现出了较好的性能,分析正确率与中文句法分析器基本相当。     

面向数据的句法分析消歧

面向数据的分析技术(Data-Oriented Parsing,DOP)是一种概率分析策略,其概率模型的主要目的在于为一个给定的句子找到最可能的分析,即分析消歧。实际上,有关算法计算复杂度的大量研究证明,该类消歧问题属于NP-完全问题。因此,为有效实现最可能的分析,国外学者提出许多近似分析算法。本文主要论述在 DOP 框架中,基于 Monte Carlo 方法找到最可能分析的近似分析算法,并说明该方法可在合理的算法时间代价范围内实现,而且在统计上受控,以确保所获得的近似解确实对应着分析消歧后的精确解。     

句法分析中基于词汇化树邻接语法的数据增强方法

句法分析是自然语言处理的基础技术,主流的由数据驱动的神经网络句法分析模型需要大规模的标注数据,但是通过人工标注扩展树库成本很高,因此如何利用现有标注树库进行数据增强成为研究焦点。在汉语句法分析的数据增强任务中,对于给定的标注树库,要求数据增强所生成的句子满足如下条件：第一,要求生成句具有多样化且完整的句法树结构;第二,要求生成句具有合理的语义。对此,我们首次提出基于词汇化树邻接语法的数据增强方法。针对第一个需求,该文设计实现基于词汇化树邻接语法的词汇化树抽取算法与句法树合成算法,基于该语法可以在句法树之间进行“接插”和“替换”的操作,从而推导生成新的句法树,并且用语言学的知识保证生成句符合语法规则且具有完整的句法树结构。针对第二个需求,该文利用语言模型对生成句进行语义合理性评估,选取语义合理的句子作为最终的增强数据,从而获取高质量的标注树库。我们以汉语为例开展研究,在汉语树库CTB5上进行句法分析的数据增强评测实验。实验结果显示,在小样本(CTB5的20%)实验中,通过该方法得到的增强数据使依存句法分析和成分句法分析的精度分别提高1.39%和2.14%。在鲁棒性实验中,该文通过构建扩展...     

基于最大熵模型的汉语依存分析

采用最大熵模型实现中文依存语法的分析。用自底而上的方式构建语句的依存关系树，构建过程每一步在向左连接、向右连接以及不连接3种动作选取其一。用最大熵原理判断每个动作的概率，得到依存树中各边的概率，然后找出具有最大概率的依存关系树。实验结果表明，该模型具有较好的分析精度。目前，该模型已被应用于基于自然语言的信息检索项目中。     

基于桥连接的词典学习方法的语义解析

现阶段的语义解析方法大部分都基于组合语义,这类方法的核心就是词典。词典是词汇的集合,词汇定义了自然语言句子中词语到知识库本体中谓词的映射。语义解析一直面临着词典中词汇覆盖度不够的问题。针对此问题,该文在现有工作的基础上,提出了基于桥连接的词典学习方法,该方法能够在训练中自动引入新的词汇并加以学习,为了进一步提高新学习到的词汇的准确度,该文设计了新的词语—二元谓词的特征模板,并使用基于投票机制的核心词典获取方法。该文在两个公开数据集(WebQuestions和Free917)上进行了对比实验,实验结果表明,该文方法能够学习到新的词汇,提高词汇的覆盖度,进而提升语义解析系统的性能,特别是召回率。