自然语言理解-词法分析.ppt

词法分析语言根据词的形态结构分类分析型语言没有专门表示语法意义的附加成分汉语，藏语黏着型语言词内有专门表示语法意义的附加成分芬兰语，日语曲折性语言用词的形态变化表示语法关系英语，德语，法语什么是词？词是语言中最小的能独立运用的单位，是信息处理的基本单位。界定词的困难所在单字词与语素之间的划界词与短语之间的划界汉语自动分词把没有明显分界标志的字串自动切分为词串 背 景汉语的特点：汉语是大字符集的语言 英语有26个字母，而常用的汉字就有六七千个，总数超过五万 书面汉语的词与词之间没有明确的分隔标记 背 景 汉语中兼类现象严重 例如：“和”根据现代汉语词典可以有五种读音，六种词性，以及十六种不同的词义 印欧语系多有形态变化，而汉语缺少形态变化 例如：复数、单数，过去、现在，阴性、阳性等等汉语词法分析所面临的问题分词词表分词词表重叠词、词缀重叠词、词缀分词和理解，孰先孰后？分词和理解，孰先孰后？歧义切分字段歧义切分字段 专有名词的专有名词的识别识别 分词词表分词词表 汉语词的抽象定义（既“词是什么”）与具体判定（既“什么是词”）问题，语言学界并未完全解决 词表对自动分词而言，是最基础的“构件”分词词表分词词表 信息处理用现代汉语分词规范 迄今也没有一个公认的、具有权威性的词表，这是分词问题所面临的第一个困难汉语双字形容词的重叠形式 汉语单字形容词的重叠形式汉语双字动词的重叠形式汉语单字动词的重叠形式汉语其他词类的重叠形式 名词哥哥，人人山山水水，是是非非，方方面面，头头脑脑数词一一做了回答，两两结伴而来量词个个都是好样的，回回考满分副词常常，仅仅，的的确确汉语重叠词的特点汉语词能否重叠具有很强的个性特点研究研究工作工作有些词重叠后词性发生了变化形容词重叠后一般成为状态词个别量词重叠后可以成为其他词性回回：副词个个：名词汉语词缀前缀老鹰、老虎、老三、老王超豪华、超标准、超高速非党员后缀骨头、砖头、甜头、苦头、盼头、想头桌子、椅子、孩子、票子、房子文学家、指挥家、艺术家科学性、可能性、学术性碗儿、花儿、玩儿、份儿、片儿 分词和理解，孰先孰后？分词和理解，孰先孰后？计算机分词仍然面临知识短缺的大问题 计算机大概永远做不到像人那样先理解后分词 不可企求百分之百的正确切分，这是自动分词所面临的第二个困难汉语切分歧义例子公路局处理解放大道路面积水问题。南京市长江大桥说：歧义切分字段歧义切分字段 定义定义1.11.1 交集型歧义：交集型歧义：字串ABC，其中汉字字串A、B、C的长度均大于零，该字串可以切分为AB/C或A/BC，则称该字串为交集型歧义字串。例如：出现在出现/在（切分1）出现在出/现在（切分2）歧义切分字段歧义切分字段 定义定义1.21.2组组合合型型歧歧义义：字串AB，其中汉字字串A、B的长度均大于零，该字串可以切分成AB或A/B，则称该字串为组合型歧义字串。例如：马上马/上（切分1）马上马上（切分2）歧义切分字段歧义切分字段 混合型歧义：由交集型歧义和组合型歧义自身嵌套或两者交叉组合而产生的歧义人才能：这样的人才能经受住考验。人才能：这样的人才能经受住考验。人才能：这样的人才能经受住考验。真歧义和伪歧义真歧义确实能在真实语料中发现多种切分形式比如“应用于”、“地面积”伪歧义虽然有多种切分可能性，但在真实语料中往往取其中一种切分形式比如“挨批评”、“市政府”交集型歧义字段的链长链长：交集型歧义字段中含有交集字段的个数，称为链长。链长为1：和尚未链长为2：结合成分链长为3：为人民工作链长为4：中国产品质量结合成分子时链长为6：努力学习语法规则链长为7：治理解放大道路面积水真实语料中歧义字段的分布 汉语真实文本中的分词歧义情况 材料一：孙茂松等1999一个1亿字真实汉语语料库中抽取出的前4,619个高频交集型歧义切分覆盖了该语料库中全部交集型歧义切分的59.20%，其中4279个属伪歧义（占92.63%，如“和软件”、“充分发挥”、“情不自禁地”），覆盖率高达53.35%。材料二：刘开瑛2000，第4章78248个交集型歧义字段中，伪歧义：94%真歧义：6%汉语真实文本中的分词歧义情况（续）分词歧义的四个层级（何克抗等1991,50883字语料）词法歧义：84.1%（“用方块图形式加以描述”）句法歧义：10.8%（“他一阵风似的跑了”）语义歧义：3.4%（“学生会写文章”）语用歧义：1.7%（“美国会采取措施制裁伊拉克”）分词模型 句子侯选切分集切分歧义之解决结果待切分生成解空间在解空间中求解切分阶段一阶段二 歧义切分字段歧义切分字段分词模型 阶段一阶段一生成解空间 根据分词词表及其某种切分原则，找出输入句子的侯选切分集合，以供下一阶段处理 最大匹配法是极端之一，给出唯一侯选（侯选即解）分词模型 全切分法是另一个极端，给出输入句子的所有可能切分形式，可实现无盲点分析，代价是解空间膨胀太大，又会造成许多不必要的干扰 关键：能否在保证无切分盲点的前提下，给出尽可能小的解空间分词模型阶段二阶段二在解空间中求解解决切分歧义的策略，大致有三：基于规则基于规则 基于词频基于词频 基于隐基于隐MarkovMarkov模型模型 阶段二阶段二:在解空间中求解 基于规则基于规则 这类研究吸取了人工智能及专家系统的思想基于规则基于规则 主要困扰是：囿于目前汉语parser的能力，任何期望倚重parser作为解决歧义切分之手段的设想尚缺乏现实的基础；由于无法实现parsing，分词系统所能利用的句法、语义规则必然是局部的，基本上仅涉及若干毗邻词之间的线性关系，可靠性不强，难以建立完整、有效、无矛盾的体系。阶段二阶段二:在解空间中求解 基于词频基于词频 基于词频的排歧问题可抽象为求有向图两点间最优路径问题。较最大匹配法，可望将切分精确率提高约1%。基于词频基于词频 本质上这是一个关于词的零阶Markov模型（也称作unigram），存在明显缺陷：其表现不依赖于上下文而变化。例如：字段“只是”，或一律作为一个词被切出来，或一律被切成“只/是”（完全取决于“只”“是”和“只是”的词频阶段二阶段二:在解空间中求解 基于隐Markov模型 语法知识以统计形式量化在标记的概率转移矩阵中 表示简洁、均匀，处理灵活、一致，避免了采用规则系统的某些弊端；基于隐Markov模型 统计数据从不受任何限制的实际语料中获得，可有效提高分析系统的能力及覆盖面，并且分词结果能随时反馈到统计数据中，使系统有一定的自学习功能。模型的求解仍可归结为有向图两点最优路径问题基于隐Markov模型 关键：以隐Markov模型为主要手段解决切分歧义，是一种最有希望的方案，但“单打一”恐怕不能完全奏效，必须集成多种手段（方法）。专有名词专有名词的识别 许多分词算法都是在完备词表的假设下设计的，这一假设并不成立。新词不断涌现，而且专有名词虽然不新，但不可能尽收。专有名词专有名词的识别 一般说来，专有名词包括：中国人名 中国地名 译名 组织机构名 事件名 时间数量名 商标名专有名词专有名词的识别 陈陈/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 “陈平”人名 “美国美国”地名 “北京大学北京大学”、“中国科技大学中国科技大学”、“中国经济研究中心中国经济研究中心”及 “德克萨斯大学德克萨斯大学”属于组织机构名专有名词专有名词的识别 不同的语料，专名所占的比例也不同。对455万字的人民日报语料统计的结果显示：专名占5.74%，其中，中国人名占2.55%，地名占2.55%,外国译名占0.73%，如果不予处理，会对切分精确率造成比歧义字段更大的影响。研 究 进 展中文词语的分析过程：预处理过程的词语粗切分 切分排歧与未登录词识别 词性标注在实际的系统中，这三个过程可能相互交叉，反复融合，也可能不存在明显的先后次序 研 究 进 展主要的汉语自动分词系统有:北航的CDWS系统，国内公开的第一个实用性汉字分词系统，采用的自动分词方法为最大匹配法，辅助以词尾字构词检错技术，使用知识库进行纠错。北航的CASS系统，它使用的自动分词方法是正向增字最大匹配法，使用知识库处理歧义字段。研 究 进 展山西大学的ABWS分词系统,使用“两次扫描联想回溯”法，利用联想-回溯来有效地解决歧义组合结构的切分，同时兼有自动检错和纠错的功能。其分词子系统较好地利用了语言学中的词法知识、句法知识，并具有调用分词规则切分歧义字段和回收生词等功能。北师大的自动分词专家系统，首次将专家系统方法引入到分词系统中。研 究 进 展 清华大学SEG分词系统，此系统提供了带回溯的正向、反向、双向最大匹配法和全切分-评价切分算法，由用户来选择合适的切分算法。其特点则是带修剪的全切分-评价算法。清华大学SEGTAG系统，该系统对词典中的每一个重要的词都加上了切分标志，即标志“ck”或“qk”。通过这两种标志并使用几条规则来实现有限的全切分。为了获得切分结果，系统采用在有向图DAG上搜索最佳路径的方法，所运用的搜索算法有两种，即“动态规划”和“全切分搜索+叶子评价”，使用了词频、词类频度、词类共现频度等统计信息。研 究 进 展 中科院计算所的词语分析系统ICTCLAS，采用N-最短路径方法进行词语粗分（概率统计），然后用HMM的方法进行分词和标注的一体化处理。国家语委文字所应用句法分析技术的汉语自动分词，此分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分歧义。切词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分可能中选择出合理的切分结果。研 究 进 展 复旦分词系统，首先，使用正向最小匹配和逆向最大匹配对文本进行双向扫描，如果两种扫描结果相同，则认为切分正确，否则就判别其为歧义字段，使用构词规则和词频统计信息来进行排歧。哈工大的统计分词系统，是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词匹配结合起来。研 究 进 展 杭州大学改进的MM分词系统，其实质为MM+规则。微软研究院多国语言处理平台NLPWin中的中文词语分析词系统，采用了切词-句法分析一体化的方法，使用语法规则并以概率模型作导向来进行排歧。北京大学计算语言学研究所的汉语切分与标注系统，把分词和词类标注结合起来，采用基于规则的标注排歧与基于语料库统计模型的排歧相结合的处理方法。研 究 进 展 北大计算语言汉语文本分析系统，该系统中采用了一种综合性歧义切分处理方法，其要点有：把汉语基本词典中所有的歧义词标记出来；把所有的歧义字段分为两类：简单歧义字段和复杂歧义字段；在切分时，如果匹配出来的词不是歧义词，则可以安全地切分出来；研 究 进 展 当匹配出歧义词时，根据词条的歧义信息（歧义偏移值）判断当前歧义字段的类别：如果是简单歧义，则使用一条非常简单的规则即可全部得解，即优先切出非歧义词；如果是复杂歧义字段，则调用一个“侦歧”过程，进一步判断歧义字段的类型是“歧义词+歧义词”还是“连续型歧义字段”；考察词条的“歧义触发信息”和“歧义消隐信息”，即可解决所有局部（直接上下文）的歧义；通过浅层句法分析及其同步的语义检查（义类代码及配价项的检查），消解句子级歧义。一个具体系统前处理在前处理中解决的问题文本的一致性文本中的控制词文本的一致性中文编码 GB：中文词、GB 标点、GB字符。ASCII：ASCII 标点、ASCII字符.同一文本中会出现GB和ASCII例鲁 迅 说 ：“世 上 本 没 有 路！”鲁 迅 说 :世 上 本 没 有 路!鲁 迅 说 :“世 上 本 没 有 路!”例鲁 迅 说 ：“世 上 本 没 有 路！”C2B3 D1B8 A3BA A1B0 B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 A3A1 A1B1鲁 迅 说 :世 上 本 没 有 路!C2B3 D1B8 A3BA 3A 22 B5CA C0C9 B1BE C3BB D3D0 C2B7 21 22鲁 迅 说 :“世 上 本 没 有 路!”C2B3 D1B8 A3BA 3A B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 21 A1B1GB、ASCII混用问题数据结构GB two bytesASCII one byte系统必须正确识别，不然就会出现乱码。解决方法将ASCII扩展到两个字节鲁 迅 说 ：“世 上 本 没 有 路！”C2B3 D1B8 A3BA A1B0 B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 A3A1 A1B1鲁 迅 说 :世 上 本 没 有 路 !C2B3 D1B8 A3BA 003A 0022 B5CA C0C9 B1BE C3BB D3D0 C2B7 0021 0022鲁 迅 说 :“世 上 本 没 有 路 !”C2B3 D1B8 A3BA 003A B0CB B5CA C0C9 B1BE C3BB D3D0 C2B7 0021 A1B1控制词问题控制此并不影响人的理解，但影响系统的识别这就是人们常说的鹬蚌相争的故事。这就是人们常说的鹬蚌相 争的故事。怎样做？“鹬蚌相争”是词组（成语）。“鹬蚌相争”还是成语吗？系统必须删除“”才能处理文本。解决方法删除所有控制词（空格、回车、制表符）。为便于人的阅读，在段落之间保留控制词。分词全切分 切分将一个字符串分为几部分普通全切分长度为N的字符串有2n-1个全切分结果例：太平洋保险保太平 太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平。太平洋保险保太平太平洋保险保太平普通全切分是无用的2n-1 个结果中绝大多数是没有用的需要重新定义全切分重定义切分切分 将一个字符串分为几个人类能理解的部分太平洋 保险 保太 平假设这些部分是词典中的词在 2n-1 个结果中选择每一部分要么是词典中的词，要么长度为一选择结果太平洋保险保太平太平 洋保险保太平太平洋保险保太平太平洋保险保太平太平 洋保险保太平太平洋保险保太平太平洋保险保太平太平 洋保险保太平太平洋保险保太平太平洋保险保太平太平 洋保险保太平太平洋保险保太平全切分问题怎样生成结果怎样压缩时间和空间的复杂度弧系统使用户来表示一个切分部分Arc 是相应的数据结构.typedef struct tagArcWWunsigned int uBegin;unsigned int uEnd;WordItem*uCode;UINTuCatThis;ArcWW;Member of ArcuBegin：弧的起点uEnd：弧的终点uCode：该切分单位在词典中的位置uCatThis：词性，在标注部分填入使用弧太平洋 保险 保 太平弧表示为：太平洋 保险 保 太平0 1 2 3 4 5 6 7 8在数据结构中uBeginuEnduCode03355668太平太平洋保保险全切分的弧表示uBeginuEnduCode03太平洋02太平01太12平23洋35保险34保45险56保68太平67太78平问题转换对于一个字符串作全切分得到包含所有切分单位的弧集词表结构Index太WordMax match itemTag InfoTag InfoTag Info太/a:0.12350:0.3435太平太a:0.0342ad:0.0320:0.0543太平洋太平n:0.01240:0.0324最大匹配项为了提高效率，我们引入了最大匹配项的概念。太平洋保险保太平太平洋太平太(红色的是最大匹配项)词典词的最大匹配项词典词的最大匹配项是词典中的词。最大匹配项是词的最大真前缀。不然的话最大匹配项为空。字符串S的最大匹配词字符串S的最大匹配词是词典中的词最大匹配词是S的最大前缀。不然的话，最大匹配词是S的第一个词。分词全切分生成所有可能的切分结果切分的结果是其中之一。生成正确的切分结果=在全切分结果中选择正确的一个切分全切分的工作=列举所有的歧义l切分=消歧=在全切分结果中选择正确的那一个=选择不同的切分算法=使用不同的切分策略切分全切分生成一个弧集不同的弧的组合表示不同的切分结果太平洋保险保太平最大正向选择策略：自左到右都选择最长的候选项 太平洋保险保太平 最大正向最大正向算法中弧的定义：第一条最大正向弧的 uBegin 是 0.第n+1条弧的uBegin是第n条弧的uEnd.最大正向弧是在所有uBegin相同的弧中uEnd最大的那条。最小正向最小正向算法中弧的定义：第一条最小正向弧的 uBegin 是 0.第n+1条弧的uBegin是第n条弧的uEnd.最大正向弧是在所有uBegin相同的弧中uEnd最小的那条。切分静止点(SSP)SSP在每一个切分路径中都存在于两条弧之间。太平洋保险保太平0 1 2 3 4 5 6 7 8切分静止点(SSP)全切分的结果是从字串头到尾。一些算法需要自尾到头的信息最大逆向选择策略：自右向左每次选择最长的候选项。太平洋保险保太平最大逆向最大逆向算法的弧定义：在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).在一个SSAS中，第一条最大逆向弧的uEnd是尾SSP。第n+1条弧的uEnd 是第n条弧的uBegin。在一个SSAS中，最后一条最大逆向弧的uBegin是头SSP。最大逆向弧是所有有相同的uEnd的弧中uBegin最小的那条。最小逆向Choice policy：自右向左选择最小的候选项 太平洋保险保太平最小逆向最小逆向算法弧的定义：在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).在一个SSAS中，第一条最小逆向弧的uEnd是尾SSP。第n+1条弧的uEnd 是第n条弧的uBegin。在一个SSAS中，最后一条最小逆向弧的uBegin是头SSP。最小逆向弧是所有有相同的uEnd的弧中uBegin最大的那条。最大概率令S=C1C2Cn-1Cn=(C1.Cx1)(Cx1+1Cx2)（Cxm-1.Cxm)=W1W2.Wm根据贝叶斯公式，P(W|C)=P(W)P(C|W)/P(C)P(C)是确定值，P(C|W)是给定词串情况下字串出现的概率，可以认为是1。所以，P(W|C)P(W)最大概率最大概率算法弧的定义：在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).在一个SSAS中，第一条最大概率弧的uEnd是尾SSP。第n+1条弧的uEnd 是第n条弧的uBegin。在一个SSAS中，最后一条最大概率弧的uBegin是头SSP。最大概率弧集是每条弧概率之积最大的那个弧集。最短路径选择策略：选择含弧最少的结果太平洋保险保太平4 arcs,the smallest num of an arc chain.最短路径最短路径算法的弧定义：在两个SSP中的弧集称为切分静态弧集 Segment Static Arc Set(SSAS).在一个SSAS中，第一条最短路径弧的uEnd是尾SSP。第n+1条弧的uEnd 是第n条弧的uBegin。在一个SSAS中，最后一条最短路径弧的uBegin是头SSP。最短路径弧集是拥有弧数最少的弧集。屈折语的词法分析词：词根词缀词尾词法分析的工作：识别屈折变化。如take,took,takes派生变化。如morphology morphological复合变化屈折语的词法分析技术描述性的词法分析过程性的词法分析基于规则的词法分析描述性的词法分析为每个单词及其变型设置一个词典入口例如do(PRES,PR1,PR2)does(PRES,PR3)did(PAST)done(VEN)相当于字典检索不适用于大词汇量的系统过程性的词法分析根据词的变形规律进行分析例：IF preword的词尾为ied,THEN把preword复制到word去掉word的词尾ied，并在word词尾加y如果能在词典中检索出word，则把PAST，VEN的属性付给word。否则，IF preword的词尾为ed，THEN把preword复制到word去掉word的词尾ed如果能在词典中检索出word，则把PAST，VEN的属性付给word。优点：减少了词典入口数量，提高辞典的检索速度缺点对于形态丰富的语言来说效率低。基于规则的词法分析词的表层形式和深层形式Walk是深层形式Walks是表层形式词法分析就是寻找两者之间的映射基于规则的词法分析规则示例.名词复数*s-*,(PLUR)*es-*,(PLUR)*ies-*y,(PLUR).动词第三人称单数*s-*(SINGULAR)(THIRDPERSON)(PRESENT)*es-*(SINGULAR)(THIRDPERSON)(PRESENT)*ies-*y(SINGULAR)(THIRDPERSON)(PRESENT)基于规则的词法分析规则示例.动词现在分词*ing-*(VING)*ing-*e(VING)*ying-*ie(VING)*?ing-*?(VING).动词过去分词、过去式*ed-*(PAST,VEN)*ed-*e(PAST,VEN)*ied-*y(PAST,VEN)*?ed-*?(PAST,VEN)基于规则的词法分析输入：一个单词输出：一个或多个单词，其中每个单词还原为原形加前后缀（可以有多个）算法：（略）词法分析的分析程度词干层。如：impossibilities-impossibility+ies词根层。如：impossibilities-im+poss+ibil+it+ies分析程度取决于自然语言处理系统的深度：不解决未定义词，分析到词干层解决未定义词，要分析到词根层。