（计算机软件与理论专业论文）面向普适计算办公环境的汉语处理技术的研究.pdf

ab s t r a c t ab s t r a c t t h e re a l p u r p o s e o f p e r v a s i v e c o m p u t i n g i s h u m a n - c e n t e r e d c o m p u t i n g , w h i c h b r i n g s a b u n d a n t c o m p u ta t i o n a n d c o m m u n i c a t i o n , a s p e rv a s i v e a n d fr e e a s a i r , n a t u r a ll y i n t o p e o p l e s l i v e s . s o c o n v e n i e n c e a n d fl e x i b i l i t y o f p e r s o n - m a c h i n e i n t e r a c t i o n i s e s s e n t i a l , w h i c h r a i s e s h i g h e r r e q u e s t t o s y s t e m a b i l i t y o f t h e n a t u r a l l a n g u a g e p r o c e s s i n g , m a k i n g t h e s y s t e m u n d e r s t a n d u s e r re q u i r e m e n t , p r o v i d i n g th e s e r v i c e a c t i v e l y f o r t h e c u s t o m e r , w i t h o u t i n t e r f e r e n c e o f p e o p l e s a tt e n t i o n . i n p e r v a s i v e c o m p u t i n g e n v i r o n me n t , t h e n a t u r a l l a n g u a g e p r o c e s s i n g t e c h n o l - o g y i n i n t e l l i g e n c e o f f i c e s y s t e m w a s re s e a r c h e 氏a n d a p l a t f o r m o f n l p w a s i m p l e m e n t e d t o p r o v i d e a s y n t a c t i c a n d s e m a n t i c i n t e r f a c e f o r t h e f o l l o w i n g w o r k . t h e re s e a r c h o f s y n t a x a n a l y s i s w a s m a i n l y f o c u s e d o n i n t h i s a r t i c l e t o d e v e l o p a s y n t a x a n a l y s i s s y s t e m , w h i c h w a s d i v i d e d i n t o t h r e e m a i n t a s k s : w o r d s e g m e n t a t i o n , p a rt o f s p e e c h t a g g i n g a n d s y n t a x a n a l y s i s . t h e s e t h ree t a s k s w e r e r e a li z e d w i t h t w o m o d u l e s : t h e w o r d s e g m e n t a t i o n a n d p a r t o f s p e e c h t a g g i n g m o d u l e , t h e s y n t a x a n a l y s i s m o d u l e . t h e m a x i m u m m a t c h b a s e d a p p r o a c h a l g o r it h m s w a s a d o p t e d a n d i m p r o v e d c h a rt a l g o r i t h m b a s e d o n c o n t e x t w a s a d o p t e d t o i m p l e m e n t t h e m o d u l e s s e p a r a t e l y . h a v i n g a n a l y z e d t h e c h a r a c t e r i s t i c s a n d m e t h o d s o f t h e t w o m o d u l e s , t h e a l g o r it h m fl o w , t h e a n a l y s i s t a c t i c s , a n d t h e p r o c e d u re o f re a l i z a t i o n w e re p r o v i d e 氏 a n d a l s o s i m p l e a n a l y s i s o f a l g o r i t h m e ff i c i e n c y w a s g i v e n . a t l a s t , a s i m p l e s u m m a ry a n d o u t l o o k o f t h e w o r k i n t h i s p a p e r w a s p r o v i d e 氏 a n d t h e re s e a r c h me t h o d o f s e m a n t i c a n a l y s i s w a s p u t f o r w a r d . k e y wo r d s p e r v a s i v e c o m p u t i n g , n a t u r a l l a n g u a g e p r o c e s s i n g , l e x i c a l a n a l y s i s , s y n t a x a n a l y s i s 图目录 图 目 录 图1 . 1系统处理流程图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 图2 . 1 c h o m s k y 形式语法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5 图3 . 1语言理解系统总体设计图 . . . . . . . . . . . . . . . . . . . . . 2 1 图4 . 1词典的结构示例 . . . . . . . . . ， . . . . . . . . . . . . . 2 7 图4 . 2单词切分流程图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 9 图4 . 3歧义处理示例 . . . . . . . . . . . . . . . . . . . . . ， . . . 3 2 图4 . 4钡 业 试结果示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 图4 . 5 c h a r t 分析示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 图4 . 6具有连看功能的c h a r t 分析示例 . . . . . . . . . . . . . . . 3 5 图4 . 7具有剪枝功能的c h a r t 分析示例 . . . . . . . . . . . . . . . 3 6 图4 . 8改进的c h a r t 算法的流程图 . . . . . . . . . . . . . . . . . . . 3 8 图4 . 9传统的c h a r t 算法分析结果示例 . . . . . . . . . . . . . . . 4 4 图4 . 1 0改进的c h a r t 算法分析结果示例 . . . . . . . . . . . ， 二4 5 图4 . 1 1改进前的句法分析结果示例 ， 二， . . . . . . . . 4 6 图4 . 1 2改进后的句法分析结果示例 ， . . ， . . . . . 4 6 图5 . 1语义理解流程图二， . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 图5 . 2语义网络示例 . . . . . . . . . . . . . . . . . . . . . . . . . ， . . 5 3 vi ii 表目录 表 目 录 表2 . 1 c h o m s k y 语法层次体系. . . . . . . . . . . . . . . . . . . . . . . . 1 4 表3 . 1活性边与非活性边示例 . . . . . . . . . . . . . . . . . . . . . . . 1 7 表 4 . 1词性标记集. . . . 。 ， . . . . . . ， . . . . . . . . 2 4 表 4 . 2短语标记集 . ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 表 4 . 3句型库示例. ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 5 表 4 . 4典型句型测试结果 . . . . . . . . . . . ， . ， . . . . . . . 4 7 i x 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定，同意如下 各项内容:按照学校要求提交学位论文的印刷本和电子版本;学校有权保存学 位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存 论文;学校有权提供目 录检索以 及提供本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电 子版;在 不以 赢利为目的的前提下，学校一可以适当复制论文的部分或全部内容用于学术 活动。 学 位 论 文 作 者 签 名 : i wd k, 川 年 t 月才日 经指导教师同意， 本学位论文属于保密， 在年解密后适用本授权书。 指导教师签名:学位论文作者签名: 解密时间: 年月日 各密级的最长保密年限及书写格式规定如下: 内部5 年 ( 最长 5 年，可少于 5 年) 秘密*1 0 年 ( 最长 1 0年，可少于 1 0年) 机密*2 0 年 ( 最长 2 0年，可少于 2 0年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导 师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学 位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内 容。对本论文所涉 及的研究工作做出贡献的其他个人和集体， 均己在文中以明确方式标明。本学 位论文原创性声明的法律责任 由本人承担 。 学 位 论 文 作 者 签 名 : 刻,# 砂1 年丁月牙日 第一章前言 第一章 前言 第一节 项目背景介绍 1 . 1 . 1普适计算简介 普适计算的思想最早是由 m a r k w e i s e r博士于 1 9 9 1年在 s c ie n t i f i c a m e r ic a n 的 “ t h e c o m p u t e r f o r t h e 2 1 s t c e n t u ry ，提出 的 。 普 适 计 算 h l也 称 作 无 处 不在计算( p e rv a s i v e c o m p u t i n g o r u b i q u i t o u s c o m p u t i n g ) ， 指无所不在的、 随时随 地可以进行计算的一种方式，普适计算设备嵌入到人们生活的环境中，为人们 提供计算和信息访问。普适计算描述了具有丰富计算资源和通信能力的人和环 境之间关系的 场景，这个环境与人们逐渐地融合在一起;它把计算机嵌入到各 种类型的设备中，建立一个将计算和通信融入人类生活空间的交互环境，从而 极 大 地 提 高 个 人 的 工 作 以 及 与 他 人 合 作的 效 率 自 。 普适计算将具有以下特点: 首先， 普适计算具有无处不在性。 在普适计算环境下计算将充斥在地下、 墙 壁、桌椅、日 用品、衣服等日常生活环境中，普适计算设备不仅通过有线网络， 还常借助于无线网络等来实现信息的访问和资源的共享，它一般具有高度可移 动性。 其次， 普适计算将改善人与计算机的关系。目 前人必须通过培训才能使用计 算机，并用计算机能够理解的方式，例如，使用鼠标或键盘和计算机交互，在 普适计算环境下人可以使用语音、手势等更自 然的方式和计算机交互，这样使 得人能够更专注于主要的工作。 再次，普适计算将具有上下文感知能力。它知道何时、何地、在和谁交互， 从而能更具个性化，甚至主动发现人的需要，为人提供服务。 最后， 普适计算服务具有不可见性。普适计算环境下不需要人工干预， 普适 计算设备具有自 我调整和自我配置的能力，信息空间将同人们学习工作生活的 物理空间融合在一起。 总之， 普适计算将改变 “ 人使用计算机” 的方式， 将人与计算机的关系改 变 为“ 计算机为人 服务” ， 让人与计算环境更好 地融合在一起， 是 2 1 世纪的 计算 模式。一言以 概之，“ 只有当机器进入人们生活环境，而不是强迫人们进入机器 第 1页 第一章前言 世界时， 机器的 使用才能像林中 漫步一样新鲜有趣3 j n. 1 . 1 . 2 普适环境下的语言理解技术 普适计算的真正目 的在于实现以人为本的计算，它使计算和通信能力无处 不在地融合在人们生活和工作的现实环境中。其中人机交互的友好性和便利性 是必需的，其对于系统的自 然语言理解和处理能力有了更高的要求，使得系统 能在不干扰人们注意力的同时，理解用户的需求，为用户主动地提供服务。 系统中通过手持设备进行服务器访问的工作流程为:用户通过手持设备以 语音或文本的方式提出自己的需求，服务器收到后将其转换成文字的形式，进 行语法分析，语义分析和提取，动作函数的定位和执行，最终实现用户的请求。 这一过程中， 对用户需求的理解和相关信息的分析具有非常重要的作用，只有 正确理解用户的意图，才能更好的为用户提供服务。系统的整个处理流程如图 1 . 1 所示: 图 1 . 1系统处理流程图 第二节 课题的提出 1 .2 . 1汉语语言的特点 汉语有很多不同于西方语言的语法特性，只有了解汉语本身的特点，才能 更好的实现语言理解技术。 下面列出一些显著的特性f4 1 , 第 2页 第一章前言 1 .汉语句子由汉字串组成，字与字之间无空格; 2 .一个词在不同的上下文中具有多个不同的语法功能; 3 .汉语没有屈折变化形式的标志; 4 . 构词规则可由很多不同的句法类型来实现; 5 .线性词序相对自由任意; 6 .词的 语义复杂，多音词广泛存在; 7 .汉语中的词基本上没有词型标志等。 这些特点对汉语的分析造成了一定的影响，使得汉语分析呈现出和英语以 及其他一些语言不同的特点。 1 . 2 .2普适办公环境下自然语言的特点 现在计算机智能还远远没有达到能够象人一样理解自 然语言的水平，而且 在可预见的将来也达不到这样的水平。因此，关于计算机对自 然语言的理解一 般是从实用的角 度进行评判的5 1 . 本文针对普适计算办公环境这一应用领域下语 言的特点， 对语言理解提出一定的要求，使得计算机能实现在此要求上的语言 信息处理功能。 普适计算办公环境下的语言有如下特点: 1 .词典库的特点 词汇是文本分析的基础，本系统的词汇分为专用词汇和普通词汇，主要收 集了办公环境下的常用词汇，特别是一些专用名词 “ 打印机” 、“ 投影仪”等进 行整理，形成专用词汇库。在此基础上，对日常生活中常见的词汇，参考 信 息处理用现代汉语分词词表进行尽可能全面的收集，使词典库能满足办公环 境下自 然语言处理的需要。 2 .词语分词的特点 汉语的 词 频 统计 6 1 表明 ， 在汉语中 ， 两 字词 大 约占7 5 % 左右。 该系 统 下的 语言 主要是规范的办公环境用语，对于一些 “ 呀”、“ 哦”等口 语化的语气词使用 较少，因而双字词的比例会更高一些。据此，词语的存储设计为基于二级索引 的词典结构，相应的分词算法采用增量的最大匹配算法，经测试切分结果基本 满足了系统的需要。 3 .短语的特点 该系统具有上下文敏感性，对于代词、介词短语、时间短语、方位短语等 第 3页 第一章前言 所表达的含义要进行转换处理、实现模糊指代功能。如 “ 打开我的计算机” ， 在 句法分析之后，系统要对词 “ 我”要进行定位和转换处理，最终将 “ 我” 变为 u s e r 0 0 1 ( 系统对用户的统一编号) ，之后去寻找计算机，执行操作。这里对 短语结构、句法结构的正确性分析提出了一定的要求。 随着社会的日 益信息化，人们越来越强烈地希望用自 然语言同计算机交流。 从计算机科学 特别是从人工智能的观点看，自 然语言理解就是研究如何能让计 算机理解人们日 常所使用的语言，目 的在于建立起一种人与机器之间的密切而 友好的关系， 使之能进行高度的信息传递与认知活动. 在普适计算环境下，这种 需求变得更加的强烈，只有计算机能真正理解人的话语、懂得人的需求，才可 能按照人们的期望，给出相应的信息或执行相关的动作，才能真正实现计算机 为人服务。 1 . 2 .3课题的实际意义 普适计算的目 标之一就是要使得人和计算机的交互更加自 然，让人能够更 专注于工作本身，因而使用自然语言理解的方式是普适计算的内在要求.可以 预见，在未来的普适计算中自 然语言理解将会有很重要的应用. 在基于普适计算环境建设方面， 国外一些研究机构非常关注自 然语言理解在 普适环 境中 的 应用。 麻省理 工学院a 1 l a b 的 “ o x y g e n ，计划(71 的 一 个普 适计 算 在会议的应用例子中，用户通过头戴式话筒给计算机发送语音命令， 例如: “ 计 算机，将今天的议程显示一下” ，计算机听到命令后用投影仪在墙壁上投影今天 的议程。这说明了国外研究机构在普适计算中己经开始重视自 然语言理解的作 用，并己取得了一定的进展。 从国内对普适计算的研究领域可以知道，国内还没有一个专门研究如何建 立一个基于自 然语言理解的普适计算环境的项目，因此这方面的研究具有一定 的新颖性。 可见，由于汉语本身的特点使得我们不能照搬国外的研究成果，而且在普 适计算办公环境下自 然语言又有其自身的特点，因此对语言理解技术进行专门 的研究和实现，就显得非常必要了。 第三节 本文内容组织与工作内容 本文的内容如下组织: 第 4页 第一章前言 第一章对普适计算环境以及该环境下的语言理解技术做了简单的介绍，并 给出了课题研究的实际意义。 第二章介绍了该系统中涉及的 技术理论和常用算法，从分词、词性标注和 句法分析三个部分分别阐述。 第三章是对系统总体结构设计的说明，包括系统的目 标、功能、实现的关 键技术及总体架构等几个方面。 第四章给出了本系统的设计与实现。 在分词和词性标注模块实现了 基于词典 的增字的最大匹配分词算法，在句法分析模块实现了改进的基于上下文的c h a r t 算法，并分别给出了试验结果和简单分析。 第五章对本文所做的工作进行了总结， 提出了今后的工作方向并对语义处理 部分做了进一步的展望。 目前，主要完成了以下几项工作: 1 .设计了一套普适计算办公环境下常用的汉语句型库作为研究基础; 2 .根据办公环境实际应用， 确定了 一套词性标记集和短语标记集; 3 .建立了 一套普适计算办公环境下使用的词典库; 4 .根据普适环境下常用的句型，设计了一套基于上下文无关的语法规则 库; s .实现了基于增量的最大匹配算法的分词和词性标注模块; 6 .实现了改进的基于上下文的c h a rt 算法的句法分析模块。 以上任何一方面均是系统实现必不可少的环节， 设计的优劣将关系到本系统 的实际性能。 第 5页 第二章系统的关键技术分析 第二章 系统的关键技术分析 第一节 单词切分相关技术 2 . 1 . 1简介 计算 机中文信息处理就是 要 “ 用计算机对汉语的 音、 形、 义进行处理”e 1 在 汉语中，“ 词是最小的 能够独 立活动的有意义的语言成 分” 1 。 然而， 汉语文 本 是连续的汉字串， 词与词之间 没有明确的分隔标记，因 此，自 动识别词边界， 将汉字串 切分为正确的 词串的 汉语分词无疑是实现中文 信息 处理的 各项任务的 首 要 问 题 d ol 2 . 1 . 2 分词系统的目标 普适计算办公环境下分词系统的 优劣主要从以 下几个方面来衡量，即 准确 性、 高效性、模块化及适用性。 1 .准确性 准确率是分词系统性能 的核心指标。 分词是自 然语言处理的首要步骤，经 统 计发现 f i l l ， 分词系统的准确 率应达到9 9 . 9 96 以上才能基 本满足 上层模块使用的 要求。 2 .高效性 分词是 自然语言处理的基础性工作，这步工作消耗的时间应尽量少，应只 占上层处理所需时间的一小部分，并应使用户没有等待的感觉。 3 .模块化 分词系统是句法分析、 语义分析等后 续工作的 基础， 其作 为语言理解系统 的一个环节，既要保证其独立的正确运行，又要为后续处理提供友好的接 口， 使得对其的修改不会对其他模块造成影响。 4 .适用性 汉 语自 动分词是手段而 不是目 的， 任何分词系统产生的结果 都是为某个具体 的应用服务的。本文设计的分词系统主要针对办公环境下的自 然语言进行切分， 使其能很好地满足办公环境下语言理解的需要。 第7页 第二章系统的关键技术分析 2 . 1 . 3 常用的分词方法 目 前常用的切分方法可以分为以下三类: 2 . 1 .3 . 1基于词典的机械分词方法 按照一定的策略将待分析的汉字串与一个机器词典中的词条进行匹配， 若 在词典中找到某个字符串， 则匹配成功( 识别出一个词) 。按照扫描方向的不同， 串匹配分词方法可以分为正向匹配、 逆向匹配和双向匹配( 正向和逆向的组合) : 按照不同长度优先匹配的 情况， 可以分为最大匹配、最小匹配、逐词匹配和最佳 匹配等。 最大匹配的基本思想:( 1 ) 取出待切分汉语句的m 个字符作为匹配字段，其 中 m 为机器可读词典中的最长词条的汉字个数;( 2 ) 查找机器可读词典并进行匹 配。若能匹配，则将这个匹配字段作为一个词切分出来;若不能匹配，则将这 个匹配字段的最后一个字去掉，剩余的字符串作为新的匹配字段， 进行再词匹 配.重复以上过程，直到切分出所有词为止。 最小匹配的基本思想是使待切分语句分词后得到的词最少。 逐词匹配法是把词典中的 词按由 长到短的顺序在待切分语句中进行搜索和 匹配，直到把所有的词都切分出来为止。最佳匹配的基本思想是词典中的词条 按照词频的大小来顺序排列，以求缩短分词词典的检索时间，从而降低分词的 时间复杂度。 基 于 词 典 的 分 词 方 法的 优点 是 简单、 易 于 实 现。 其 缺点 是 1 2 .13 1 : ( 1 ) 匹 配 速 度慢:( 2 ) 存在交集型和组合型歧义切分问题;( 3 ) 词本身没有一个标准的定义， 没有统一标准的词集;( 4 ) 不同词典产生的歧义也不同。 2 . 1 .3 .2 基于统计的分词方法 基于统计的分词方法所应用的主要统计量或统计模型有: 互信息、n元文法 模型、隐m a r k o v 模型和最大嫡模型等。 这些统计模型主要是利用词与词的联合 概率作为分词的信息。 1 .互信息 对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互信息。定 义两个字的互信息，计算两个汉字x , y 的相邻共现概率。对于字符串x 和y ，其 互信息的计算公式如下: 第 b页 第二章系统的关键技术分析 w ( x , y ) = l o g 2p ( x , y ) 其中 p ( x ,y ) 为 字符串 x 和y 共现的 概率， p ( x ) p ( y ) p ( x ) 和p ( y ) 分别为字符串x 和y 出现的 概 率。 互信息m i ( x ,y ) 反映了 字符串 对之间结合关系的 紧密程度。 ( 1 ) 互 信息 m i ( x ,y ) 0 ， 则x 与y 之间具有 可 信的 结 合关系 ， 并且 m i ( x ,y ) 越大 ， 结合程度越强; ( 2 ) m i ( x , y ) -o， 则 x 与 y 之间的结合关系不明确; ( 3 ) m i ( x ,y ) 刀 ， ( 。 ， 刀e ( v u t ) * ) , a x e 1 型 上下文有关文 法 线性有界自动机 a 。)6 , (a , ,6 。 ( v u t ) * ) , la l lq l 2 型 上下文无关文法 下推自动机 a - r /6 , q ( v u t ) * , a。 v 3 型 正规文法有穷自动机 a -+a , a -+a b , a 。 t u 琳a ,b e v 一个p s g 所接受的语言就是由开始符号s 通过p 中的规则所可以导出的所有 终结 符串的 集合. c h o m s k y 四 种形式语法所导出的语言 之间 的关系如图 2 . 1 所 示: 第1 4 页 第二章系统的关键技术分析 图2 . 1 c h o m s k y 形式语法 正规 文法的 语法形式最严格， 生成的语言最简单， 分析起来也最容易 ( 时 间复杂度 是线性的) ，可以 用有限 状态自 动机进行分析。由 于有限状态自 动机 的高效 性，也有 人使用它来进行 句法 分析，甚至有人用来 做机器翻译 3 1 1 上下文无关文法虽然不足以刻划自然语言的复杂性，但由于其形式简单， 分析效率高 ( 多项式时间复杂度)，是目前句法分析中使用最广泛的一种语言 形式。本 文实现的句法分析算法也都是 基于上下文无关语法的。 上下文有关文法分析的时间复杂度是非多项式的 ( n p问题)，而 0型文法 的分析甚至不是一个可判定 性问题 ( 实际 上是一个半可判定问 题)， 所以 这两 种语法形式在实际中都无法得到应用。 2 .3 .3句 法分析基本策略 句法分析的 基本策略3 2 1 有:自 顶向下 分析法、自 底向上 分析法、 左角分析 法等。 一 自顶向下分析法 自顶向下的方法又称为基于预测的方法，即先构造句法树的根节点，再逐 步向下扩展，直到叶节点。 一 自底向上分析法 自 底向上的方法也叫基于归约的方法，即先构造句法树的叶节点，再逐步 向上扩展，直到根节点。 一 左角分析法 第1 5页 第二章系统的关键技术分析 左角分析法是一种自 顶向下和自 底向上相结合的方法， 所谓 “ 左角( l e f t c o m e r ) ” 是指任 何一个句法子树中 左下角的那 个符号。 2 . 3 . 4 句法分析算法 句法分析的过程就是将小的语法成分组合成大的语法成分的过程。虽然各 种语法的形式相差 很大， 不过在句 法分析的过程中采用的分析 算法都 是类似的. 常见的上下文无关语法的句法分析算法包括: 1 . l r算法; 2 . 左角分析算法; 3 . c y k算法: 4 . m a r c u s 确定性分析算 法; 5 . e a r l e y 算法; 6 . t o m i ta 算法 ( g l r算法 ) ; 7 . c h a rt 算法等。 国内很多有代表性的汉语句法分析 模块都是通过改进已 有的 经典句法分析 算法设计的，不少己在实践中 取得了 很好的 效果 3 3 1 。目 前应用得 最为广泛的 句 法分析算法是 l r算法和 c h a rt算法。由于论文主要采用了c h a rt算法的改进， 下面主要介绍 c h a rt的相关概念. 2 .3 .4 . 1 线图 线图 ( c h a rt )是美国计算语言学家 卡普兰在树形图的 基础上修改而来的。 它是一组节点 ( n o d e ) 和边( e d g e ) 的 集合. 即把词与词之间的间隔 作为结点，把词 和短语当作连接结点的边。在句法树中，父节点支配子节点，同级节点之间存 在顺序关系。 2 . 3 . 4 . 2 点规则 规则的右部的符号串中， 可以加圆点， 叫做“ 点规则” 。 例如， 如果s -n p v p 是语法中的一个规则，那么在线图中，下面几个加了圆点的点规则都可以作边 上的标记: s-. np vp s-np . vp s- np vp. 第 1 6页 第二章 系统的关键技术分析 在这些点规则中，圆点用来表示在分析过程的某一时刻，什么是规则中检 验过的， 什么是规则中尚未检验过而有待进一步检验的， 可见，引入 “ 点规则” 用于表示规则右部被匹配的程度。 2 . 3 . 4 . 3 活性边与非活性边 在规则使用的过 程中， 为了 消除冗余的操作，将边分为两种，一种叫做活 性边，即规则右部未被完全匹配的边。另一种叫做非活性边，用于记录一条规 则右部已经被完全匹配的情形。于是，规则 s -n p v p在使用的过程中，可以产 生如表3 . 1 所示的两条活性边和一条非活性边: 表3 . 1活性边与非活性边示例 记录方式边状态匹配程度起点终点 活性 s- - . nipvp00 活性 snp. vp01 非活性s np v p.03 2 . 3 . 4 . 4 代理 表 在c h a rt 算法中，还有一个重要的数据结构，称为 “ 代理表”或 “ 待处理表” ( a g e n d a )。记录待处理的 成分，也 称k e y . c h a rt 分析的过程就是一个不断产生新的边的过程。但是每一条新产生的边 并不能立即加入到c h a r t 中， 而是要 放到代理表中。 代理表实际上是一个边的 集合， 用于存放已 经产生， 但是 还没有加入到c h a rt 中的边。 代理表中边的排序和存取方式， 是c h a rt算法执行策略的一个重要方面。 2 . 3 . 5 小结 本节主要介绍了句法分析的任务、常用句法理论、句法分析的基本策略以 及常用的句法分析算法。 句法分析一般都依赖于某种语法理论，该系统实现的句法分析算法基于短 语结构语法中的上下文无关文法，采用 自 底向上的基本策略，针对传统的 c h a rt 算法产生冗余较多而导致分析效率低的 情况，提出基于 上下文的改进思想，为 其添加了 连看和剪枝功能。 改进的句法分 析方法降低了 冗余边的产生概率，使 得分析效率和准确率得到进一步提高。 第 1 7页 第三章系统的总体结构设计 第三章 系统的总体结构设计 自 然语言理解是实 现普适计算办公系统的第一步，是无处不在计算中信息 处理和控制的基础。本文主要研究办公环境下的语言理解技术，实现自然语言 处理的平台，为后续的工作提供基于用户需求的、友好的句法和语义接口。具 体分为语法分析和语义分析两个部分.本论文主要着眼于语法分析的研究，目 的在于开发一个适用于本环境的语法分析系统，其实现分为词法分析和句法分 析两个模块。 第一节 系统目 标 该系统的目 标主要是对语句进行单词切分、词性标注并给出其合理的句法 结构。现阶段处理的文本单位是单句，系统以下面几个原则为目 标: 1 .具有合理性，为后续的语义分析提供合理的句法树结构; 2 .具有实用性，为今后该环境下自 然语言的进一步研究提供基础; 3 .具有通用性，可以 方便的同其他模块相结合，不仅仅是语言处理模块， 还可以为普适计算环境下更多相关问题的解决提供语法方面的支持。 第二节 系统的功能 本文实现的是基于规则的语法分析系统，主要由知识库和控制程序两大部 分组成，知识库包括含有一千多个词条的词典库和用于句法分析的规则库，以 及句型库、语料库、词性和短语标记集等。控制程序是由词法分析控制程序和 句法分析控制程序组成的软件包。 通过本系统的工作，主要实现以下几个功能: 1 .给每个输入的句子s 进行分词: 2 .给分好的词进行词性标注; 3 .对一系列标注好词性的词，用改进的c h a rt算法进行句法分析。 第 1 9页 第三章系统的总体结构设计 第三节 系统的关键技术 系统采用的后台数据库是o r a c l e 9 i 数据库，使用通用可移植语言c / c + + 作 为开发工具，极大地提高了工作效率，实现了普适环境下的平台无关性。经过 进一步地运行、测试、完善，最终提供给用户可以方便使用的语法接口。 本文主要采用以下几种关键技术来实现: 词法分析阶段:采用基于词典的分词算法，并根据 “ 在汉语中两字词大约 占7 5 % 左右”的统计规律， 采用增字的最大匹配算法实现分词。匹配词条的同时 为句子中的词条标注词性， 对于兼类词的词性， 按照办公环境下的出现频率进 行优先级排序，优先处理级别较高的词性，然后依据上下文信息，结合规则库 中的规则进行词性消歧。 句法分析阶段:依据上下文无关文法，采用自 底向 上的基本策略，针对传 统的c h a r t 算法产生冗余较多而导致分析效率低的情况， 基于上下文的改进思想， 添加连看和剪枝功能，提高算法的分析效率和准确率。存储机制采用的是句法 结构树的形式。 第四节 系统的总体设计 3 .4 . 1系统设计的原则 系统的几个重要设计原则: 1 .立足于实际需要 本文的目的是构造一个普适办公环境下实用的汉语理解系统，因而在可供 选择的若千技术路线面前，将根据系统的特点，尽量选用比较适合该环境的技 术，完成系统的设计和实现。 2 .开放的体系结构 开放的体系结构主要体现在系统的实现上所采用的软件构件技术。整个系 统由一些相对独立的软件构件组成，因而可以方便地对系统进行修改、维护和 扩充。分析的过程严格按照独立分析、独立生成的原则进行组织，每一阶段的 算法相互独立，对其中一个阶段算法的修改不会对其他算法造成影响。 3 .采用一致的数据结构，有利于各个阶段之间的衔接. 第 2 0页 第三章系统的总体结构设计 3 .4 .2 系统的组成模块 该系统由两个模块组成，它们是分词和词性标注模块以及句法分析模块。 1 .分词和词性标注模块是通过最大词长匹配算法和建立的词典库实现的。 当输入一个句子的时候，该算法在词典数据库中进行相应的搜索，从而将句子 分解为一个个独立的词，同时为相应的词标注词性。这里采用分词和词性标注 合一的方法。 2 .句法分析模块是实现对一个单句建立一个句法树的过程。将己经分词、 标注词性的句子， 通过改进的c h a r t 算法， 运用从汉语的句法结构特点出发总结 的一套语法规则，实现适用于本环境的基于规则的汉语句法分析模块。 3 .4 . 3 系统的总体设计 本文主要实现了 基于词法分析和句法分析的自 然语言理解系统，其总体设 计如图3 . 1 所示: 图3 . 1语言理解系统总体设计图 在该系统中，首先从键盘或文本文件中输入汉语句子，然后通过词法分析 模块，分析该句中的每个词并为其进行词性标注:在句法分析模块中根据 c h o m s k y范 式形式 的 语法规则分 析句 子， 用句 法 树描 述出 该 句子的 句 法结 构。 在此系统中所用到的词典库和规则库，分别在后台建立词典管理系统和规则管 理系统加以管理。 第 2 1页 第三章系统的总体结构设计 第五节 小结 本章给出了该系统的设计目标和总体结构，介绍了实现该系统的开发环境 和算法。系统具有良 好的模块独立性，可以分别对分词和词性标注、句法分析 进行实验。 上面是对该系统的总体介绍，下一章将分各个模块具体介绍整个系统的实 现。 第 2 2页 第四章系统的实现与结果分析 第四章 系统的实现与结果分析 第一节 知识库 一 个比 较完善的 句子或短语的自 动分析，总离不开两样东西: 一部词典， 词典中的每一个词项都必须带上词类标记;一部语法，语法中每一条规则都由 一组词 类或形式类符号按照一定顺序的 排列来表示【 3 4 1 。 然而 在实 现的 过程中， 对其科学性、合理性的设计和统一、规范化的表示是必须的，因此根据系统实 际需要， 本文建立了 词性标记集和短语标记集，并且根据常用句型总结了 典型 句型，成为分词词典和语法规则的分析基础。 4 . 1 . 1词性标记集与短语标记集 为了 进行语 法研究与信息处理， 需要把 语法功能( 或者说语法 性质) 相同的 或 者相近的 词归成一类3 5 1 .这里包含两项工 作。 一项是要针对汉语词语的 全集， 按照某 种标准， 建立一个分 类体系。在朱德熙先生的语法理论的 指导下， 北大 计算语言学研究所与中文系合作，经过几年的研究，提出了一个适用于语言信 息处理 的 现代 汉 语词 语分 类 体系 3 61 。 多 项 语 言 工 程的 实 践 检验 了 这个 词 语分 类 体系的 科学 性与可操作性。 这个词语分类体系在中文信息处理 学界己 产生较大 的影响。另一项工作是决定该全集中的每一个词语究竟属于哪一个词类。根据 这些思想，并 结合实际 情况，本文确定了 一套适用于普适计算办公 环境的词 性 标记集和短语标记集。 第 2 3页 第四章系统的实现与结果分析 表 4 . 1词性标记集表 4 . 2短语标记集 词性标识 词性 描述 1 v 动词 2n 名词 3a 形容词 4f 方位词 5t时间词 6 9量词 7田 数词 8 an y 数量词 9d 副词 1 0 p介词 1 1c连词 1 2 y语气词 1 3e 叹词 1 4u 助词 1 5r 代词 1 6 s处所词 短语标识短语名描述 1 np 名词性短语 2v p 动词性短语 3a p形容词性短语 4d p副词性短语 5 p p 介词性短语 6s p 处所词性短语 77 p 时间词性短语 8mp数量词短语 9m c p数词短语 1 0d j“ 的”字结构 1 1s 单句 由于时间短语、处所短语在项目研究中有特殊的意义，为了后面语义分析 的方便， 把它们从副词短语中 分出， 单独进行分析。 4 . 1 . 2 句型库 句型库是一个基础数据库。本文根据常用句型总结出了典型句型，并为句 法分析过程中使用的产生式规则的分析奠定了基础。 第 2 4 页 第四章系统的实现与结果分析 表4 .3句型库示例 汉语类型示例 短语语法结构示例 完全句 ( 主谓不缺) 主谓 ( 动词短语当谓语)电脑打开了np vp 主谓 ( 形容词短语当谓语)会议室热得很np ap 主谓 名词短语当谓语)今天星期天tp np 主谓宾我打开门np vp np 主谓补天黑下来np ap vp 主谓定宾小鸟吃黄色的果子np vp ap np 主谓定补宾小张送我一本词典n p v p np mp np 主状谓老张明天出发np t p vp 主状谓老张骑自 行车出发np vp np vp 主状谓补他只答应了一声np dp vp mp 主状谓宾逃犯企图偷越边境np dp vp np 主状谓定宾中国坚决执行改革开放的政策np dp vp ap np 主状状谓 人们在田 野里辛勤地劳动 np p p dp vp 主状状谓宾他今天在单位里整理资料np作 即 v p np 状主状谓宾今天他在单位里整理资料t p np p p v p np 状状主谓宾今天在单位里他整理资料t p p p np v p np 状定主谓那座老房子塌了dp np np vp 省略句 ( 主谓不全) 主张三np 定主美丽的花儿ap np 补主一个人dp np 主补我李明np np 谓工作v p 谓补跑得飞快vpap 谓宾刮风了vpnp 状谓在学校工作p p v p 状谓补渐渐慢下来dp a vp vp 第 2 5页 第四章 系统的实现与结果分析 续表 4 .3 汉语类型示例短语语法结构示例 状谓补宾屋顶上飘着一面红旗 p p vp mp np 状状谓今天已经开会了 tp dp vp 宾计算机 np 状在学校里 p p 第二节 单词切分和词性标注 4 . 2 . 】分词词典 词典作为知识库的一部分，担任着重要的角色，词典查询主要考虑分词词 典的数据结构与查询算法的时空消耗问题。本系统的词典主要存放了每个词条 的词性信息和语义信息，每个兼类词的词性根据在该办公环境下的使用频率自 高向低排列。词典中词条收录的合理与否非常重要。 目 前词典中主要收录了办公环境下的常用词汇以及一些简单的日 常用语， 经统计词库总数约为1 2 0 0 余条，尚在进一步完善中。 4 .2 .2分词词典的设计 基于词典的分词方法， 分词词典建立的好坏直接影响单词的查询速度和匹 配算法 效率， 因 而必须 考虑