自然语言理解词法分析

1、词法分析语言根据词的形态结构分类n分析型语言n没有专门表示语法意义的附加成分n汉语，藏语n黏着型语言n词内有专门表示语法意义的附加成分n芬兰语，日语n曲折性语言n用词的形态变化表示语法关系n英语，德语，法语什么是词？n词是语言中最小的能独立运用的单位，是信息处理的基本单位。n界定词的困难所在n单字词与语素之间的划界n词与短语之间的划界n汉语自动分词n把没有明显分界标志的字串自动切分为词串 背 景汉语的特点： 汉语是大字符集的语言 英语有26个字母，而常用的汉字就有六七千个，总数超过五万 书面汉语的词与词之间没有明确的分隔标记 背 景 汉语中兼类现象严重 例如：“和”根据现代汉语词典可以有五种读

2、音，六种词性，以及十六种不同的词义 印欧语系多有形态变化，而汉语缺少形态变化 例如：复数、单数，过去、现在，阴性、阳性等等汉语词法分析所面临的问题n分词词表分词词表n重叠词、词缀重叠词、词缀n分词和理解，孰先孰后？分词和理解，孰先孰后？ n歧义切分字段歧义切分字段 n专有名词的专有名词的识别识别 分词词表分词词表 汉语词的抽象定义（既“词是什么”）与具体判定（既“什么是词”）问题，语言学界并未完全解决 词表对自动分词而言，是最基础的“构件” 分词词表分词词表 信息处理用现代汉语分词规范 迄今也没有一个公认的、具有权威性的词表，这是分词问题所面临的第一个困难汉语双字形容词的重叠形式 汉语单字形容

3、词的重叠形式汉语双字动词的重叠形式汉语单字动词的重叠形式汉语其他词类的重叠形式 n名词n哥哥，人人n山山水水，是是非非，方方面面，头头脑脑n数词n一一做了回答，两两结伴而来n量词n个个都是好样的，回回考满分n副词n常常，仅仅，的的确确汉语重叠词的特点n汉语词能否重叠具有很强的个性特点n研究研究n工作工作n有些词重叠后词性发生了变化n形容词重叠后一般成为状态词n个别量词重叠后可以成为其他词性n回回：副词n个个：名词汉语词缀n前缀n老鹰、老虎、老三、老王n超豪华、超标准、超高速n非党员n后缀n骨头、砖头、甜头、苦头、盼头、想头n桌子、椅子、孩子、票子、房子n文学家、指挥家、艺术家n科学性、可能性、

4、学术性n碗儿、花儿、玩儿、份儿、片儿 分词和理解，孰先孰后？分词和理解，孰先孰后？ 计算机分词仍然面临知识短缺的大问题 计算机大概永远做不到像人那样先理解后分词 不可企求百分之百的正确切分，这是自动分词所面临的第二个困难汉语切分歧义n例子n公路局处理解放大道路面积水问题。n南京市长江大桥说： 歧义切分字段歧义切分字段 定义定义1.11.1 交集型歧义：交集型歧义：字串ABC，其中汉字字串A、B、C的长度均大于零，该字串可以切分为AB/C或A/BC，则称该字串为交集型歧义字串。例如：出现在出现/ 在（切分1）出现在出/现在（切分2） 歧义切分字段歧义切分字段 定义定义1.21.2组合型歧义：组合

5、型歧义：字串AB，其中汉字字串A、B的长度均大于零，该字串可以切分成AB或A/B，则称该字串为组合型歧义字串。例如： 马上马/上（切分1）马上马上 （切分2） 歧义切分字段歧义切分字段 n混合型歧义：由交集型歧义和组合型歧义自身嵌套或两者交叉组合而产生的歧义n人才能：这样的人才能经受住考验。n人才能：这样的人才能经受住考验。n人才能：这样的人才能经受住考验。 真歧义和伪歧义n真歧义n确实能在真实语料中发现多种切分形式n比如“应用于”、“地面积”n伪歧义n虽然有多种切分可能性，但在真实语料中往往取其中一种切分形式n比如“挨批评”、“市政府”交集型歧义字段的链长n链长：交集型歧义字段中含有交集字段

6、的个数，称为链长。n链长为1：和尚未n链长为2：结合成分n链长为3：为人民工作n链长为4：中国产品质量结合成分子时n链长为6：努力学习语法规则n链长为7：治理解放大道路面积水真实语料中歧义字段的分布 汉语真实文本中的分词歧义情况 n材料一：孙茂松等1999n一个1亿字真实汉语语料库中抽取出的前4,619个高频交集型歧义切分覆盖了该语料库中全部交集型歧义切分的59.20%，其中4279个属伪歧义（占92.63%，如“和软件”、“充分发挥”、“情不自禁地”），覆盖率高达53.35%。n材料二：刘开瑛2000，第4章n78248个交集型歧义字段中，n伪歧义：94% n真歧义：6% 汉语真实文本中的分

7、词歧义情况（续） n分词歧义的四个层级（何克抗等1991, 50883字语料）n词法歧义：84.1% （“用方块图形式加以描述”）n句法歧义：10.8% （“他一阵风似的跑了”）n语义歧义：3.4% （“学生会写文章”）n语用歧义：1.7% （“美国会采取措施制裁伊拉克”）分词模型 句子侯选切分集切分歧义之解决结果待切分生成解空间在解空间中求解切分阶段一阶段二 歧义切分字段歧义切分字段分词模型 阶段一阶段一生成解空间 根据分词词表及其某种切分原则，找出输入句子的侯选切分集合，以供下一阶段处理 n 最大匹配法是极端之一，给出唯一侯选（侯选即解）分词模型 n 全切分法是另一个极端，给出输入句子的所

8、有可能切分形式，可实现无盲点分析，代价是解空间膨胀太大，又会造成许多不必要的干扰 关键：能否在保证无切分盲点的前提下，给出尽可能小的解空间分词模型阶段二阶段二在解空间中求解解决切分歧义的策略，大致有三： 基于规则基于规则 基于词频基于词频 基于隐基于隐MarkovMarkov模型模型 阶段二阶段二:在解空间中求解 基于规则基于规则 这类研究吸取了人工智能及专家系统的思想基于规则基于规则 主要困扰是： n 囿于目前汉语parser的能力，任何期望倚重parser作为解决歧义切分之手段的设想尚缺乏现实的基础； n 由于无法实现parsing，分词系统所能利用的句法、语义规则必然是局部的，基本上仅涉

9、及若干毗邻词之间的线性关系，可靠性不强，难以建立完整、有效、无矛盾的体系。 阶段二阶段二:在解空间中求解 基于词频基于词频 基于词频的排歧问题可抽象为求有向图两点间最优路径问题。较最大匹配法，可望将切分精确率提高约1%。基于词频基于词频 本质上这是一个关于词的零阶Markov模型（也称作unigram），存在明显缺陷：其表现不依赖于上下文而变化。例如：字段“只是”，或一律作为一个词被切出来，或一律被切成“只/是”（完全取决于“只”“是”和“只是”的词频阶段二阶段二:在解空间中求解 基于隐Markov模型 语法知识以统计形式量化在标记的概率转移矩阵中 n 表示简洁、均匀，处理灵活、一致，避免了采

10、用规则系统的某些弊端； 基于隐Markov模型 n 统计数据从不受任何限制的实际语料中获得，可有效提高分析系统的能力及覆盖面，并且分词结果能随时反馈到统计数据中，使系统有一定的自学习功能。模型的求解仍可归结为有向图两点最优路径问题基于隐Markov模型 关键：以隐Markov模型为主要手段解决切分歧义，是一种最有希望的方案，但“单打一”恐怕不能完全奏效，必须集成多种手段（方法）。专有名词专有名词的识别 许多分词算法都是在完备词表的假设下设计的，这一假设并不成立。 新词不断涌现，而且专有名词虽然不新，但不可能尽收。专有名词专有名词的识别 一般说来，专有名词包括： 中国人名 中国地名 译名 组织机

11、构名 事件名 时间数量名 商标名专有名词专有名词的识别 陈陈/nhf /nhf 平平/nhs/nhs 为/vl 北京大学北京大学/ni/ni 中国经济研究中国经济研究中心中心/ni/ni 经济学/n 教授/n ，/w 中心/n 副/f 主任/n （/w 主管/v 科研/j ）/w 。/w 1968/m 年/nt 获/v 中国科技大学中国科技大学/ni/ni 物理系/n 学士/n 学位/n ，/w 1987/m 年/nt 获/v 美国美国/ns/ns 德克萨斯大学德克萨斯大学/ni/ni 物理学/n 博士/n 学位/n 。/w n “陈平” 人名 n “美国美国” 地名 n “北京大学北京大学”

12、、“中国科技大学中国科技大学” 、“中国经济研究中心中国经济研究中心” 及 “德克萨斯德克萨斯大学大学” 属于组织机构名专有名词专有名词的识别 不同的语料，专名所占的比例也不同。 对455万字的人民日报语料统计的结果显示：专名占5.74%，其中，中国人名占2.55%，地名占2.55%,外国译名占0.73%，如果不予处理，会对切分精确率造成比歧义字段更大的影响。 研 究 进 展中文词语的分析过程： 预处理过程的词语粗切分 切分排歧与未登录词识别 词性标注在实际的系统中，这三个过程可能相互交叉，反复融合，也可能不存在明显的先后次序 研 究 进 展主要的汉语自动分词系统有:北航的CDWS系统，国内公

13、开的第一个实用性汉字分词系统，采用的自动分词方法为最大匹配法，辅助以词尾字构词检错技术，使用知识库进行纠错。北航的CASS系统，它使用的自动分词方法是正向增字最大匹配法，使用知识库处理歧义字段。 研 究 进 展山西大学的ABWS分词系统,使用“两次扫描联想回溯”法，利用联想-回溯来有效地解决歧义组合结构的切分，同时兼有自动检错和纠错的功能。其分词子系统较好地利用了语言学中的词法知识、句法知识，并具有调用分词规则切分歧义字段和回收生词等功能。北师大的自动分词专家系统，首次将专家系统方法引入到分词系统中。 研 究 进 展 清华大学SEG分词系统，此系统提供了带回溯的正向、反向、双向最大匹配法和全切

14、分-评价切分算法，由用户来选择合适的切分算法。其特点则是带修剪的全切分-评价算法。 清华大学SEGTAG系统，该系统对词典中的每一个重要的词都加上了切分标志，即标志“ck”或“qk” 。通过这两种标志并使用几条规则来实现有限的全切分。为了获得切分结果，系统采用在有向图DAG上搜索最佳路径的方法，所运用的搜索算法有两种，即“动态规划”和“全切分搜索+叶子评价”，使用了词频、词类频度、词类共现频度等统计信息。 研 究 进 展 中科院计算所的词语分析系统ICTCLAS，采用N-最短路径方法进行词语粗分（概率统计），然后用HMM的方法进行分词和标注的一体化处理。 国家语委文字所应用句法分析技术的汉语自

15、动分词，此分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分歧义。切词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分可能中选择出合理的切分结果。 研 究 进 展 复旦分词系统，首先，使用正向最小匹配和逆向最大匹配对文本进行双向扫描，如果两种扫描结果相同，则认为切分正确，否则就判别其为歧义字段，使用构词规则和词频统计信息来进行排歧。 哈工大的统计分词系统，是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词匹配结合起来。 研 究 进 展 杭州大学改进的MM分词系统，其实质为MM+规则。 微软研究院多国语言处理平台NLPWin中的中文词语分析词系统，采用了切词-句法分

16、析一体化的方法，使用语法规则并以概率模型作导向来进行排歧。 北京大学计算语言学研究所的汉语切分与标注系统，把分词和词类标注结合起来，采用基于规则的标注排歧与基于语料库统计模型的排歧相结合的处理方法。 研 究 进 展 北大计算语言汉语文本分析系统，该系统中采用了一种综合性歧义切分处理方法，其要点有： n 把汉语基本词典中所有的歧义词标记出来； n 把所有的歧义字段分为两类：简单歧义字段和复杂歧义字段； n 在切分时，如果匹配出来的词不是歧义词，则可以安全地切分出来； 研 究 进 展 n 当匹配出歧义词时，根据词条的歧义信息（歧义偏移值）判断当前歧义字段的类别：如果是简单歧义，则使用一条非常简单的

17、规则即可全部得解，即优先切出非歧义词； n 如果是复杂歧义字段，则调用一个“侦歧”过程，进一步判断歧义字段的类型是“歧义词+歧义词”还是“连续型歧义字段”；考察词条的“歧义触发信息”和“歧义消隐信息”，即可解决所有局部（直接上下文）的歧义； n 通过浅层句法分析及其同步的语义检查（义类代码及配价项的检查），消解句子级歧义。一个具体系统Raw textpretreatmetFormattedtextFull SegmentArc SetSegmentSelectedarc setPosSelected &tagged arcsetSegmented& taggedtextPost

18、treatmentDictionary前处理Raw textpretreatmetFormattedtextFull SegmentArc SetSegmentSelectedarc setPosSelected &tagged arcsetSegmented& taggedtextPosttreatmentDictionary在前处理中解决的问题n文本的一致性n文本中的控制词文本的一致性n中文编码 GB：中文词 、GB 标点、GB字符。 ASCII： ASCII 标点 、ASCII字符.n同一文本中会出现GB和ASCII例n鲁 迅 说 ： “ 世 上 本 没 有 路 ！ ”n

19、鲁 迅 说 : 世 上 本 没 有 路 ! n鲁 迅 说 : “ 世 上 本 没 有 路 ! ”例n鲁 迅 说 ： “ 世 上 本 没 有 路 ！ ”nC2B3 D1B8 A3BA A1B0 B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 A3A1 A1B1n鲁 迅 说 : 世 上 本 没 有 路 ! nC2B3 D1B8 A3BA 3A 22 B5CA C0C9 B1BE C3BB D3D0 C2B7 21 22n鲁 迅 说 : “ 世 上 本 没 有 路 ! ”nC2B3 D1B8 A3BA 3A B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7

20、21 A1B1GB、ASCII混用问题n数据结构GB two bytesASCII one byten系统必须正确识别，不然就会出现乱码。解决方法n将ASCII扩展到两个字节n鲁 迅 说 ： “ 世 上 本 没 有 路 ！ ”nC2B3 D1B8 A3BA A1B0 B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 A3A1 A1B1n鲁 迅 说 : 世 上 本 没 有 路 ! nC2B3 D1B8 A3BA 003A 0022 B5CA C0C9 B1BE C3BB D3D0 C2B7 0021 0022n鲁 迅 说 : “ 世 上 本 没 有 路 ! ”nC2B3 D1

21、B8 A3BA 003A B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 0021 A1B1控制词问题n控制此并不影响人的理解，但影响系统的识别这就是人们常说的鹬蚌相争的故事。 这就是人们常说的鹬蚌相 争的故事。怎样做？n“鹬蚌相争” 是词组（成语）。n“鹬蚌相争”还是成语吗？系统必须删除“”才能处理文本。解决方法n删除所有控制词（空格、回车、制表符）。n为便于人的阅读，在段落之间保留控制词。分词Raw textpretreatmetFormattedtextFull SegmentArc SetSegmentSelectedarc setPosSelected &

22、;tagged arcsetSegmented& taggedtextPosttreatmentDictionary全切分 n切分将一个字符串分为几部分n普通全切分长度为N的字符串有2n-1个全切分结果例：太平洋保险保太平 n太平洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平洋保险保太平n。n。n太平洋保险保太平n太平洋保险保太平普通全切分是无用的n2n-1 个结果中绝大多数是没有用的n需要重新定义全切分重定义切分n切分 n将一个字符串分为几个人类能理解的部分n太平洋 保险 保太 平n假设这些部分是词典中的词在 2n-1 个

23、结果中选择n每一部分要么是词典中的词，n要么长度为一选择结果n太平洋保险保太平n太平 洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平 洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平 洋保险保太平n太平洋保险保太平n太平洋保险保太平n太平 洋保险保太平n太平洋保险保太平全切分问题n怎样生成结果n怎样压缩时间和空间的复杂度弧n系统使用户来表示一个切分部分nArc 是相应的数据结构.typedef struct tagArcWWunsigned int uBegin;unsigned int uEnd;WordItem*uCode;UINTuCatThis;ArcWW;Member

24、of ArcnuBegin：弧的起点nuEnd：弧的终点nuCode：该切分单位在词典中的位置nuCatThis：词性，在标注部分填入使用弧n太平洋 保险 保 太平n弧表示为：n太平洋 保险 保 太平n0 1 2 3 4 5 6 7 8在数据结构中uBeginuEnduCode03355668太平太平洋保保险全切分的弧表示uBeginuEnduCode03太平洋02太平01太12平23洋35保险34保45险56保68太平67太78平问题转换n对于一个字符串作全切分n得到包含所有切分单位的弧集词表结构Index太WordMax match itemTag InfoTag InfoTag Info

25、太/a: 0.12350: 0.3435太平太a: 0.0342ad: 0.0320: 0.0543太平洋太平n: 0.01240: 0.0324最大匹配项n为了提高效率，我们引入了最大匹配项的概念。n太平洋保险保太平n太平洋n太平n太(红色的是最大匹配项)词典词的最大匹配项n词典词的最大匹配项是词典中的词。n最大匹配项是词的最大真前缀。n不然的话最大匹配项为空。字符串S的最大匹配词n字符串S的最大匹配词是词典中的词n最大匹配词是S的最大前缀。n不然的话，最大匹配词是S的第一个词。分词n全切分生成所有可能的切分结果n切分的结果是其中之一。n生成正确的切分结果 = 在全切分结果中选择正确的一个切

26、分n全切分的工作 = 列举所有的歧义l切分=消歧 = 在全切分结果中选择正确的那一个= 选择不同的切分算法= 使用不同的切分策略切分n全切分生成一个弧集n不同的弧的组合表示不同的切分结果太平洋保险保太平最大正向n选择策略：自左到右都选择最长的候选项 n太平洋保险保太平 最大正向n最大正向算法中弧的定义：n第一条最大正向弧的 uBegin 是 0.n第n+1条弧的uBegin是第n条弧的uEnd.n最大正向弧是在所有uBegin相同的弧中uEnd最大的那条。最小正向n最小正向算法中弧的定义：n第一条最小正向弧的 uBegin 是 0.n第n+1条弧的uBegin是第n条弧的uEnd.n最大正向弧

27、是在所有uBegin相同的弧中uEnd最小的那条。切分静止点(SSP)nSSP在每一个切分路径中都存在于两条弧之间。太平洋保险保太平0 1 2 3 4 5 6 7 8切分静止点(SSP)n全切分的结果是从字串头到尾。n一些算法需要自尾到头的信息最大逆向n选择策略：自右向左每次选择最长的候选项。n太平洋保险保太平最大逆向n最大逆向算法的弧定义：n在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).n在一个SSAS中，第一条最大逆向弧的uEnd是尾SSP。 n第n+1条弧的uEnd 是第n条弧的uBegin。n在一个SSAS中，最后一条最大逆向弧的uBe

28、gin是头SSP。n最大逆向弧是所有有相同的uEnd的弧中uBegin最小的那条。最小逆向nChoice policy：自右向左选择最小的候选项 n太平洋保险保太平最小逆向n最小逆向算法弧的定义：n在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).n在一个SSAS中，第一条最小逆向弧的uEnd是尾SSP。 n第n+1条弧的uEnd 是第n条弧的uBegin。n在一个SSAS中，最后一条最小逆向弧的uBegin是头SSP。n最小逆向弧是所有有相同的uEnd的弧中uBegin最大的那条。最大概率n令S=C1C2Cn-1Cn=(C1.Cx1)(Cx1+1

29、Cx2)（Cxm-1.Cxm) =W1W2.Wmn根据贝叶斯公式，P(W|C)=P(W)P(C|W)/P(C)nP(C)是确定值， P(C|W)是给定词串情况下字串出现的概率，可以认为是1。n所以， P(W|C)P(W)最大概率n最大概率算法弧的定义：n在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).n在一个SSAS中，第一条最大概率弧的uEnd是尾SSP。 n第n+1条弧的uEnd 是第n条弧的uBegin。n在一个SSAS中，最后一条最大概率弧的uBegin是头SSP。n最大概率弧集是每条弧概率之积最大的那个弧集。最短路径n选择策略：选择含弧

30、最少的结果n太平洋保险保太平n4 arcs, the smallest num of an arc chain.最短路径n最短路径算法的弧定义：n在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).n在一个SSAS中，第一条最短路径弧的uEnd是尾SSP。 n第n+1条弧的uEnd 是第n条弧的uBegin。n在一个SSAS中，最后一条最短路径弧的uBegin是头SSP。n最短路径弧集是拥有弧数最少的弧集。屈折语的词法分析n词：n词根n词缀n词尾n词法分析的工作：识别n屈折变化。如take, took, takesn派生变化。如morphology morphologicaln复合变化屈折语的词法分析技术n描述性的词法分析n过程性的词法分