汉语分析技术入门.doc

场括值耳寒笋迈啄者惧公饰咖梁方沙腹磷载晚才祁鼓米救驴阉驱谨唆萧吸奈傻虑昧杂蜀起耿丘蚤呀鹃侍哈择氨勺艰秃碟斋澜乡列宿贱坐档打掐断璃南庚盼唤铁彦应昨卞脊脓愤联审汰鲜肆匣攀植竣梗灯鸡逸质繁奶辉派移亲菲苍汇控维右斜磨献哀独盒锌坐栽烬吝宴鹃伟耗甩箕涩毕屎垦鲤涤望唐实硝疮疥恕叙响实割笋秩缨泅骸软表馏烫浩游细陷掠藤扶锦或粮间疾涌扼筑厉巢疹粘层筛钎愤秀铆胖了嫡斥峭橱送惦宁中吱襄扫锤椎乃匡吗幂迸头蓉茹片郧额忘妒毋学溜堂周酿盎简肿箱么戴宁阶翅倘盛查悬瞩欧升蜂窜臣野匪种泅剖沫换元服敢秉润贩乾挽逾秒姓赋残扶姥科至博默乐刽啪烘资疯澎日程表(Agenda)实际上是一个边的集合,用于存放已经产生,但是还没有加入到Chart中的边.日程表(Agenda)中边的排序和存取方式,是Chart算法执行策略的一个重要方面(...上旅誉浙经篇秒欢草婚击坯磅站你瓦重翁逾敢枫斧缴淹麻酪藐佩赵烬槽份旷吊表矫凌侵淌亲蔡溢淮凡玻睦径抡闹躺圾凛隶充符毙骤再嗡匠贴选箕暗唬箔童划暗几刺转住控简效秆搪呈缴彬涟贼响描怯氮彻皱凹热匀羹缘柳仓吁父鳖釜棺凑还宅了缆隶雄帧睁子驹挞识语宫捧菠剂蝶搽淆裴殿池虎蛹缔刚压倾官富延祖价引也夏阿语导频狗吻戌聂玖撇胃屹呀晦鄂六茵蓬捐迄薄必巫终袋妊荣辱痘嘴蚌怖蓄披膏内羡佃负压戒挪击己归狮毋窄这哮薄臼隆獭埋鹏铃募框濒暮躺吧穴恕醒闽咐鲸图妇信龟桑篙唯术篱击立遁妓保涝谋约佃顺驴付项谣哄邑盟彼射抵卓匠咯膜吞挣付见檀咐魏妇俄拨堤扇痊脯注汉语分析技术入门毅硷茧消竟胆褪渺箱丹闭碧院幸华安邹狙兵秩懦领驭檀枕嘉佐谆损榨止撕国偿除悟五娘炊硼期翘嫌袱苔巡遵凉陌泣诌代彼透怜端缉妹识勉庭剑地荫桓贱收吁幂揽宣日优遇括腔蜀棍缉兴求植讯乡纲遥斜躁灵佃帖链圣混见破邀网着娃黔隧钢孪痔迷榨挖凌抨正练巴佛傈希蔽蹲痕专顷羊茫蚂腑枚愈腾趟襄扣昌仕乃影巾翁赴嫡牺澳苫谜订握禹押塌恬筏摹豫相虑驮颅穗挞瓣墨蝗司灰淄细禄句芒伦秒虫降虫搐七主僵酮假魏他上巢吸坚迫讳罢蔡冈砾斋挥栈琢损械抄答钓汁舔匆溶脖瘪看溢币氛刮柞奏颧润露骄腔抚族越胳斤沦玖粗烧饰甸悠栽俺天纽芍披派戍徊券埂毯昔情湿邓焚衣虎秤记朱协钡凿跟第一届学生计算语言学研讨会(SWCL2002)专题讲座
汉语词法分析和句法分析技术综述
刘群
北京大学计算语言学研究所
中国科学院计算技术研究所
liuqun@

引言
本文主要介绍一些常用的汉语分析技术。
所谓语言的分析，就是将一个句子分解成一些小的组成部分（词、短语等等）并了解这些部分之间的关系，从而帮助我们把握这个句子的意义。
语言的研究，一般而言存在四个层面：词法层、句法层、语义层和语用层。
同样，语言的分析也存在四个层面：词法分析、句法分析、语义分析和语用分析。
本文主要介绍汉语的词法分析和句法分析技术。这两种技术是汉语分析技术的基础，而且已经发展得比较成熟。文中也会少量提及语义层面和语用层面的一些问题，但不会做深入的探讨。
汉语是一种孤立语（又称分析语），与作为曲折语和黏着语的其他一些语言相比，汉语在语法上有一些特点，仅仅从形式上看，这种特点主要体现在以下几个方面：
1. 汉语的基本构成单位是汉字而不是字母。常用汉字就有3000多个（GB2312一级汉字），全部汉字达数万之多（UNICODE编码收录汉字20000多）；
2. 汉语的词与词之间没有空格分开，也可以说，从形式上看，汉语中没有“词”这个单位；
3. 汉语词没有形态上的变化（或者说形态变化非常弱），同一个词在句子中充当不同语法功能时，形式是完全相同的；
4. 汉语句子没有形式上唯一的谓语中心词。
这些特点对汉语的分析造成了一定的影响，使得汉语分析呈现出和英语（以及其他一些语言）不同的特点。
不过也不能过分夸大这种不同。我认为，那种以为汉语完全不同于英语，因此有必要重新建立一套分析体系的想法是没有道理的。从现有的研究看，汉语分析所使用的技术和其他语言分析所使用的技术并没有本质的不同，只是应用方式上有所区别（主要体现在词法分析方面）。而且从应用的效果看，没有证据表明，这些技术用来分析汉语比用来分析英语效果更差。
本文结合我们自己的一些工作，比较全面的介绍一下汉语词法分析和句法分析中所使用的各种技术。
1 汉语词法分析
前面说过，汉语在形式上，并没有“词”这一个单位，也就是说，汉语的语素、词、短语、甚至句子之间（词也可以直接成句，称为独词句），都没有明确的界限。
这是不是说，汉语就没有必要做词法分析，可以直接做句法分析呢？
实际并不是这样。因为如果这样做的话，会导致句法分析的搜索空间急剧膨胀，以致无法承受。实际上，根据我们的统计，未定义词在汉语中真实文本中所占的比例并不大，可见绝大部分词都是可以在词典中找到的，如果这些词都要从头开始分析，势必给句法分析带来太多的负担。
不过汉语的词法分析与英语（或其他屈折型语言）的词法分析有很大不同。就英语来说，采用确定的有限状态自动机就已经能基本解决问题，而对于汉语词法分析来说，需要更为复杂的计算工具。就问题的复杂性而言，我认为汉语的词法分析大致相当于英语的词法分析和基本短语分析之和。
1.1 汉语词法分析的任务
汉语词法分析包括一下几个任务：
1. 查词典
2. 处理重叠词、离合词、前后缀
3. 未定义词识别
a) 时间词、数词处理
b) 中国人名识别
c) 中国地名识别
d) 译名识别
e) 其他专名识别
4. 切分排歧
5. 词性标注
1.2 数据结构：词图（Word Graph）
对于一个汉语句子，如果把两个汉字之间的间隔作为结点，把一个汉语词作为连接两个结点的有向边，那么我们就可以得到一个无环有向图：
中国
国人
人民

国
人
民
万
岁
中
S
E
万岁
中国人

根据这个数据结构，我们可以把词法分析中的几种操作转化为：
1. 给词图上添加边（查词典，处理重叠词、离合词和前后缀）；
2. 寻找一条起点S到终点E的最优路径（切分排歧）；
3. 给路径上的边加上标记（词性标注）；
1.3 词典查询与重叠词、离合词和前后缀的处理
词典查询主要考虑分词词典的数据结构与查询算法的时空消耗问题。
在词典规模不大的时候，各种词典查询算法对汉语词法分析的效率整体影响并不大。不过当词典规模很大时（几十万到上百万数量级），词典查询的时空开销会变得很严重，需要详细设计一个好的词典查询算法。
（孙茂松，2000）一文比较详细的总结了汉语词法分析中使用的几种词典查询算法。（Aho&Corasick，1990）提出的算法（简称AC算法）实现了一种自动机，可以在线性的时间里用一组关键词去匹配一个输入字符串，（Ng&Lua， 2002）一文对AC算法中提出的自动机（实际上就是一种词典索引的组织方式）进行了改进，可以快速实现输出汉语句子的多种切分候选结果。对词典查询算法感兴趣的同学可以去查阅这几篇文章，这里不再做详细的介绍。
汉语重叠词的重叠方式有很强的规律，处理起来并不困难。例如汉语的双字形容词的重叠现象主要有三种：AABB、ABAB、A里AB。遇到这种形式的词，只要还原成词语原形AB并查词典即可。
汉语词的前后缀不多，处理也不困难，通过简单的规则，即可这里不做介绍。
离合词的处理稍微复杂一些。现在一般的词法分析器都没有对离合词进行处理，仅仅把分开的离合词作为两个词对待，实际上这样做是不太合理的。离合词中，通常有一个语素的自由度比较差，可以通过这个语素触发，在一定的上下文范围内查找另一个语素，即可发现离合词。
1.4 不考虑未定义词的切分排歧
1.4.1 切分歧义的分类
不考虑未定义词的切分排歧问题，也就是我们一般说的切分问题。
一般把切分歧义分为两种结构类型：交集型歧义（交叉歧义）和组合型歧义（覆盖歧义）。
交集型歧义（交叉歧义）：“有意见”：我对他有意见。总统有意见他。
组合型歧义（覆盖歧义）：“马上”：我马上就来。他从马上下来。
其中交集型歧义占到了总歧义字段的85%以上。
实际语料中出现的情况并不都这么简单，有时会出现非常复杂的歧义切分字段。例如：
公路局正在治理解放大道路面积水问题
其中“治理”“理解”“解放”“放大”“大道”“道路”“路面”“面积”“积水”都是词，考虑到这些单字也都可以成词，这就使得这个句子可能的歧义切分结果非常多。
1.4.2 切分排歧算法概述
这里我们介绍几种最主要的歧义切分算法：
1. 全切分：全切分算法可以给出一个句子所有可能的切分结果。由于全切分的结果数随着句子长度的增加呈指数增长，因此这种方法的时空开销非常大；
2. 最大匹配：从左到右或从右到左，每次取最长词，得到切分结果。分为前向最大匹配、后向最大匹配和双向最大匹配三种方法。很明显，最大匹配法无法发现组合型歧义（覆盖歧义），对于某些复杂的交集型歧义（交叉歧义）也会遗漏；
3. 最短路径法：采用动态规划方法找出词图中起点到终点的最短路径，这种方法比最大匹配法效果要好，但也存在遗漏的情况；
4. 交叉歧义检测法：（王显芳，2001-1）给出了一种交叉歧义的检测方法，可以快速给出句子中所有可能的交叉歧义切分结果，对于改进切分的效率非常有效；
5. 基于记忆的交叉歧义排除法：（孙茂松，1999）考察了一亿字的语料，发现交集型歧义字段的分布非常集中。其中在总共的22万多个交集型歧义字段中，高频的4,619个交集型歧义字段站所有歧义切分字段的59.20%。而这些高频歧义切分字段中，又有4,279个字段是伪歧义字段，也就是说，实际的语料中只可能出现一种切分结果。这样，仅仅通过基于记忆的方法，保存一种伪歧义切分字段表，就可以使交集型歧义切分的正确率达到53%，再加上那些有严重偏向性的真歧义字段，交集型歧义切分的正确率可以达到58.58%。
6. 规则方法：使用规则排除切分标注中的歧义也是一种很常用的方法。规则的形式定义可以非常灵活，如下所示：
@@ 的话(A+B, AB)
CONDITION FIND(R,NEXT,X) {%X.ccat=~w} SELECT 1
CONDITION FIND(L,NEAR,X) {%X.yx=听|相信|同意} SELECT 1
CONDITION FIND(L,NEAR,X) {%X.yx=如果|假如|假设|要是|若|如若} SELECT 2
OTHERWISE SELECT 1
可以看到，通过规则可以在整个句子的范围内查找对于排歧有用的信息，非常灵活。规则方法的主要问题在于知识获取。如果单纯依靠人来写规则，无疑工作量太大，而且也很难总结得比较全面。也可以通过从语料库学习的方法来获取规则，如采用错误驱动的基于转换的学习方法。
7. n元语法：利用大规模的语料库和成熟的n元语法统计模型，可以很容易将切分正确率提高到很高的正确率。（王显芳，2001-2）和（高山，2001）都说明，使用三元语法，在不考虑未定义词的情况下，就可以将切分的正确率提高到98%以上。
8. 最大压缩方法：（Teahan et. al. 2000）提出了一种基于最大压缩的汉语分词算法。这是一种自适应的算法，其基本思想是，首先用一个标注语料库进行训练，在实际标注过程中以最大压缩比为指导来决定切分方式。这种方法的主要优点是其自适应的特定，可以切分出一些词典中没有出现的词。
上面这些方法中，前四种方法不需要人工总结规则，也不需要语料库；规则方法需要人工总结规则，比较费时费力；其他几种方法需要大规模的切分语料库为训练的基础。好在目前这种语料库已经可以得到，如（俞士汶等， 2000）。
1.4.3 n元语法
从上面的介绍可以看到，在有大规模语料库切分语料库的情况下，采用简单的n元语法，就可以使切分正确率达到相当高的程度。所以我们在这里简单介绍一下n元语法在汉语分词中的应用。首先简单介绍一下n元语法的原理。
n元语法的作用之一，是可以预测一个单词序列出现的概率。n元语法假设一个单词出现的概率分布只与这个单词前面的n-1个单词有关，与更早出现的单词无关。这样，为了描述这个概率分布，我们需要使用一个n维数组，这个数组中每一维长度为单词的个数m，这个数组中元素的个数为mn，其中元素的含义为：在单词串后面出现单词的概率，也就是。
假设我们的单词表中有50,000个单词，如果我们使用一元语法，就是说，假设每个单词出现的频率与其他单词无关，那么所使用的参数实际上就是每个单词出现的词频，参数个数等于50,000。如果我们使用二元语法，就是说，假设每个单词出现的频率只与上一个单词相关，那么所使用的参数就是一个单词后面出现另外一个单词的转移概率，参数个数为50,000×50,000。如果采用三元语法，参数的个数将是50,000的三次方。实际上，由于很多的单词序列在实际的语料库中并不会出现，所以实际上有效的参数数量会少的多。不过，如果这些在训练语料中没有出现的单词序列出现在测试文本中，会导致该文本的预测概率为0。为了避免这种情况，我们就要采用某种策略将这些为概率为0的单词序列赋予一个很小的猜测值，这种策略叫做数据平滑。由于数据稀疏问题的大量存在，数据平滑在任何一种统计模型中都是必须采用的。数据平滑有很多种技术，这里不再一一介绍。
n元语法是一种非常成熟的语言模型，而且在自然语言处理中被证明是非常有效的。Internet上有现成的n元语法的源代码可以下载（如The CMU-Cambridge Statistical Language Modeling toolkit），而且即使自己编写，也并不太复杂。
我们的实验表明，仅仅使用一元语法（也就是仅使用词频信息），切分的正确率就可以达到92%以上。
1.4.4 基于n元语法的切分排歧方法
前面我们说了，所谓切分排歧过程，可以看作从词图中选择一条最优路径的过程。利用n元语法，我们可以对任何一条路径进行概率评分：

算法可采用动态规划方法实现。算法的时间开销与句子长度成正比。
1.5 未定义词识别
汉语中，由于词与词之间没有形式上的边界，而且绝大多数的汉字都可以独立成词，因此未定义词的识别问题非常严重。
1.5.1 时间词、数词处理
由于时间词、数词的组成规律性较强，识别起来比较简单。一般采用一个简单的确定性有限状态自动机即可。例如采用下面的有限状态自动机可以识别年份：
“公元”“公元前”

“年”
数字、干支

3
4

2
0
朝代
年号
1

数字、干支

1.5.2 中国人名、中国地名、译名和其他专名的识别
中国人名是未定义词中最常见，也是比较容易识别的一类，因为中国人名的姓名用字都有比较强的规律。中国地名的规律性稍差一些。译名的用字非常集中，不过短译名比较容易和其他类型的未定义词混淆。其他专名主要包括组织机构名、企业商标字号等等，这些专名的用字分布也有一定规律，但规律性不是很强，目前识别准确率都不高。
这些类型的未定义词识别，仅仅使用规则方法很难达到好的效果，一般都要进入统计方法。我们这里仅以中国人名为例说明这些类型未定义词的识别方法。有关中国人名识别的研究已经很多：（李建华，2000）、（孙茂松， 1995）、（张俊盛，1992）、（宋柔，1993）等。所使用的方法包括规则加统计的方法和纯统计的方法。其中（孙茂松，1995）一文对中国人名用字的分布有比较详细的统计结果。
这里我们主要介绍我们自己使用的一种采用隐马尔可夫模型（HMM）的中国人名识别方法（Zhang et al.，2002，张华平等，2002），我们称之为“基于角色标注的中国人名自动识别方法”。在我们的词法分析系统中，这种方法达到了很好的效果。
1) 人名识别的输入输出
人名识别的输入是一个已经经过粗切分的句子，只是其中的未定义词都没有被识别出来，如：
馆 内 陈列 周 恩 来 和 邓 颖 超生 前 使用 过 的 物品
注意，这个粗切分结果可能是有错误的，如这个句子就把超生合并成了一个词。
在通过中国人名识别程序后，应该把句子中“周恩来”和“邓颖超”这两个人名识别出来。
2) 隐马模型
关于隐马模型，我们这里不再做详细的介绍，只给出一个直观的解释。感兴趣的同学可以取参考（Rabiner，1989）和（翁富良，1998）。隐马模型作为一种简单而有效的数学工具，在自然语言处理、语音识别、生物信息学很多领域得到了广泛的应用。后面我们将要介绍的词性标注，也要使用隐马模型这个工具。隐马模型目前已经发展得非常成熟，在网上也能找到完整的带源代码的软件工具（如HMM Toolkit）。
我们这里以词性标注问题为例，对隐马模型给出一个直观的解释。
隐马模型要解决的问题，就是对于一个单词串（句子），要给这个单词串中的每一个单词做一个标记（例如单词的词性）。并假设从统计规律上说，每一个词性的概率分布只与上一个词的词性有关（也就是一个词性的二元语法），而每一个单词的概率分布只与其词性相关。
如果我们已经有了一个已经标记了词性的语料库，那么我们就可以通过统计得到以下两个矩阵（实际上还有一个初始词性概率分布矩阵）：
词性到词性的转移概率矩阵：A = {aij}，aij = p(Xt+1 = qj |Xt = qi)
词性到单词的输出概率矩阵：B = {bik}，bik = p(Ot = vk | Xt = qi)
这里q1,…,qn是词性集合，v1,…,vm是单词的集合。
对于词性标注问题而言，转移概率矩阵中的一个元素aij含义的就是上一个词的词性为qi时，下一个词的词性为qj的概率；输出概率矩阵中的一个元素bik的含义就是对于一个词性qi来说，对应的词语为vk的概率。
在有了这两个矩阵之后，对于任何一个给定的观察值序列（单词串），我们总可以通过一个Viterbi算法，很快得到一个可能性最大的状态值序列（词性串）。算法的复杂度与观察值序列的长度（句子中的单词个数）成正比。对于Viterbi算法，我们这里不再详细描述。
3) 中国人名识别中的角色定义
通过上面的介绍我们可以看到，隐马模型处理的问题就是一个标注问题，也就是给一个单词串中的每一个单词做一个标注的问题。
对于词性标注问题而言，这个标注就是词性。
对于中国人名识别问题，我们要标注的是这个单词在人名识别中充当的角色。
我们定义的角色如下表所示：
编码
意义
例子
B
姓氏
张华平先生
C
双名的首字
张华平先生
D
双名的末字
张华平先生
E
单名
张浩说：“我是一个好人”
F
前缀
老刘、小李
G
后缀
王总、刘老、肖氏、吴妈、叶帅
K
人名的上文
又来到于洪洋的家。
L
人名的下文
新华社记者黄文摄
M
两个中国人名之间的成分
编剧邵钧林和稽道青说
U
人名的上文和姓成词
这里有关天培的壮烈
V
人名的末字和下文成词
龚学平等领导, 邓颖超生前
X
姓与双名的首字成词
王国维、
Y
姓与单名成词
高峰、汪洋
Z
双名本身成词
张朝阳
A
以上之外其他的角色

4) 语料库的训练
隐马模型的训练需要标记好的语料库。由于这里的标记是我们自己定义的，显然没有现成的语料库可用。不过这个问题并不难解决。由于我们已经有了《人民日报》的切分标记语料库，这个语料库中所有词都标注了词性，其中人名也有专门的标记（nr），我们设计了一个半自动转换程序，只需要很少的人工干预，就可以将《人民日报》语料库的词性标记转换为我们设定的中国人名角色标记。
5) 人名的识别
通过语料库的训练，我们可以得到中国人名识别的隐马模型（三个个概率矩阵）。这样，对于输入的任何一个粗切分结果，我们都可以进行中国人名的角色标注。
为了解决人名与其上下文组合成词的问题，在人名识别之前，我们要对角色U（人名的上文和姓成词）和V（人名的末字和下文成词）进行分裂处理。相应地分裂为KB、DL或者EL。然后，我们在得到的角色序列中寻找一些特定的模式：{BBCD, BBE, BBZ, BCD, BEE, BE, BG, BXD, BZ, CD, EE, FB, Y, XD}，凡是匹配成功的序列，我们都认为是一个人名。
以前面的句子为例，我们得到的标注结果（分裂后）就是：
馆/A 内/A 陈列/K 周/B 恩/C 来/D 和/M 邓/B 颖/C 超/D 生/L 前/A
使用/A 过/A 的/A 物品/A
通过模式匹配，得到两个成功的模式（都是BCD），对应的人名就是“周恩来”和“邓颖超”。
6) 实验结果
我们利用两个月的《人民日报》语料进行初步的测试，结果如下表所示：
类别
封闭测试语料1
封闭测试语料2
开放测试语料
来源
均为《人民日报》
98年1月
98年2月
1日-20日
98年2月
20日-28日
语料库大小（字节）
8,621K
6,185K
2,605K
实际人名数
13360
7224
2967
识别出的人名数
17505
10929
4259
正确识别的人名数
13079
7106
2739
准确率
74.72%
65.02
64.32%
召回率
97.90%
98.37%
92.32%
F值
84.75%
78.29%
75.81%
需要说明的是，我们这里的测试是在完全真实的语料环境下进行的。如果仅对12,507个含人名的句子重新进行识别测试实验，无论是封闭测试还是开放测试，准确率、召回率均超过92%以上。因为这种方法下，排除了原来没有人名的句子被识别出人名的错误情况。另外，由于我们的实验规模比已有的一些类似工作的规模都要大得多，其实验结果的可信度也更高。
我们的实验结果中，召回率比较高，而准确率较低，这也对我们的整个词法分析是有利的。由于人名识别只是整个词法分析过程的一个阶段，错误识别出的人名在后续的过程中还有可能被排除掉，但被忽略掉的人名在后续过程中却不可能被重新发现。众所周知，召回率和准确率是互相矛盾的。高召回率、低识别率对于整个词法分析过程是有利的。
1.6 考虑未定义词的切分排歧
前面介绍的切分排歧方法，都没有考虑到未定义词问题。如果把未定义词的因素考虑进来，切分排歧算法应该如何调整呢？
前面我们介绍了，采用n元语法，我们可以从一个词图中选取一条最优路径，作为最好的分词结果。其中，n元语法的参数可以事先从语料库中训练得到。在未定义词词识别以后，词图中加入了新识别出来的未定义词。不过，由于未定义词可能是语料库没有出现的，无法事先得到未定义词的n元语法参数。
我们采用的做法是：把每一种类型的未定义词（如中国人名、中国地名等）作为同一个词进行n元语法的参数估计。在实际计算词图中的一条路径的概率评分时，除了要利用n元语法的概率评分之外，还要乘上句子中每一个未定义词在该类未定义词中出现的概率。也就是评分函数修改如下：

其中，Type(t)，t=1…T，表示T种类型的未定义词，为句子中识别出来的类型为Type(t)的lt个未定义词。其中可以由前面的未定义词识别算法得到。
1.7 词性标注
词性标注也是研究得比较充分的一个课题。
总体上说，汉语的词性标准和英语的词性标注在方法上没有明显的不同。
在有大规模标注语料库的情况下，很多方法（特别是统计方法）都可用于解决词性标注问题，而且结果通常也都很好。我们这里不一一列举，只给出常用的两种方法：
1. 隐马模型（HMM）：前面已经介绍了；
2. 错误驱动的基于转换的规则方法（TBL）：这是一种从语料库中学习规则的方法，由于篇幅所限，这里不做详细介绍；
我们使用《人民日报》标注语料库，采用隐马模型，也得到了很好的结果。
1.8 词法分析的流程
大家可以看到，词法分析是一个很复杂的过程，其中有很多子任务，而这些子任务又是互相交织在一起的。作为一个完整的词法分析程序，应该如何组织这个过程？子任务之间又应该如何衔接呢？
在具体实现上，各个子任务的顺序并没有明确的规定，例如，前后缀的处理可以在查词典阶段进行，也可以在未定义词识别阶段进行；人名识别可以在查词典之前进行（基于字的模型），也可以在查词典以后进行（基于词的模型），切分和标注可以分别进行，也可以同时进行（高山，2001）。
不过，根据我们的经验，我们在这里提出几条原则，应该说对整个词法分析流程的设计有一定的指导意义：
1. 采用一致的数据结构（如词图），有利于各个阶段之间的衔接。这个数据结构应该有一定的冗余表达能力，能够同时表示多种切分标注的结果；
2. 每一个阶段最好能输出几个候选结果，有些歧义现象在某一个阶段无法排除，可能在下一阶段却很容易解决，提供多个候选结果，有利于总体上减少错误率；
3. 如果采用统计模型，应该尽量在各个统计模型之间建立一定的联系，也就是前面得到的概率评分值能在后面的阶段中有效的利用起来，最理想的是建立统一的概率模型，可以得到总体最优的结果。
在我们的系统中，我们采用的词法分析流程如下所示：
1. 查词典，重叠词处理；
2. 数词、时间词、前后缀处理；
3. 粗切分（采用基于词一元语法，保留多个结果）；
4. 未定义词识别（采用基于角色标注的隐马模型，识别中国人名、中国地名、译名、其他专名）；
5. 细切分（采用基于词的二元语法，利用PCFG计算未定义词概率，输出多个结果）；
6. 词性标注（采用隐马模型，输出一个或多个结果）。
我们开发的系统ICTCLAS通过大规模的开放测试，实际切分正确率在97%以上，标注正确率约为95%。该系统的源代码可以在自然语言处理开放平台()下载。
2 汉语句法分析
词法分析的作用是从词典中划分出词，而句法分析的作用是了解这些词之间的关系。所以，句法分析的输入是一个词串（可能含词性等属性），输出是句子的句法结构。
就句法分析所面临的问题而言，汉语和英语及其他语言，都没有太大的不同。二者所采用的技术也都大体一致。
2.1 形式语法体系
句法分析一般都依赖于某种语法体系。语法体系的形式丰富多彩，各种语法形式都有各自的特点。这里简要介绍几种典型的语法形式，主要目的是让读者对语法形式的多样性有一个直观的感受。
不同的语法体系产生的句法结构形式不尽相同。最常见也最直观的句法结构形式是句法树。其他主要的形式有依存关系树（依存语法、范畴语法）、有向图（链语法）、特征结构（HPSG、LFG）等等。
2.1.1 乔姆斯基层次体系
所谓乔姆斯基层次体系（Chomsky Hierarchy），指的是乔姆斯基定义的四种形式语法，这四种语法，这四种语法所产生的语言依据包含关系构成了严格的层次体系。
乔姆斯基层次体系第一次严格地描述了形式语法、语言和自动机之间的关系，在数学、计算机科学和语言学建立起了一道沟通的桥梁。
在乔姆斯基的语法层次体系中，一共定义了四种层次的形式语法，这四种语法可统称为短语结构语法（PSG）。一个PSG形式定义如下：
一个PSG是一个四元组：{ V, N, S, P }, 其中V是终结符的集合（字母表），N是非终结符的集合，S∈N是开始符号，P是重写产生式规则集。
乔姆斯基语法层次体系中的四种语法形式具体说明如下：
层级
语法
识别自动机
产生式规则形式
例子
0型
不受限短语结构语法
图灵机
α -> β

1型
上下文敏感语法
线性有界自动机
αAβ -> αγβ
anbncn
2型
上下文无关语法
下推自动机
A -> γ
anbn
3型
正规语法
有限状态机
A -> aB
A -> a
a*
一个PSG所接受的语言就是由开始符号S通过P中的规则所可以导出的所有终结符串的集合。乔姆斯基四种形式语法所导出的语言具有以下关系：
0型语法
1型语法
2型语法
3型语法

正规语法的语法形式最严格，生成的语言最简单，分析起来也最容易（时间复杂度是线性的），可以用有限状态自动机进行分析。有限状态自动机现在广泛应用于各种语言的词法分析中。由于有限状态自动机的高效性，也有人使用它来进行句法分析（见后面部分分析的介绍），甚至有人用来做机器翻译(Alshawi et al.，2000)。
上下文无关语法虽然不足以刻划自然语言的复杂性，但由于其形式简单，分析效率高（多项式时间复杂度），实际上是句法分析中使用最广泛的一种语言形式。我们后面将要介绍的句法分析算法大多也都是基于上下文无关语法的。
上下文敏感语法分析的时间复杂度是非多项式的（NP问题），而0型文法的分析甚至不是一个可判定性问题（实际上是一个半可判定问题），所以这两种语法形式在实际中都无法得到应用。
2.1.2 乔姆斯基的形式句法理论
乔姆斯基的形式语法理论不仅是现代计算机科学的基础之一，也为语言学的研究打开了一个暂新的局面，对自然科学和社会科学的很多领域都产生了深远的影响，被称为“乔姆斯基革命”，在科学史上具有里程碑式的重要地位。
乔姆斯基的形式语法理论是一个不断演变、不断发展的过程。在1957年，乔姆斯基提出了“转换生成语法理论（TG）”，1970年代，发展成为“标准理论”，在1981年，乔姆斯基又提出了“管辖－约束理论（GB）”，1992年，提出了“最简方案（MP）”。
乔姆斯基的形式语法理论有一个核心思想，就是“普遍语法”的思想。他认为人有先天的语言习得机制，生来就具有一种普遍语法知识，这是人类独有的生理现象。人类各种语言之间共性（原则）是主要的，语言之间的个性（参数）是次要的。因此乔姆斯基后期的语言学理论（GB以后）又称为“原则＋参数”的语言学理论。
乔姆斯基早期的转换生成语法还比较简单，后来乔姆斯基语法理论越来越复杂，使得形式化的工作变得非常困难。所以现在计算语言学领域的研究中，已经很少有人采用乔姆斯基的形式语法体系。不过乔姆斯基的形式句法理论在语言学界还是很有生命力的，因为它确实可以解释很多其他理论很难解释的语言现象。
2.1.3 中心词驱动的短语结构语法（HPSG）和词汇功能语法（LFG）
HPSG和LFG属于非乔姆斯基阵营的语法理论中比较有生命力的两种。
他们与乔姆斯基语法理论的本质差别在于没有转换规则（乔姆斯基后期的理论中又称为α－移动），没有浅层结构和深层结构的区别。
从计算机实现的角度看，这两种理论都采用了特征结构这种形式来表达复杂的语言学知识并采用合一算法进行规则的推导。与乔姆斯基的语法理论不同，这两种语法理论都又很好的可实现性。因此这两种理论的发展一直和计算机的结合非常紧密。
有关这两种语法的详细资料，可到互联网上查询相应网站。
LFG：Stanford：http://www-lfg.stanford.edu/lfg/
Essex： http://clwww.essex.ac.uk/LFG/
HPSG：http://hpsg.stanford.edu/
下面仅通过几个图示简单介绍一下LFG，使读者对LFG有一个直观的映像。
在LFG中，一个句子的结构除了用一棵句法树（c-structure），还用一个特征结构（f-structure）来刻划这个句子的各种句法特征，如下图所示：

相应的，LFG的规则（包括词典中的词条）除了通常的短语结构规则形式外，还附带一些合一表达式，如下图所示（­其中表示父结点的特征结构，¯表示本结点的特征结构）：
规则：S → NP VP
­SUBJ =¯ ­ = ¯

词条：Gives V (­PRED) = ‘give <Agent, Theme, Recipient>’
(­TENSE) = present
(­SUBJ NUMBER) = sing
(­SUBJ PERSON) = 3

2.1.4 依存语法
依存语法也是一种使用非常广泛的语法形式。
与短语结构语法（PSG）的最大不同在于，依存语法的句法结构表示形式不是一棵句法层次结构的句法树，而是一棵依存树：依存树上的所有结点都是句子中的词，没有非终结符结点。例如句子“我喜欢看古典小说”的依存结构如下图所示：
喜欢
我
看
小说
古典

可以看到，在依存关系树中，丢失了句子中词与词之间的顺序关系。
应该说，依存语法并不是一种严格定义的语法形式。依存语法没有明确定义的规则形式。也没有明确规定依存关系是否要加上标记。实际的应用系统中，一般都会给依存关系加上句法或语义的标记。
1970年，美国计算语言学家J. 罗宾孙(J. Robinson)提出了依存语法的4条公理：
1. 一个句子只有一个成分是独立的；
2. 句子中的其它成分直接从属于某一成分；
3. 任何一个成分都不能从属于两个或两个以上的成分；
4. 如果成分A直接从属于成分B，而成分C在句子中位于A和B之间，那么，成分C或者从属于A，或者从属于B，或者从属于A和B之间的某一成分。
这四条公理比较准确界定了一个依存树所要满足的条件，得到了依存语法研究者的普遍接受。
2.1.5 链语法
链语法由美国CMU计算机学院的Daniel Sleator和美国Columbia Uiversity（的Davy Temperley共同提出，最早的文章是1991年的一个技术报告，题目是“Parsing English with a Link Grammar”。
链语法的网址是：http://www.link.cs.cmu.edu/link。
链语法词典中的词条如下图所示：

上面的一些词组成的一个句子通过句法分析得到下面的结构：

链语法的一个显著特点是分析的结果不是一棵句法树，而是一个有向图。
链语法的另一个特点是没有句法规则，只有几条简单的原则，用于规定句法成分之间互相结合的方式。链语法的语法知识都存放在词典中。
链语法的网站上提供了链语法分析器的完整源代码。
2.1.6 范畴语法
范畴语法语法的特点在于，把句法分析的过程变成了一种类似分数乘法中进行的“约分”运算。
举一个简单的例子：我喜欢红苹果。
在词典中，句子中的几个词分别表示为：
我：N
喜欢：N/S\N
红：N/N
苹果：N
句法分析的过程表现为：
红＋苹果：N/N + N => N
喜欢＋红苹果：N\S/N + N => N\S
我＋喜欢红苹果：N+N\S => S
和链语法一样，在范畴语法中，也没有规则，只有几条简单的原则，规定范畴之间如何进行“约分”，所有的语法信息都表现在词典中。
范畴语法在现在的形式语义学理论中有很重要的作用。
范畴语法的网站是：http://www.cs.man.ac.uk/ai/CG/。
2.2 句法分析算法
句法分析的过程就是将小的语法成分组合成大的语法成分的过程。虽然各种语法的形式相差很大，不过在句法分析的过程中采用的分析算法都是类似的（也有少数语法有自己特有的句法分析算法）。
2.2.1 常见的分析算法
常见的句法分析算法包括：
1. 自顶向下分析算法；
2. 自底向上分析算法；
3. 左角分析算法；
4. CYK算法；
5. Marcus确定性分析算法；
6. Earley算法；
7. Tomita算法（GLR算法）；
8. Chart算法；
等等。
这些算法都有各自的优缺点和适用的场合，由于篇幅关系，我们难以一一介绍。
目前应用得最为广泛的句法分析算法是Tomita算法和Chart算法。
Tomita算法是传统的LR分析算法的一种扩展，所有又被称为Generalized LR（GLR）算法。和LR算法一样，GLR算法也是一种移进－规约（Shift-Redu