不连续语法：局部成本函数处理复杂性分析和优化问题 O(nlog4n)

理论计算机科学电子笔记53（2001）网址：http://www.elsevier.nl/locate/entcs/volume53.html17页不连续文法MatthiasT rautner Kromann1;2哥本哈根商学院计算语言学系，丹麦摘要经过简要的调查不连续语法（DG），我们提出了本地成本函数作为一个概括的违法约束OT，概率PCFG，和分布式竞争模型的处理时间。我们演示了如何在DG中使用本地成本函数来编码词序，着陆点，岛屿，协议和选择性限制，以及词汇频率和语用偏好的违规约束。将句法分析转化为一个优化问题，在这个优化问题中，需要搜索大量的部分句法分析来寻找最小代价的解。我们提出了一个基于局部搜索的DG启发式句法分析算法，在树深度和岛约束条件下，最坏情况复杂度为O（nlog4n），在没有任何约束条件下，最坏情况复杂度为O（n5）所提出的算法在存在局部歧义的情况下工作，对广泛的不连续词序现象（如主题化、相对化、提取、加扰和不连续AP）进行正确的分析，并且在花园路径句子上失败，就像人类一样。1不连续语法不连续语法[10]（或DG）是一种句法形式主义，最初被认为是中心语驱动短语结构语法[15]，政府约束[5]和德语依存语法[6]之间的综合。随后，它借鉴了优选论[8]、树邻接语法[1]、1 电子邮件：mtkromann@ieee. org。网址：www.id.cbs.dk/mtk/dg[2]我要感谢我的论文导师卡尔·维克纳教授，这篇论文是献给他的。谢谢理查德·哈德森，唐·C。Mitchell、Owen Rambow、Lars Konieczny、Line Mikkelsen、StenVikner、Sabine Kirchmeyer-Andersen和Alex Klinge进行了富有成效的讨论，并感谢两位匿名评论家提出了非常有价值的意见。这项工作是由丹麦人文科学研究委员会的赠款。c2001年由Elsevier Science B出版诉 在CC BY-NC-ND许可下开放访问。克罗曼2词语法[7]，以及心理语言学[4]。通过这些共同的起源，DG也与词汇功能语法[3]和较新的依存理论[9]分享了一些想法。1.1DG中的图在不连续语法中，语法图是无环的和有向的，具有表示单词和语法关系的类型化节点和边。节点和边以继承层次结构组织，下面部分显示了边。表面边缘深土地comp当地ext填充subjdobj约布日沃布日adj在绘制语法图时，通常不指定边类型。相反，主边缘类型用以下箭头之一表示：补偿边缘边缘平台边短语符号DG图的示例如下所示为了便于标记，DG图像短语结构图一样绘制，在每个单词上方绘制短语符号（尽管形式上，短语符号和单词只是一个节点）。此外，如果内部结构与讨论无关，则有时会将诸如“实现”之类的短语NPNP APAPAPVPVPVP硬计划-实施DG图硬计划-实施地面采油树硬计划-实施深树图中的每个节点（根节点除外）都有一个由表面边编码的着陆点，以及一个由深边编码的调控器。该节点必须作为其登录站点的登录节点和其调控器的从属节点进行许可。依赖项可以是补集，由它们的调控器选择并充当它们的语义参数;也可以是补集，选择它们的调控器并充当它们的函子。为了使图是良构的，表面边必须形成连续的表面树，深边必须形成可能不连续的深树，并且两棵树必须满足向上深移动原则，该原则要求单词克罗曼3登陆地点以主宰字31.2DG中的词汇在词典中，每个类型都由一个词法条目定义，该词法条目指定其直接超类型的有序列表，并声明其变量。默认情况下，变量声明和值从超类型继承。变量被标记为原子值或集值。原子变量的值要么是本地指定的，要么是从定义它的第一个超类型继承的（即默认优先级继承）。一个集值变量的值可以用不同的操作符局部指定：v = A用于将变量v的值设置为集合A，而v = +A B将v的值设置为集合A加上超类型中v的所有值减去集合B。在下面的简化示例中，动词被定义为类型词的子类型，其中变量comps具有设置值[subj：noun]（也就是说，动词默认许可带有边缘类型主语的类型名词的补语）。Eat被定义为动词和动词（现在时）的子类型，它对于comps的值是继承后的[subj：noun，dobj：noun]（也就是说，它也将一个名词作为直接宾语）。雨将覆盖的继承设置为comps[subj：it]。type（verb，[word]，[comps =[subj：noun]]）.type（pres，[flex]，[]）.type（eat，[verb，pres]，[comps =+[dobj：noun]]）.type（rains，[verb，pres]，[comps =[subj：it]]）.如果s和t是类型，则s t被称为s和t的联接，并且被定义为具有s和t作为其超类型的类型类型规范可以是类型名，也可以是形式为“+，”的组合你好，, and jwhere和运算符isa（t;）用于测试类型是否t满足类型规范。它递归地定义为：是a（t;s），如果类型s在类型层次结构中支配类型t是a（t+），如果isa（t）和isa（t）是a（t;）如果isa（t;），但不是isa（t）是（t;j）如果isa（t;）或是（t;）每个词和词类必须列出其许可的补结构、附属调控器、着陆节点和成本函数。下面是形容词hard的一个简化例子，它接受以for为首的短语作为介词宾语，接受以不定式to为首的短语作为动词宾语，可以作为amod附加语附加到名词上，只接受自己的局部从属关系作为着陆节点，并且具有惩罚左着陆补语高度不合语法的代价函数。3在曲面运动中，一个词这比深度移动更受限制，因为表面树可以被视为深度树的扁平经典HPSG中的斜线传播和GB中的运动对应于地表运动。有趣的是，Bouma，Malouf和Sag[2，x3.1]最近提出改变HPSG内的斜线传播，使其对应于深部运动。克罗曼4type（hard，[adjective]，[comps = [pobj：for，vobj：to inf]，adjs =[amod：noun]，land =[word+local]，costs = [1000 * left（comp）]]）。为了简单起见，我们忽略了词典如何编码歧义、习语、补语和附加结构的语义以及授权填充语（用于满足双重依赖关系的语音空词，如相对化角色或共享主语）。2成本函数与优选理论一样，DG使用可违反的约束，以使分析对语音错误和意外结构更鲁棒。然而，DG约束不同OT约束具有非负成本，而不是排名，并通过本地化，即，与特定节点的图形。另一个不同之处在于，DG中的加权约束是在定义良好的约束语言中指定的，该约束语言可以表达广泛的语言约束，但通过要求所有约束都是从图中节点的最近邻居本地可计算的来事实上，大多数语言约束可以计算本地是DG的设计，其中一个节点的总督，着陆点，补充，补充和着陆节点构成其邻居的一个重要后果2.1运算符定义DG约束定义的成本函数，返回一个成本，衡量的次数，违反了语法条件，权衡其严重性。成本函数用下面所示的实值和集值算子表示。每一个操作符都是在图G中的一个词w的上下文中陈述的。DG定义了以下集值算子（我们让n表示节点n与其所有父边的类型连接）：this：= fwg其中w是上下文定义的单词。dep（t）：=所有依赖于w的d的集合，使得d 是T型血left（t）：=所有w的左着陆节点n的集合，使得n 是T型血right（t）：= w的所有右着陆节点n的集合，使得n 是T型血gov（t）：= fgg如果w有governor g和g 有类型t，否则为。lsite（t）：= n如果w有着陆点l，且l 有类型t，否则为。island（t）：=所有n的集合，使得e是具有类型t的w的依赖边，以及n是从其调控器到其着陆点的路径包括e的节点。se m（n;t）：=fng，如果节点n的语义是类型t，否则不成立。我们将这些算子的定义扩展到集值参数，（X1;：;Xn）：=[（x1 ;：;xn）2X1Xn（x1;：;xn）克罗曼5对每个集值算子，用集值函数X1;：;Xn.此外，我们定义以下整数值运算符（其中0对应于假，1对应于真）：n 1 n 2：= 1，如果节点n1跟随节点n2，否则为0。x=y：如果x和y相同，则=1，否则为0。x6=y：如果x和y不相同，则=1，否则为0。isa（n;t）：=1如果节点n具有类型t，否则为0。dist（n）：=w和节点n之间的距离，以插入单词的数量来衡量。这些运算符通过定义以下内容扩展到集值参数（X1;：;Xn）：（x1 ;：;xn）2X1 ：Xn（x1;：;xn）对于每一个具有集值参数X1;：;Xn的整数值算子，最后，我们定义以下整数值运算符（其中+表示实数的加法和乘法）：jxj：=x的绝对值，定义为x的基数，如果x是一个集合。且（x 1;：;x n）：= jx1jjx n j或（x 1;：;x n）：= jx1j ++jx n jnot（x）：如果jxj =0，则=1，否则为0。在下文中，我们将演示如何使用上述运算符对各种语法约束的成本函数进行编码，即，表达什么算作违反约束。在实际词典中，成本函数必须通过将其乘以固定的非负成本来分配相对权重。然而，为了简单起见，我们假设所有的成本函数都有单位成本。2.2缺失的边缘：根和强制依赖项由于我们想要一个完整的分析，而不是部分的分析，一个词应该强加一个丢失的着陆点或总督的成本。这可以通过以下方式实现：not（lsite（any））：缺少着陆点not（gov（any））：缺少总督在DG中，所有家属默认都是可选的，因为没有成本与他们的缺席相关联。然而，补充和补充可以通过对它们的缺席征收费用而成为下面是一个英语动词resident的例子：not（dep（subj））：缺失受试者not（dep（locadv））：缺失位置状语克罗曼62.3违反词序一个着陆点有一个左字段和一个右字段，其中包含其着陆节点。下面列出了一些在右言语领域的违规行为。在丹麦语和英语中，这些违规行为总是不合语法的，必须付出高昂的代价。在德语中，它们只被标记，必须被分配一个较低的成本。right（subj）>right（land）：主语前面有任何落地节点right（iobj）>right（compsubj）：间接宾语前面有任何不是主语right（dobj）>right（compsubjiobj）：直接宾语前面有任何既不是主语也不是间接宾语的补语在丹麦语和德语的V2-order动词中，左域必须包含一个补语，或者一个或多个补语。违规行为可以通过以下方式进行测试：not（left（land））：没有着陆节点左（comp）6=左（地）：有一个补语和一些其他从属语2.4岛屿限制虽然特定的岛屿限制并不适用于所有语言，但必须有可能在DG中说明这些限制下面列出了主要的岛约束，说明了违反条件及其应用的词类。动词中的岛（subj）：通过主语边缘（主语条件）进行提取名词中的岛（vobjjrel）：提取通过名词中的关系从句或动词补语的边缘发生（复杂NP约束）和动词中的（sem（this，wh），island（any））：提取通过wh标记的动词中的任何边发生（Wh-岛条件）单词中的岛（形容词）：提取通过任何单词中的附属边缘发生（附加岛约束）和动词中的（gov（that），dep（subj+ext））：主语是从由补语（补语间隙约束）支配的动词中提取的。2.5协议可以在以下违规条件下测试一致性isa（this，subj-nom）innoun：主语没有主格标记isa（depsubj），neut）6=isa（dep（adjecti v e+spred），neut）inver b：主语和主语表语有不同的中性标记2.6选择限制与语用为了实现选择性限制，我们假设语义解释被组织在一个类型层次结构中，克罗曼7这样我们就可以测试它们是否匹配语义类型规范。克罗曼8;;sem（dep（subj），-human）in verb：主语不表示人和（isa（this，locadv），sem（this，-place））在名词和介词中：充当地点状语的名词或介词不表示地点更一般地，成本函数给出了一种考虑语法图的语义和语用可解释性的自然方式：简单地将语义或语用模块计算的成本添加到其他成本。2.7词距心理语言学的证据表明，人类句法分析中偏好低依恋[4]。在DG中，这可以用公式表示为节点与其登陆站点和调控器之间的接近度偏好：dist（gov（any））：在word和governor之间插入的单词数。dist（land（any））：单词和登陆点之间的插入单词数。2.8词汇偏好和概率单词通常有不同的阅读频率。在DG中，通过为每个表单分配固定的成本，频繁表单可以优先于不频繁表单。成本可以合理地选择为logP（w），其中P（w）是单词形式w的先验概率。那么，图G中的总词汇偏好成本将减少到log（w） =log（w），即，假设统计独立性，词序列在负对数变换下的概率两个字之间。类似地，我们可以将固定成本附加到互补结构，从而导致在基于依赖性的PCFG中计算的树的概率，但是在负对数变换下。更一般地说，概率可以用来估计任何违规条件的2.9成本解释由于成本可以被解释为负对数概率，因此DG可以被视为PCFG语法的基于依赖性的概括[11]。DG也可以被看作是优选论的推广，因为OT中的约束违反在成本方面有一个明显的解释，如下所示：令r表示从OT约束到非负整数的秩函数，其通过将0分配给最低秩约束、将1分配给次低秩约束等来定义。设V（n;c）表示在图中的节点n处违反OT约束c的次数然后，对应于节点n处的约束c的成本多项式可以被定义为函数C（n c）= V（n c）Xr（c），其中X是多项式变量。所有局部成本多项式的总和对OT违规的总数及其秩进行编码。 此外，OT克罗曼96简化为多项式的标准阶（即，如果f g的首系数为正，则f> g）。因此，OT约束可以被视为具有多项式值成本的成本函数，通过将X设置为大的正数，可以将其减少为实值成本最后，DG中的启发式解析算法可以根据分布式竞争模型进行解释，如[17]。通过对这些模型的稍微重新表述，我们可以将人类解析解释为并行计算的不同解析操作之间的顺序竞争。第一个完成约束检查的操作获胜，然后用一组新的操作继续竞争。也就是说，成本也可以解释为处理时间。3优选性分析解析可以被看作是一个搜索问题，在这个搜索问题中，在给定某种衡量语言可解释性的代价函数的情况下，搜索某个输入的潜在解析空间以寻找最优解找到一个保证全局最优解的问题--也就是精确解析的问题--在DG，4中可能像大多数其他形式主义一样难以处理[5]然而，从纯语言学的角度来看，找不到有效的精确解析算法并不值得担心，因为我们从花园路径句子的心理学实验中知道，人类的解析并不精确[4]。因此，语言学的兴趣在于寻找快速的启发式解析算法，准确地模拟人类解析及其缺陷，而不是解决精确解析的问题。从工程的角度来看，精确解析也是不期望的，因为无法对人类解析进行建模可能导致应用程序误解人类输入或生成人类无法正确解析的句子。3.1使用本地搜索进行解析许多NP难优化问题，包括旅行推销员问题，可以用局部搜索相当成功地解决[14，ch.19]。局部搜索是基于一个简单的想法，如果我们可以定义一个小邻域周围的每一个4DG中的图表解析是不切实际的，因为一个n字的字符串有2n 1个不连续的子串，而对于像CFG这样的连续形式主义，图表解析器必须存储至多1n（n+1）（n+ 2）个精确的DG解析可以被证明是NP难的，如果 语法被认为是输入的一部分，因为在这种情况下，从最大可满足性问题[13]到精确DG解析很容易简化。5NP难形式主义包括具有无限制约束的最优理论[18]，随机树替换文法和面向数据的解析[16]，LFG [12]和基于约束的形式主义，如HPSG。 CFG和TAG是例外，因为它们可以分别在O（n 3）和O（n6）时间内解析，尽管存在它们无法解释的语言现象[1]。此外，用于CFG和TAG的图表解析器创建可以包含指数数量的解析的打包图表（例如， 考虑语法X！ X X和终端规则X！ x）。因此，如果在CFG和TAG之上给出一个在语言学上合理的代价度量（比如说，一个检查语义和语用可解释性的度量），那么可以想象，在CFG和TAG中的精确最优性分析将是NP难的。克罗曼10节点，那么我们可以通过从任何解开始，在其邻域中挑选最佳解，并重复该过程直到我们找到局部最优，希望最终的局部最优将是全局最优或接近最优的。如果有合适的问题和合适的社区，这种策略可能会非常成功。DG中的解析算法是基于局部搜索的。搜索空间被定义为一个句子的所有部分分析的集合，而解空间由包含所有输入词的所有部分分析组成。 因此，即使DG解析失败，它也将返回输入的最大部分解析。起始点是空解析，部分解析的总成本定义为解析中单词所施加的所有违规成本之和这给出了最优解析的算法：1. 设置G：=空图。2. 设G0：= G的邻域内的n y最优图.3. 如果G的代价小于G0，且包含所有的输入命令，则判定G是满的.4. 设置G：=G0并重复步骤2。每个部分解析周围的局部邻域是根据一个集合定义的基本的解析操作，从现有的图计算一组新的图。如果输入中有任何未读单词，则读取下一个单词并将其添加到图中的操作始终是有效的解析操作。恒等映射从来都不是一个有效的解析操作，也就是说，一个图从来都不包含在它自己的邻域中。理想情况下，解析操作必须选择得足够强，以从人类从次优分析中恢复过来，并且足够弱，以陷入人类陷入的次优分析优选地，操作也必须没有理由假设所有人都有相同的解析操作集。相反，人类似乎在接触到花园路径句子后会修改他们的解析策略，因此有理由假设解析操作是学习的，因此不同的人和语言社区之间存在一些差异。当测试一个最优解析器时，我们需要区分语法失败和解析器失败。如果由语法定义的成本度量是错误的，则出现语法故障，这是因为不期望的分析被语法认为是最优的，或者期望的分析被认为是非最优的。当解析器无法找到最佳分析时，就会出现解析器故障。显然，我们不能因为任何语法错误而责怪解析器，但是解析器的错误是对解析器的严重反证，除非人类也遇到同样的问题。3.2解析操作只向图中添加新节点或边的解析操作称为单调的，而从图中删除边的解析操作称为非单调的。图中没有着陆点的节点称为表面根，没有调控器的节点称为深根。DG初步提出了六种解析操作：克罗曼113533：subj5a：subj5b：dobj有三种不同类型的单调操作：lex-operations将下一个未读单词添加到图中，land-operations将着陆点边缘添加到表面根，dep-operations将总督边缘（可能还有着陆点边缘，如果还不存在的话）添加到深根。land-operation用于在调控器还不可用的情况下将节点附加到着陆点，例如主语临时着陆在补语上，直到遇到其控制动词。在下面的德语示例中，步骤1、2、4和6是lex-operations，步骤3是dep-operations，步骤5是land-operations。VPVPNP NPVPVP7NP NP1 2 4 6 1 2 4 6音乐家们将演奏华尔兹舞曲音乐家们将演奏华尔兹舞曲此外，有三种不同的非单调修复操作，分别涉及一个，两个和三个节点。Repair 1-操作将一个调控器和一个新的着陆点分配给深根。在上面的例子中，右手边显示了步骤7中的修复1操作的结果，其中来自步骤5的直接宾语修复2-操作通过将调控器的另一个依赖项推到一边来将调控器和着陆点分配给深根因此，修复2操作涉及两个节点。下面给出了对应于“音乐家有华尔兹”的主题化德语句子的示例。在步骤5的修复2-操作中，VPNPNPVPNP NP1 2 4 1 2 4华尔兹有音乐家华尔兹有音乐家华尔兹有音乐家华尔兹有音乐家Repair 3-操作通过将调控器的两个现有依赖项推到一边，将调控器和着陆站点分配给深根，使其中一个成为旧调控器的新下面的例子是上述解析的继续：在步骤7中，修复3操作将“die-Walzer”作为“haben”的直接宾语推到一边，克罗曼125a：subj5b：dobj7b：subj快！G“die Musiker” is analyzed as the object of “erfreuen” in stepVPVPNP NPVPVPNP NP1 2 4 6 1 2 4 6华尔兹舞曲使音乐家们感到高兴华尔兹舞曲使音乐家们感到高兴花园路径语句包含了人类解析器无法自由使用的修复操作。例如，在下面的经典例子中，在步骤7a中，VP35NP PPVPVPNP7bVPPP1 2 4 6 1 2 4 6一匹马跑过谷仓摔倒了一匹马跑过谷仓摔倒了影响图中最多k个节点的解析操作（通过向图中添加节点或通过更改其调控器和着陆点）称为k-更改操作。显然，对于足够大的k，任何解析操作都是k-改变操作.特别地，花园路径示例中所需的修复操作是2-改变操作。一个k-change操作的时间复杂度为O（n2k），所以如果我们想要解析几乎是线性的，k-change太昂贵了。然而，可以想象的是，人类使用2-change和3-change作为更高级别的修复操作，如果所有正常的解析操作都失败，则仅将其用作最后的不可靠手段。这也可以解释人类如何学习一组解析操作：最初，他们必须求助于2-change和3-change操作来找到最佳解析操作。但是过了一段时间，他们注意到最优操作中的一种模式，这使他们能够制定更有效的解析操作类别，例如land，dep，repair1，repair2和repair3。3.3解析操作的形式化定义在下文中，令G + E表示图G加上E中的边或字，令GE表示G减去E中的边，并且令GE表示G加上E减去G中与E中的边不相容的所有边（回想每个节点最多有一个g over nor或着陆点）。 再来一次，我们走吧！l表示节点n，其表面边缘连接到着陆点l，且深边缘连接到调速器g。在定义不同的解析操作之前，我们首先需要定义以下函数：7a7c57a克罗曼13快！L快！L的情况。快！GG快！GG快！L快！Lg00DGlands（G）：=所有r的集合，使得r是深根，l是接受r作为局部或外部着陆节点的相邻着陆点（假设我们删除G中r的任何现有着陆点），相应地将表面边缘k设置为local或ext。直觉：返回图中深根的所有潜在根登陆站点配置。lgovs（G）：=所有rg的集合，使得r快！L在陆（G）中，g = l，如果=local，并且如果=ext，则在深树中g被l支配。直觉：返回图中所有深根的所有潜在根登陆站点调控器配置。dep s（G;d;g）：=所有d的集合！g使得g接受d作为具有补边的补，或者被d接受作为具有附属边的附属调控器。直觉：返回给定依赖项的所有潜在依赖边还有州长block s（G;d;g;B）：=所有补边d的集合！g（GB;d;g）不在deps（GB0 dg），对B的一个ny真子集B0. 直觉：返回给定依赖项和调控器的所有补充角色，这些角色被给定的依赖项边集阻塞。现在，我们可以定义局部解析操作，指定图G周围的邻域，如下所示：lex（G）：=fG0g使得G0=G+fwg其中w是n个未读w阶.直觉：查找下一个未读单词。landd（G）：=所有G0的集合，使得G0=G+r！其中r是的表面根，G，！l在land s（G）中，且=ext。直觉：为一个表面根找到一个有效的着陆点。de p（G）：=所有G0的集合，使得G0=G+r！其中r是G的深根，！l在lgo vs（G）中，且r！g在dep s（G;r;g）中。直觉：找到有效的着陆点站点和调控器进行深根。repair 1（G）：G0满足G0=Gr！其中r是a深根在G与现有的着陆点边缘不同的X！ 我，我！l在lg o v s（G）中，且r∈ ！g在dep s（G;r;g）中。直觉：为已经有另一个着陆点边缘的深根找到有效的着陆点和调控器。repair2（G）：=所有valid图G00 0的集合，使得G00 =Gd0！你好！g;G000 =G001000！l 001000！g00其中rg在lgovs（G）中，d≠0！g在G中，r是！g在块s（G;r;g;fd≤0！gg），！l00 单位为lgovs（G00），和d00！g00 在deps（G）中00的情况。 ）的。 直觉：找到一个总督和着陆点的一个深根推开总督的另一个依赖，找到一个新的总督和着陆点。repair3（G）：=所有valid图G00 0的集合，使得D00克罗曼14快！L！G快！L0G=Gd0！g！你好！g; G =G0+c0;G000 =G001000！l 001000！g00其中rg在lgovs（G）中，d≠0！g和c的！g在G中，r是！g在块s（G;r;g;+d00克罗曼15！l0000f0！g;！gg），c0！g以deps（G;c;g）为单位，dg00以lgovs（G）为单位），和d00！g00在deps（G00;d;g00）中。直觉：通过推开调控器的另外两个依赖者，为go vernor和着陆点找到一个深根，在同一个调控器中给第一个新的依赖者角色，给第二个新的调控器和着陆点。注意，解析最多需要3n个操作，因为每个操作都会增加图中的单词和边的数量，而图的边界是3n。3.4解析复杂度为了估计解析器的最坏情况复杂度，令r表示图中根的最大数目，h表示最大高度，l表示可能的根着陆点对的最大数目，s表示在着陆点下搜索的最大调控器数目，d表示词典中指定的依赖项与其调控器之间的潜在依赖边的最大数目下表显示了这些变量的最坏情况估计和四种不同情况下的局部解析操作：（a）没有假设;（b）我们假设语法树具有有限数量的根并且近似平衡，即它们的高度至多为O（log n）;（c）我们假设（b）保持并且岛约束确保每个节点中至多有一个通道用于从无限深度提取;（d）我们假设（b）成立，并且调速器和着陆点总是重合，即在图中没有不连续。这四个场景被用来分析解析器中计算效率低下的来源。最大行动(a)没有一(b)平衡(c)群岛(d)土地=政府RO（ n）O（1）O（1）O（1）HO（ n）时间复杂度O（logn）时间复杂度O（logn）时间复杂度O（logn）LO（ n）时间复杂度O（logn）时间复杂度O（logn）时间复杂度O（logn）SO（ n）O（ n）时间复杂度O（logn）O（1）DO（1）O（1）O（1）O（1）莱克斯1O（1）O（1）O（1）O（1）土地LO（ n）时间复杂度O（logn）时间复杂度O（logn）时间复杂度O（logn）DEPLSDO（ n2）时间复杂度O（n）O（log2n）时间复杂度O（logn）维修1LSDO（ n2）时间复杂度O（n）O（log2n）时间复杂度O（logn）维修2lhs2 d3O（n）时间复杂度O（n）O（log4n）O（log2n）克罗曼16维修3lhs2 d4O（n）时间复杂度O（n）O（log4n）O（log2n）解析3个nlhs2d4O（n）时间复杂度O（n）时间复杂度O（n）时间复杂度O（n）该表表明，近似平衡树（b）和限制性岛约束（c）大大提高了解析器的有效性高度嵌套的句子可能会给人类带来问题，特别是在口语中，所以假设(b)并不是不合理的。由于岛屿约束，如附属岛屿约束，复杂NP约束和补语间隙约束的结果是，只有动词和形容词不表现为克罗曼17作为补充，假设（c）也并非不合理。第六章假设(d)对应于没有不连续性，所以它显然太强了，但是可以提供DG解析器的效率的合理下限。3.5评价和实例DG解析器已在Prolog中实现，带有一个小的语法编码器。 配价模式、格和选择性限制。 落实一个原型，并没有尝试使用有效的算法，所以它是相当慢，时间复杂度为O（n5）。解析器和语法实现，以及广泛的不连续示例（top-icalizations、extractions、scrambling、不连续AP和coordinations，以及带 有 花 园 小 径 和 局 部 歧 义 的 句 子 ） 的 测 试 结 果 ， 可 以 从http://www.id.cbs.dk/mtk/dg下载。实现的目的是检验算法的精度。当解析器返回一个次优解析时，它要么是一个人类也失败的花园路径句子，要么解析只是次优的，因为着陆点在结构中选择得太高，并且在所有其他方面都是最优的。由于着陆点在语义解释中不起作用，这种轻微的次优性并不重要。除了着陆点次优性之外，测试表明解析器在所有其他情况下都返回了最优分析，而不是强花园路径。因此，尽管解析器是启发式的，但在实践中它似乎并不比精确解析器更容易出错。“Ein-Ma¨r chen童话故事1告诉2将3他4他的女儿5能够61. 第七章第九十六节2. 第二章：一个人的世界3. 副署长（1土地-2）7 96dobj-2：立法会（3）24 18副主席（1土地-2）10 96：iobj-2：4. Lex（3）16：225. 副署长（2及3）826vobj-3：（4）24 18土地（2土地-3）12 22**6. 第16章：你是我的女人7. 副署长（4土地-3）796subj-3：法律（五）24 18副（四土三）10 26土（四土三）12 22：iobj-2： ：修理2（4land-3，1land-2）14 修理2（4land-3，1land-3）1096DOBJ-2iobj-2：26dobj-2 subj-3：修理2（4land-3，1land-3）14 26DOBJ-2iobj-2：8. 第15章： 你 是我的女人9. 副署长（5土地-3）796iobj-2：法律（6）23 88土地（5土地-3）11 92**修理2（5land-3，4land-3）14 修理2（5land-3，1land-2）1396subj-3iobj-2：96dobj-2iobj-2：修理2（5land-3，1land-3）13 96DOBJ-2iobj-2：10. 第15章：你是我的女人11. 修理2（6land-3，2land-3）796VOBJ-3vobj-6：土地（3土地-6）11 92土地（6土地-3）11 92**[6]通常只有一根“脊柱”的提取克罗曼1857NP4 69311a11b11b7NP9 NP4 68VP7a7b5a7bNP247b27a10VP11NP12bVP316INFPVP12a191NP2469NP13151718上面的解析说明了DG解析器是如何处理不连续的德语主题化“Ein M rchenerz a len wird er seine r - T ochter k nen”的。左栏显示了在每个步骤中被选为最小成本操作的解析操作，右栏显示了所有可选操作。相关的成本在每个操作后的下标中显示。在每一步中，由于根的数量、格标记或选择限制，所选操作优于备选操作。符号E（E）表示具有新边E的解析操作E，其将图G转换为G E。在步骤11中修复之前和之后的结果图如下所示，其中指示了创建每个边缘的步骤（如果调速器和着陆点重合，则仅显示深边缘）：VP VPVP VPVP VPNP NP NP1 2 8 10 1 2 10一个童话故事告诉我们，他的女儿能不能一个童话故事告诉我们，他的女儿能不能下面的例子展示了局部歧义，其中NP可以是sub-submitted和objects，取决于最后的动词，并且其中动词have在具有名词性和动词性宾语之间是VPVP VPNP NP NP1 6 1 4 6《华尔兹舞曲》是由音乐家们演奏的华尔兹舞曲使音乐家们感到高兴下面的例子说明了德语中的加扰和外置CPweil民主党尼曼德韦尔斯普罗兴帽子华尔兹舞曲自由报因为没有人承诺的观众有华尔兹 玩37c克罗曼199V35131011V16NP NP1 2 4NP146 8 1215下面的例子说明了德语和荷兰语中的中心嵌入CPCP1weil Piet Marie die−Kinder schwimmen lassen sahbecause Piet Marie the−children swim letsawVomdat Piet Marie de−kinderen zag laten zwemmen becausePiet玛丽孩子们看到让游泳左下角的例子说明了德语中的不连续坐标。右边的例子说明了DG如何无法解析花园路径句子，因为它的修复操作太弱了，就像人类一样。CPVPNP13警察NPVP35NP PP VP1 246 10111 2 4 6Weil儿幽默拜西茨特和节拍一匹马跑越过谷仓倒下了4结论不连续文法中的局部代价函数提供了一种灵活有效的方法来度量语法分析的句法、语义、语用和概率可解释性。此外，最优性分析器是非常快的，在语言上合理的假设下，理论时间复杂度为O（nlog4n），并且用最优性分析器和语法的简单实现进行测试表明，所提出的分析操作足够强大，可以为广泛的不连续句子提供正确的分析，尽管它在人类失败的花园路径句子上失败了。因此，优化分析似乎提供了一个快速和准确的模型，人类分析和其不完善之处。有些问题在本文中没有涉及，特别是如何处理歧义的问题，以及如何通过使用复杂的搜索技术来提高DG解析器的平均情况复杂度的问题。新的句法分析操作可能必须被添加到可允许的句法分析操作集合中最后，一个大规模的语法和评估的DG将是非常可取的。引用[1] Abeill e'，A. 和O. Ramb ow，editors，“Tree Adjoining Grammars. 《语法、语言分析与处理》，CSLI出版社，2000年15VPNP1817NPVP16NP2 4 613VP81210 14789名国家警察12克罗曼20[2] Bouma ， G. ， R. 马 卢 夫 和 我 Sag ， Satisfying constraints on extraction andadjunction，Natural Language and Linguistic Theory（2001）.[3] Dalrymple，M.，R. Kaplan，J.M. III和A.王文，[4] 格恩斯巴赫湾一、《心理语言学手册》，学术出版社，1994年[5] 海 格 曼 湖 ， “Introduction to Government and Binding Theory,” Blackwell,1994/1991, 2nd[6] Helbig，G. 和W. Schenk el，[7] 哈德逊河英语语法和单词语法百科全书，http://www.phon.ucl.ac.uk/home/dick/enc-gen.htm（2001年）。[8] 卡格河[9] Kahane，S.，编辑，[10] Kroann，M. T.，走向不连续语法，在：ESSLI 1999年学生会议的会议记录，1999年，页。145-154[11] 曼宁角D. 和H. Schütze，[12] 麦克斯韦，J.T.和R. M. Kaplan，The interface between phrasal and functionalconstraints，Computational Intelligence19（1993），pp. 571-590.[13] 帕帕迪米特里乌角H、[14] 帕帕迪米特里乌角H.和K. Steiglitz，“Combinatorial Optimization.《算法与复杂性》，[15] 波拉德角和I. A. Sag，[16] Simaan，K.，通过树文法的，在：COLING 96，COLING2，1996，pp.1175-1180。[17] Vosse，T.和G. Kempen，人类句法分析中的句法结构组装：基于竞争抑制和词汇语法的计算模型，认知75（2000），pp. 105-143[18] Wareham，H. T.，“计算音系学中的系统参数化复杂性分析”，博士。论文，维多利亚大学（1998年），罗格斯优化档案318-0599。