基于大规模语料库的句法模式匹配研究

摘 要：通过大量记录的正确处理实例的分析过程和结果，在句法分析时，搜寻近似实例或片段，匹配相似语言结构和分析过程，这样的句法分析体现了“语言分析依赖经验”的思想。基于这样的思想，本文提出了一种基于模式匹配的句法分析的方法，即从大规模标注语料树库中抽取出蕴含的句法模式，构建模式、子模式及其规约库，句法分析的过程转化为模式匹配和局部模式转换的过程。实验表明句法分析的各项指标都比较理想，尤其是处理效率很高，平均句耗时0.46秒(CPU为Intel双核2.8G，内存为1G)。

关键词：计算机应用；中文信息处理；句法分析；模式匹配；句法树库

中图分类号：TP391　文献标识码：A

1　引　言

基于语料库的统计概率模型是句法分析的重要研究方向，代表性的有概率型上下文无关模型(PCFG)基于历史的分析模型、分层渐近式句法分析模型、头驱动的统计句法分析模型等。统计方法实质是一个评价句法分析结果的概率评价函数，即对于一个输入句子s和它的句法分析结果t，给出一个条件概率P(t|s)，并由此找出该句法分析模型认为概率最大的分析结果，即找到argmaxP(t|s)，句法分析问题的样本空间为S×T，其中S为所有句子的集合，T为所有句法分析结果的集合。统计方法的主要问题是数据稀疏问题、忽略上下文结构信息、需要大量计算等。

基于语料库的另一种方法是面向数据的分析(Data Oriented Parsing，DOP)技术，它从句法标注语料库中抽取所有任意大小规模和复杂结构的片段，通过对片段的组合操作来实现句法分析，然后考虑所有结果的概率大小，来选择最优结果。DOP模型较好地利用了语料库中蕴含的知识，体现了“语言分析依赖经验”的思想，缺点还是没有充分利用上下文信息(片段间相互独立)，注重片段而忽略了整体，另外片段组合与概率计算的工作量也很大。我们的基于模式匹配的句法分析与DOP类似，都是建立在“语言分析依赖经验”的思想基础上，但在算法实现上不同，借鉴了文法转换中的部分理论和技术，并在句法分析中注重整体匹配、局部转换。

2　基于模式匹配的句法分析

2．1 基本思想

在计算机上输入汉语时，单个的汉字输入既慢又易出错，词组的输入则又快又准，究其原因是词组的重码率低，减少了歧义发生率，基于模式匹配的句法分析与此类似，模式即类似于词组，当然分析处理要复杂得多。在从句法标注语料库中获取了大量句法模式的基础上，不再如传统的概率模型，计算各种组合的最大概率，而是大处着眼，快速识别处理对象中包含的句法模式或隐含的近似句法模式。

模式匹配的句法分析方法与传统统计句法分析方法在处理方式上的不同，前者强调整体优先，在大块匹配的基础上，对局部没有能直接匹配上的部分做一定的转换处理，而后者是基于局部概率的计算，由点到线；前者是基于短语的(句法短语)，后者是基于词的。基于模式匹配的句法分析是对人的处理方式的模仿(人做句法分析可以左看右看，把握整体，注重平衡，因而是二维的)，可充分发挥大规模语料库蕴含的处理各类句法现象的能力。

2．2　句法模式的定义

定义1：对于一个句法树，从左向右画一条只穿过树中节点的线，这条线上的节点如果满足以下约束条件，则其节点序列即为一个句法模式。

这条线上的节点是树上全部节点D的一个真子集C，并且(1)C中没有一个节点处在由C中其他节点开始的任何一条后继节点路径上；(2)D中没有其他节点可以加入c而不违背规则(1)。

如图1所示，虚线上的节点序列是句法树S(dj(np(n(奥里诺科河))vp(pp(p(在)np(r(哪儿))))))中的几种模式，其中(d)为非法模式，因为该序列中节点p是节点vp的子孙，不满足模式定义约束。按定义，该句法树中共包含25个模式。模式数量按几何级数增长，1个包含20个词的句子，其模式数约为500多万，故构建数据支撑平台是一个海量数据处理过程。

一个模式的规约是句法树中该模式与树根节点之间的部分，图1(c)中模式为(np p哪儿)，对应的模式规约为S(dj(np vp(pp(p np(r(哪儿))))))，如图2所示。从本质上讲，句法分析的过程是从叶子节点向根节点过渡的过程，而模式及其规约正是对句法树库标注过程的动态记录，基于此的句法分析规约速度快，处理效率高。

2．3　模式的抽取

从句法树库的每一个树及其派生的子树中，抽取所有的句法模式，并记录对应的规约。该算法应用于后台处理，是构建数据支撑平台的基础。抽取算法基于句法解析函数及其链表表示，在算法中，结构树在内存中以中序优先的形式存储。模式抽取算

算法结束后List中的内容即为所求的句法结构s中包含的所有模式序列。

2．4　模式匹配及其局部转换

定义2：设模式P＝a1a2…ai…an，处理对象S＝b1b2…bi…bm，其中a、b为节点(即词或词性标记)，若m＝n，且ai?＝bi，i∈[1，m]，则称模式P与S完全匹配。

判断待处理语句是否与模式库中的模式相匹配，则成立相应的模式规约即为句法分析结果；否则进而判断近似模式(即模式中有部分不匹配，近似模式匹配不同于多模式匹配，因为待处理语句和模式中任何部分之间都可能进行匹配)。

定义3：设模式P＝a1a2…ai…an＝P1P2…Pk，其中P1＝a1a2…ai，P2＝ai+1 ai+2…，…，Pk＝ai+1at+2…an，1≤i≤≤t；S＝bi+1bi+2…bi…bn＝S1S2…Sk，其中S1＝b1b2…bi，S2＝bi+1bi+2…，…，Sk＝bt+1bt+2…bn，1≤i≤t，Pj与Sj不同时为空，若Pj ＝Si，则称其为P、S中的相同子模式，包含若干相同子模式的模式P，即为S的近似模式。

根据定义近似模式有多种取法，不同顺序不同取舍会得到不同的近似模式，例如P＝ns np vp unp vp，S＝ns u mp np vp vp，P与S之间存在多种模式对齐方式，如下所示。

近似模式的取舍按最大匹配个数(长度)优先和分布平衡优先的原则，兼顾统计句型的判断(这里的句型是从语料库中统计出来的出现频率较高的句法结构，其叶子节点序列也是一个模式，我们称这样的模式为强模式，频率高，有较强的吸附性，即它是很多模式的上位模式)。近似模式的计算公式如下：

其中，Len(s，p)为计算处理对象s与模式p中的节点匹配度，N(s)为s中的节点数，N(p)为p中的节点数，N＇(s，p)为s与p中共同出现的节点数目；Ord(s，p)为计算s与p中相同节点的顺序相似度，MaxRev(s，p)表示共同节点在p中的自然数序列的最大逆序数，Saq(s)表示共同节点对应在s中的位置构成的自然数序列，Rev(s，p)表示Seq(s)的逆序数，公式(2)反映出s与p中的共同节点的顺序越接近，则s与p越近似；Patt(p)给出句型p的频率，如果p不是句型，则Patt(p)＝0；AP为所求的最优近似模式，P为模式集合，α1，α2，α3是对应的计算权重。

定义4：设模式P1＝a11a12…a1i…a1n和模式P2＝a21a22…a2j…a2m是同一棵句法树上模式，n＜m，a1i或是P2中的某个节点，或是P2中某个或某些节点在句法树中的祖先，则称P1是P2的上位模式。如图2，模式np pp即为模式np p np的上位模式。

定义5：设P是S的近似模式，P＇是P的一个上位模式，局部转换是指对S中与P不同的部分进行一定的规约处理，得到S＇，使得S＇＝P＇。

对近似模式中不匹配的部分进行特别的转换和归并处理的目的是得到一个完整的匹配模式，如图3所示，待处理对象S(a1 a2 a3＇a4 a5 a6a7)与模式P(a1 a2 a3 a4 a5 a6 a7)中的a3不能匹配上，则试探包含a3的上位节点b，且与模式P距离最近的上位模式P＇(a1 a2 b a5a6 a7)，若处理对象S中局部转换a3＇a46成立，则模式P＇即为所求完整模式。

2．5　系统处理流程

模式匹配的句法分析是建立在大规模语料库包含的海量句法模式的基础上，其分析质量和处理性能，取决于整个句法分析系统的各个环节，可以分为数据和算法两大方面，数据是支撑，数据量愈大，句法模式涵盖面愈广，处理的精度和效率愈高，算法则是如何管理、调度大量数据，以及如何利用和发挥出模式库的句法分析能力。

图4是句法分析的系统结构图，其中数据支撑平台是后台实现的，处理的数据量较大，句法分析是实时处理，由于有后台大量的索引及其快速匹配算法，所以有较高的分析效率。

预处理主要是词法分析工作，模式匹配成功则直接进行模式规约处理，否则需要抽取最优的近似模式，进行局部转换处理，得到近似模式的上位模式。系统的复杂性涉及时间和空间两个方面，主要策略是以空间换时间，即建立大量多层次索引换取句法分析的高效率。

3　实验结果及其分析

我们以TCT973树库作为实验的资源，从其中29 000余句句法树中抽取所有不重复的句法模式，构建大规模的模式库及其相应的规约库，模式总数大约8百万条。从29 000中分别随机抽取百科、学术、新闻、应用类100句，抽取长句(词个数大于40)和短句(词个数小于20)100句，做封闭测试，再从29 000句以外的句子中抽取1 000句做开放测试，计算机CPU为Pentium2.8G双核，内存1G.实验结果如表1所示。

实验的主要目的是检验基于大规模树库的模式匹配句法分析器的分析效率和分析结果的准确度。其中，对分析结果准确度的评估主要依据了以下几个性能指标：(1)标记正确率(LP)；(2)括号召回率(LR)；(3)交叉括号数(CBs)；(4)没有括号交叉的情况(0CB)；(5)最多有一个括号交叉的情况(1CB)；(6)最多有两个括号交叉的情况(2CB)。有关它们的详细定义，请查阅PARSEVAL评估标准，句耗时指批平均每句耗费的分析时间，单位为秒。

总的实验结果令人满意，准确率召回率等各项指标较文献[11]公布的同类测试有明显的提高，尤其是分析效率，传统的一遍Chart分析的方法的时间复杂度为句子长度的三次方，采用基于模式匹配的句法分析方法，由于在后台建立了大量的多级模式索引库，且在匹配算法上采取了规约深度优先、规约总次数最少优先等原则，所以分析的效率非常高，平均句耗时为0.46秒。

从实验结果中可发现，短句的分析没有长句的好，这和模式匹配的算法有关，短的语句，一旦匹配上错误的模式，各项分析分析指标的得分就会很低；长的语句，分析单元之间的约束较强，其存在多种分析结果的可能性相对小，即使在局部可能存在分析错误，总体分析结果也不会太差，故反而能够取得较好的平均结果。模式匹配的句法分析也有歧义组合的问题，如对于“货币学派/n及其/c政策/n主张/n”，其词性序列是“n c n n”，在模式库中有两种规约与之对应，分别为np(np(n c n)n)和np(n cnp(n n))，目前对于一个模式多种规约的情况，采用概率优先，即同等情况取概率大的规约，以后将考虑不同规约与上下文的关系，进行语境相似度计算。

4 结　论

基于模式匹配的句法分析的思想基于这样的一个事实，即对一个语句进行句法分析，总可以在大规模树库中找到与之相应的完整模式，或模式片段的组合，也就是说句法树及其子树中蕴含了大量的句法分析的知识，我们要做的事就是如何从海量的句法模式库中，快速搜寻到合适模式。基于模式匹配的句法分析建立在海量模式库的基础上，大块处理，利用分析单元之间的相互约束，降低了歧义发生的概率，实验结果较为理想，尤其是处理效率非常高。

在今后的改进中，将引入局部优先算法思想，提高短结构分析的正确率，同时引入标点符号的处理，减少由于跨标点引起的匹配错误，另外还将融入一定的语义处理，提高对词与词之间的搭配关系的把握精度。