线图分析法

线图分析法（chart parsing）是基于CFG规则的分析方法，首先需要了解一下什么是形式语言：形式语言

1 三种策略

线图分析法在具体的实现上有三种不同的策略，分别为：

• 自底向上（Bottom-up）
• 从上到下（Top-down）
• 从上到下和从下到上结合

对于自然语言来说，采用的更多的是自底向上策略，即给定一个句子，从句子开始推算其可能的结构，最后得到一棵树。而从上到下则是根据一个结构推算句子。

2 自底向上的线图分析法

算法的内容如下：

• 给定一组CFG规则：$XP\to {\alpha }_1\cdots {\alpha }_n(n\ge 1)$，这其中的$\alpha$既可以是非终结符又可以是终结符；
• 给定一个句子的词性序列：$S=W_1{W}_2\cdots W_n$，注意是词性序列，这意味着要做词性标注；
• 构造一个线图：线图是一组节点和边的集合；

• 建立一个二维表：记录每一条边的起始位置和终止位置。

然后执行操作：查看任意相邻几条边上的词性串是否与某条重写规则的右部相同，如果相同，则增加一条新的边跨越原来相应的边，新增加边上的标记为这条重写规则的头（左部）。重复这个过程，直到没有新的边产生。

3 数据结构

算法需要的数据结构如下：

• 线图（Chart）：保存分析过程中已经建立的成分（包括终结符和非终结符）、位置（包括起点和终点）。通常以$n\ast n$的数组表示（$n$为句子包含的词数）。
• 待处理表（Agenda）：记录刚刚得到的一些重写规则所代表的成分，这些重写规则的右端符号串与输入词性串（或短语标志串）中的一段完全匹配，通常以栈或线性队列表示。
• 活动边集（ActiveArc）：记录那些右端符号串与输入串的某一段相匹配，但还未完全匹配的重写规则，通常以数组或列表存储。

4 点规则

点规则用于表示规则右部被归约（reduce）的程度。可以理解为点的位置左边都是匹配到的规则的一部分，如果点的左边是规则右部的所有内容，那么就说明规则右边已经被完全匹配。根据点规则，可有以下两种边：

• 活性边（活动弧）：规则右部未被完全匹配
• 非活性边（非活动弧，或完成弧）：规则右部已被完全匹配

5 算法描述

从输入串的起始位置到最后位置，循环执行如下步骤：

1. 如果待处理表（Agenda）为空，则找到下一个位置上的词，将该词对应的（所有）词类$X$附以$(i,j)$作为元素放到待处理表中，即$X(i,j)$。其中，$i,j$分别是该词的起始位置和终止位置，$j>i$，$j-i$为该词的长度。
2. 从Agenda中取出一个元素$X(i,j)$。
3. 对于每条规则$A\to X\gamma$，将$A\to X\circ \gamma (i,j)$加入活动边集ActiveArc中，然后调用扩展弧子程序。
   扩展弧子程序：
   （a）将$X$插入图表（Chart）的$(i,j)$位置中。
   （b）对于活动边集（ActiveArc）中每个位置为$(k,i)(1\le k<i)$的点规则，如果该规则具有如下形式：$A\to \alpha \circ X$，如果$A=S$，则把$S(1,n+1)$加入到Chart中，并给出一个完整的分析结果；否则，则将$A(k,j)$加入到Agenda表中。
   （c）对于每个位置为$(k,i)$的点规则：$A\to \alpha \circ X\beta$，则将$A\to \alpha X\circ \beta$加入到活动边集中。

6 示例

现有规则：
$$\begin{gathered} S\to NPVP \\ VP\to VNP \\ NP\to DetN \\ Det\to the \\ N\to boy \\ V\to hit \\ N\to dog \end{gathered}$$
句子为$theboyhitsthedog$。
首先进行词的形态分析，这里将$hits$还原为$hit$，然后根据规则进行词性标注得到${}_{1}De{t}_2{N}_3{V}_{4}De{t}_5{N}_6$，根据算法之后每一次循环的步骤如下：

1. $Agenda$初始内容为空加入第一个词$Det(1,2)$，然后取出$Det(1,2)$，将$NP\to Det\circ N(1,2)$加入$ActiveArc$中，将$Det(1,2)$插入$Chart$中。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{\} \\ ActiveArc:\{NP\to Det\circ N(1,2)\} \\ Chart:\{(Det,1,2)\} \end{gathered}$$
2. $Agenda$为空，加入第二个词$N(2,3)$；取出$N(2,3)$；并没有满足$A\to N\gamma$的规则；将$N(2,3)$插入$Chart$中，$ActiveArc$中$NP\to Det\circ N(1,2)$满足条件（b），于是将$NP(1,3)$加入$Agenda$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{NP(1,3)\} \\ ActiveArc:\{\} \\ Chart:\{(Det,1,2),(N,2,3)\} \end{gathered}$$
3. 取出$NP(1,3)$；将$S\to NP\circ VP(1,3)$加入$ActiveArc$；将$NP(1,3)$插入$Chart$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{\} \\ ActiveArc:\{S\to NP\circ VP(1,3)\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3)\} \end{gathered}$$
4. $Agenda$为空，加入第三个词$V(3,4)$；将$VP\to V\circ NP(3,4)$加入$ActiveArc$；将$V(3,4)$插入$Chart$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{\} \\ ActiveArc:\{S\to NP\circ VP(1,3),VP\to V\circ NP(3,4)\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3),(V,3,4)\} \end{gathered}$$
5. $Agenda$为空，加入第四个词$Det(4,5)$；将$NP\to Det\circ N(4,5)$加入$ActiveArc$；将$Det(4,5)$插入$Chart$中。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{\} \\ ActiveArc:\{S\to NP\circ VP(1,3),VP\to V\circ NP(3,4),NP\to Det\circ N(4,5)\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3),(V,3,4),(Det,4,5)\} \end{gathered}$$
6. $Agenda$为空，加入第五个词$N(5,6)$；将$N(5,6)$插入$Chart$中；$ActiveArc$中$NP\to Det\circ N(4,5)$满足条件（b），将$NP(4,6)$加入$Agenda$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{NP(4,6)\} \\ ActiveArc:\{S\to NP\circ VP(1,3),VP\to V\circ NP(3,4)\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3),(V,3,4),(Det,4,5),(N,5,6)\} \end{gathered}$$
7. 取出$NP(4,6)$；将$NP(4,6)$插入$Chart$；$ActiveArc$中$VP\to V\circ NP(3,4)$满足条件（b），将$VP(3,6)$加入$Agenda$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{VP(3,6)\} \\ ActiveArc:\{S\to NP\circ VP(1,3)\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3),(V,3,4),(Det,4,5),(N,5,6),(NP,4,6)\} \end{gathered}$$
8. 取出$VP(3,6)$；将$VP(3,6)$插入$Chart$；$ActiveArc$中$S\to NP\circ VP(1,3)$满足条件（b），将$S(1,6)$加入$Chart$。此时各个数据结构的内容如下：
   $$\begin{gathered} Agenda:\{\} \\ ActiveArc:\{\} \\ Chart:\{(Det,1,2),(N,2,3),(NP,1,3),(V,3,4),(Det,4,5),(N,5,6),(NP,4,6),(VP,3,6),(S,1,6)\} \end{gathered}$$
9. 到此为止，算法便退出了，根据$Chart$中的内容便可绘制出线图，然后将节点变成边，边变成节点就能够绘制成分析树。

7 算法评价

优点：算法简单，容易实现，开发周期短
弱点：算法效率低，时间复杂度为$K{n}^3$；需要高质量的规则，分析结果与规则质量密切相关；难以区分歧义结构。

参考资料：《统计自然语言处理》宗成庆