依存句法分析器的简单实现

早期博文含有大量错误，见谅。关于最大生成树句法分析器，请参考 Non-projective Dependency Parsing using Spanning Tree Algorithms

生成式句法分析指的是，生成一系列依存句法树，从它们中用特定算法挑出概率最大那一棵。句法分析中，生成模型的构建主要使用三类信息：词性信息、词汇信息和结构信息。前二类很好理解，而结构信息需要特殊语法标记，不做考虑。

本文主要利用了词汇+词性生成联合概率模型，使用最大生成树Prim算法搜索最终结果，得到了一个简单的汉语依存句法分析器。

开源项目

本文代码已集成到HanLP中开源：http://www.hankcs.com/nlp/hanlp.html

基本思路

统计词语WordA与词语WordB构成依存关系DrC的频次，词语WordA与词性TagB构成依存关系DrD的频次，词性TagA与词语WordB构成依存关系DrE的频次，词性TagA与词词性TagB构成依存关系DrF的频次。为句子中词语i与词语j生成多条依存句法边，其权值为上述四种频次的综合（主要利用词-词频次，其余的作平滑处理用）。取边的权值最大的作为唯一的边，加入有向图中。

在有向图上使用Prim最大生成树算法，计算出最大生成树，格式化输出。

模型训练

简单地统计一下清华大学语义依存网络语料，得到如下结果：

找@ 频次 54
找@##核心## 核心成分 16
找@<d> 结果事件 1
找@<f> 目的 1
找@<n> 限定 3
找@<root> 核心成分 16
找@<v> 内容 2 结果事件 2 目的 1
找@<vf> 目的 1
找@也有 结果事件 1
找@仪器 限定 1
找@前来 目的 1
找@去 目的 1
找@合作 内容 1
找@引导 结果事件 1
找@让 结果事件 1
找@进入 目的 1
找@队伍 限定 1
找@需 内容 1
找@项目 限定 1

@符号连接起两个词汇或词性，用<>括起来的表示词性，否则是词汇。如果@后面没有内容，则表示频次，否则表示一些依存关系与其出现的频次。

依存句法分析

分词标注

以“我吃米饭”为例，先进行分词与词性标注，结果：

[我/rr, 吃/v, 米饭/nf]

生成有向图

由于依存句法树中有虚根的存在，所以为其加入一个虚节点，这样一共有四个节点：

[##核心##/root,我/rr,吃/v,米饭/n]

每个节点都与另外三个构成一条有向边，一共4 * 3 = 12 条：

##核心##/root 到 我/rr : 未知 10000.0 
##核心##/root 到 吃/v : 未知 10000.0 
##核心##/root 到 米饭/n : 未知 10000.0 
我/rr 到 ##核心##/root : 核心成分 6.410175 
我/rr 到 吃/v : 施事 21.061098 经验者 28.54827 目标 33.656525 受事 37.021248 限定 43.307335 相伴体 48.00737 关系主体 53.115623 内容 53.115623 来源 64.101746 
我/rr 到 米饭/n : 限定 22.2052 施事 48.00737 受事 57.170277 目标 57.170277 经验者 64.101746 连接依存 64.101746 
吃/v 到 ##核心##/root : 核心成分 1.7917595 
吃/v 到 我/rr : 连接依存 96.688614 介词依存 107.67474 施事 107.67474 
吃/v 到 米饭/n : 限定 24.849068 
米饭/n 到 ##核心##/root : 核心成分 37.077995 
米饭/n 到 我/rr : 连接依存 113.2556 
米饭/n 到 吃/v : 受事 0.6931472

其中“未知”表示边不存在，“受事”“施事”表示依存关系，后面的小数表示权值。我对概率取了负对数，所以接下来用加法求最小生成树即可。

最小生成树

关于最小生成树的Prim算法请参考《最小生成树算法初步》，这里必须有所改动，由于虚根有且只能有一个孩子，所以虚根必须单独计算：

        // 找虚根的唯一孩子
        float minCostToRoot = Float.MAX_VALUE;
        Edge firstEdge = null;
        Edge[] edgeResult = new Edge[termList.size() - 1];
        for (Edge edge : edges[0])
        {
            if (edge == null) continue;
            if (minCostToRoot > edge.cost)
            {
                firstEdge = edge;
                minCostToRoot = edge.cost;
            }
        }

然后就是中规中矩的Prim算法：

        while (!que.isEmpty())
        {
            State p = que.poll();
            int v = p.id;
            if (used[v] || p.cost > mincost[v]) continue;
            used[v] = true;
            if (p.edge != null)
            {
                edgeResult[p.edge.from - 1] = p.edge;
            }
            for (Edge e : edges[v])
            {
                if (e == null) continue;
                if (mincost[e.from] > e.cost)
                {
                    mincost[e.from] = e.cost;
                    que.add(new State(mincost[e.from], e.from, e));
                }
            }
        }

得出最小生成树：

2 0核心成分
3 2受事
1 2施事

格式化输出

将其转为CoNLL格式输出：

1	我	我	rr	rr	_	2	施事	_	_
2	吃	吃	v	v	_	0	核心成分	_	_
3	米饭	米饭	n	n	_	2	受事	_	_

可视化

使用可视化工具展现出来：

结果评测

我没有进行严格的测试，这只是一个玩具级别的汉语依存句法分析器。先来看几个good case与bad case——

坚决惩治贪污贿赂等经济犯罪

我每天都在写程序

hankcs每天都在写程序

挖掘机技术哪家强

咬死猎人的狗

效果比较马虎，为何这么说，这是因为分词的训练语料和句法分析语料不同，且我自知此方法严重依赖词汇共现，主要是这种二元词汇生成模型无法充分利用上下文。

短一点的搜索语句可能还是有微量的利用价值。

TODO

应当采用判别式模型，导入SVM或最大熵作为权值的计算工具，然后使用最大生成树算法获取全局最优解。

 知识共享署名-非商业性使用-相同方式共享：码农场 » 依存句法分析器的简单实现