（计算机应用技术专业论文）基于中文的主观试题自动批改技术的研究.pdf

论文题目：基于中文的主观试题自动批改技术的研究 专业：计算机应用技术 硕士生：陈伟( 签名) i 垂j 生 指导教师：张小艳 ( 签名) 强= l ! 建。 摘要 主观试题自动批改技术作为自然语言理解中重要课题之一，对于学生自测作业、大 规模在线考试方面具有非常重要的意义。目前针对客观题的自动批改技术己经相当成 熟，但是，对于论述、简答、写作等没有统一答案的主观试题，涉及到人工智能、模式 识别和自然语言理解诸多方面，又由于汉语的特点，在实现上有其自身的困难，相对来 说比较复杂，一直制约中文主观试题自动批改技术的发展。因此，研究如何实现中文主 观题的自动批改具有很重要的现实意义。 本文根据汉语理解的特点，模拟教师人工批改的过程，通过对自动批改中涉及到的 中文知识表示、分词方法、句法分析、语义相似度等方面的研究，利用统计与规则相结 合分词方法、改进线图分析算法、非线性函数和“成对比较法”相结合的关键词权值计 算方法和加权语义相似度计算方法分析和实现主观试题的自动批改。在语义相似度计算 方面，利用知网提供的语义信息，从义原到概念、从概念到词语的相似度计算方法，根 据词语相似度的计算结果，利用词语加权语义相似度计算句子的相似度，最后将相似度 的值转化为最终的分数。 根据以上自动批改的思想，设计出一个主观题自动批改试验系统，对小样本数据进 行测试，验证本文分析算法可行有效，达到一定批改效果。 关键词：自动批改技术；汉语句法分析；权值；语义相似度 研究类型：应用研究 s u b j e c t ：r e s e a r c ho na u t o m a t e da s s e s s m e n tt e c h n o l o g yo fs u b j e c t i v e s p e c i a l t y ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y n a m e：c h e nw e i ( s i g n a t u r e ) i n s t r u c t o r ：z h a n gx i a o y a n c m e a s s e s s m e n tt l m o l o g yo f s u b j e c t i v et e s t sb a s e do nc h i n e s ei so n eo f t h ec o 他p r o b l e m s i nn a t u r a ll a n g u a g eu n d e r s t a n d i n g m a s s i v eo n l i n ee x a m i l 埘o l l sh a sv e r yi m p o r t a n t s i g n i f i c a n c e , t h eo b j e c t i v ev i e wt h a tt h ea u t o m a t i cm a r k i n gt e c h n o l o g yh a sb e e nv e r ym a t u r e b u t , w h e nr e f e r st ot h es u b j e c tq u e s t i o 璐，s u c ha ss h o r ta l l s w e rq u e s t i o n s 、e s s a yq u e s t i o n s a n dw r i t i n ge t c ，i sn os i n g l ea i s w e rt ot h eq u e s t i o n s ，b e c a u s et h e s u b j e c tq u e s t i o n s a t r o - a s s c s 8t e c h n i q m sa r er e s t r i c t e db yt h ed e v e l o p m e n to ft h et e c h n i q u e si na r t i f i c i a l i n t e l l i g e n c ea r e a , t h en a t u r a ll a n g u a g eu n d e r s t a n d i n ga r e aa n d t h ep a t t e r nr e c o g n i t i o na r e a , a n ds o0 1 1i t so w ni n v o l v i n gc h i n e s el a n g u a g ef e a t u r 鼯，t h er e a l i z a t i o nh a si t so w nd i f f i c u l t i e s a n dc h a r a c t e r i s t i c so fr e l a t i v e l ya c h i e v ei sr e l a t i v e l yc o m p l e x , t h i s , t oac e r t a i ne x t e n t , c o n s t r a i n sa u t o m a t e da s s e s s m e n tt e c h n o l o g yo fs u b j e c t i v et e s t sb a s e do nc h i n e s e t h e r e f o r e , t h es t u d yo fh o wt h ea u t o m a t e da s s e s s m e n tt e c h n o l o g yo fs u b j e t , r et e s t sb a s e do nc l l i n e t h a th a sg r e a tp r a c t i c a ls i g n i f i c a n c e b a s e d0 1 1t h eu n d e r s t a n d i n go ft h ec h a r a c t e r i s t i c so fc h i n e s e 1 h i sp a p e rs i m u l a t e si n m a n u a lp r o c e s s ，c o m p u t e ra u t o m a t e c la s s e s s m e n tt e c h n o l o g ys h o u l dt a k eo nc h i n e s e a u t o m a t i cw o r ds e g m e n t a t i o n , k n o w l e d g ed e n o t a t i o n , s y n t a xa n a l y s i s ，s e m a n t i cs i m i l a r i t y , t o r e a l i z et h a ts u b j e c t i v eq u 妇a u t o - a s s e s s a n a l y s i so f t h ep r o c e s so f u s i n gr o l e - b a s e da n d c o r p u sb a s e ds t a t i s t i c a lm e t h o d s ，i m p r o v e m e n t so nc h i n e s es y n t a xp a r s i n gh a v eg i v e nb y a d o p t i n gm e t h o d so fb o t hb o t t o ml | pa n dt o pd o w n , t h en o n - l i n e a rf u n c t i o na n dt h e d o u b l e c o m p a f i n gm e t h o d t oc a l c u l a t et h et e r mw e i g l m n g 。i nt e r m s o fs e m a n t i cs m g a r i t y , 谢t ht h e a b u n d a n ts e m a n t i ci n f o r m a t i o ns u p p l i e db yh o w n e t , i tc a l c u l a t e st h es e n t e n c es i m i l a r i t yw i t h w e i g h t e ds e m a n t i cs i m i l , i t yb a s e do nc h i n e s ew o r d ss e m a n t i cs i m i l a r i t y , f r o mp r i m a r yt o t h eo r i g i n a lc o n c e p t sa n dt e r m sf r o mc o n c e p tt ot h es i m i l a r i t yc a l c u l a t i o nm e t h o d t h e nw e c a ng e tt h ef i n a ls c o r e sd e p e n do nt h ev a l u eo f s i m i l a r i t y a c c o r d i n gt ot h ea b o v ei d e a , n 把p a p e rd e s i g n sas u b j e c t i v eq u e s t i o na u t o - a s s e s s s y s t e ma n da p p l i e si t i n t os m a l l s c a l ec h i n e s et e x t , f r o mt h et e s tr e s u l t s , i tp r o v e st h a tt h e a l g o r i t h mm e n t i o n e da b o v ei se f f i c i e n c ya n df e a s i b i l i t y t h ea u t o - a s s e s sr e s u l tw a sp r e t t y g o o d k e y w o r d s ：a u t o m a t e d a s s e s s m e n tt o c h n o l o g y c f l i n 雠s y n t a c t i ca n a l y s i s 西要料技支学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 傲的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：7 氧1 予日期：哆6 ，? 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名： 倚伟 指导教师签名：弓b l 、艳 却p 7 年，月于e t i 绪论 l 绪论 1 1 研究背景 随着计算机辅助教学、多媒体处理以及计算机网络等技术的飞速发展和推广，网络 教学成为极具应用前景的远程教育模式，将从根本上改变人们的学习方式。为了提高在 线网络教学质量，各种相关技术得到了重视和研究，其中自动批改技术作为自然语言理 解技术难点之一，被广泛关注。 自动批改技术对于学生自测作业和大规模在线考试具有非常重要的意义，它不仅可 以节省大量手工批改工作，并且能立即反馈或直接得到考试的结果。尤其是在自动化组 卷方面可以利用自动批改结果及时了解学生考试情况，动态调整试题难度和知识点的考 核，是计算机自适应考试的基础，也是考试结果点评和个性化分析的基础。对不同的试 题类型，试卷自动化批改的难易程度相差很大，客观题的自动批改易于实现，主观题的 自动批改实现起来则相对复杂，在一定程度上使得在线考试不能真正实用化，从而成为 制约网络教学发展的一个重要因素。 目前，针对判断题、选择题等客观题的自动批改技术已经相当成熟，被广泛应用到 计算机能力考试、英语考试等大规模的考试中。而诸如填空题、简答题等主观题自动批 改，由于涉及到人工智能、模式识别和自然语言理解诸多方面的理论l l 】，至今没有出现 通用的自动批改的方法，对主观题的批改还是以人工批改为主。 人工批改方式给出的分数受很多客观因素的影响，比如批改者当时的心情、学生卷 面的整洁程度等。在学生答案彼此相同的情况下，假如批改者当时心情愉快或者学生卷 面比较整洁或字体很漂亮的情况，受主观因素的影响，学生成绩会高一些；反之，当时 批改者心情低落或学生卷面很乱、字迹潦草的情况，则分数会低一些。批阅大量试卷时， 人会容易疲劳，也就容易产生误判等情况。这样就降低了学生之间竞争的公平性和公正 性，受各种主客观因素的影响，使得学生的分数差异较大。 利用计算机进行自动批改时，批改的标准会始终保持一致，不会像人一样会因为各 种主客观因素的影响而使评判标准发生偏移。计算机的批改速度快、效率高、准确性高、 不会疲劳，适合于大规模、大批量试题的自动批改。因此，研究如何利用计算机来实现 对基于中文的主观试题的自动批改具有很重要的现实意义。 1 2 研究现状 f 1 2 0 世纪6 0 年代以来，国外许多专家和学者就致力于主观题的计算机自动批改技术 的研究，开发, m p r o j c c te s s a yc n a d e ( p e g ) ，l a t e n ts e m a n t i ca n a l y s i s ( l s a ) ，e d u c a t i o n a l l 西安科技大学硕士学位论文 t e s t i n gs e r v i c ei ，e r a t e r ，a u t o m a t e dt c 。( tm a r k c r ( a t m ) 和a u t o m a r k 等系统，有的已经 进入实用阶段，并取得了较好的效果。 国外对于主观题的自动批改技术的研究可以分为任意文本答案的主观题的自动批 改和简短文字的自动批改两类。前者是文章写作类试题的批改，通常采用的是抽取出答 案中的浅层结构信息或者语义信息，根据学生的遣词造句情况给以得分或者设置若干答 案模板，包括可接受模板和不可接受的模板，将学生的答案与这些模板进行匹配，根据 匹配程度，计算出得分；后者是简述题、名词解释题的批改，一般是先将参考答案进行 适当的表示，然后对学生答案与参考答案进行比较，通过计算匹配程度给出学生的得分。 相比之下，国内对主观题自动批改技术的研究起步较晚，成熟的理论技术也不多。 由于汉语不同于英语等欧式语言，没有形态和时态的变化，词与词之间也没有天然的分 隔标记。因此，对汉语的自然语言理解和处理面临着很多的难题，比如句法分析、语义 相似度计算等问题。因而，国内针对简述题、写作题等需要高度自然语言理解能力的主 观题自动批改的研究未有文献记载。 已有的研究都是对于简单类主观题如填空题、简答题等的自动批改，这些研究主要 有：张量和王邯等研究了针对计算机基础上机操作考试文字录入题和计算机水平考试程 序填空题自动批改技术，采用学生答案与标准答案字符串匹配或语义匹配方法，实现了 对c 语言程序设计填空题的自动批改；湘潭大学信息工程学院九九级研究生李辉阳通过 研究有限领域中简述文字的自动判读，提出了基于关系的带权匹配技术实现对c a i 中简 单论述题的判定；王永生1 2 1 研究基于模糊综合评判技术的主观题的批阅形式，分析其与 解答关键因素的贴近度，按照各解答关键因素在整个试题得分中所占的比例( 权重) ，通 过对应试者解答中该子因素的模糊综合评判，评定其小分；最后累加各解答关键因素的 得分，作为试题解答的最终成绩。在单层模糊综合评判过程中，单因素评价向量由统计 调查确定，所以要考虑调查人数足够多而且要有代表性。权值的确定是由各权威专家按 因素的重要程度来商定，因此也存在着差异；高思丹、袁春风提出了基于动态规划的语 句相似度计算方法实现文字类主观题的自动批改技术，采用动态规划算法主要考虑是语 义上的相似度，而不考虑语法结构关系。利用短语级匹配和整句级匹配，通过动态规划 算法对短语相似度矩阵进行计算，得到语句相似度。这种方法对于标准答案是单句的情 况准确度显得很高，但是如果考虑到复句，以及语句次序和句式结构结果就显得差异很 大：肖雪莲【3 l 在研究h n c ( 概念层次网络) 的基础上提出针对筒述题自动批改技术，从语 句块识别，分词算法，句法分析等基础上根据相似度计算讨论简述题批改问题。 国内主观题自动批改实验系统都是针对某特定领域的某特定类型提出的，为主观题 自动批改实现提供了定的解决途径，达到了一定的批改效果，但是这些系统仍存在一 些问题和不足： 研究基于中文主观题的自动批改时，通常是从语法、语义、语句模式某一方面 2 l 绪论 单独考虑语句相似度的计算，针对中文复杂的情况，没有考虑将上述方面结合 起来考虑句法分析或者语句相似度的计算； 问答题或者填空题进行批改时采用字符串匹配，没有考虑词在句子中的位置和 作用，以及词在句子中的语义和顺序； 通用分词算法，要么是基于规则的分词，要么是基于统计的分词，这两种分词 方法都有它优缺点，没有将两者结合起来考虑； 关键词的权重一般方法都是“位置加权法”、“词频统计法”或二者的结合或 引申上述方法都是采用的加权体系建立在线性基础上，很大程度上不符合语 言的实际情况。一 1 3 本论文主要研究工作 针对国内外主观题自动批改系统的研究现状，本文从知识表示、语法分析和语义分 析、语义相似度的计算方面讨论中文类主观题的自动批改问题。对于标准答案和学生答 案，采用知网中词语的表示方式。计算学生答案和标准答案中词语的相似度，进一步去 研究句子的相似度，根据词语的权值确定答案中的关键词语，给出不同权值的词或者句 子的得分点。利用分数转换功能，将相似度的计算结果转化为学生最后的分数。 本文将研究工作的重点放在以下几个方面： ( 1 ) 对知网理论的学习，知网中词语表示方式和相似度计算方法。 ( 2 ) 主观题自动批改算法思想的研究和自动批改流程的设计 ( 3 ) 主观题自动批改分词算法和句法分析的设计。 ( 4 ) 关键词权值的计算方法采用非线性函数和“成对比较法”相结合的方法。 ( 5 ) 对语句相似度的计算方法进行深入的分析和研究，设计适合判定学生答案与标 准答案接近程度的计算方法，去研究中文类主观题的自动批改。 1 4 论文框架 本论文共分5 章： 第一章绪论本章主要介绍本论文的研究背景、研究现状、研究工作和论文框架。 第二章主观试题自动批改相关理论本章主要介绍主观题自动批改过程中相关理 论，从知识表示、语法和语义分析、语义相似度计算等方面详加讨论。 第三章主观题自动批改的思想和流程本章阐述了手动批改和自动批改的思想， 比较之后模拟人工批改过程，提出了计算机自动批改的算法流程。 第四章主观试题自动批改算法设计本章重点是对主观试题批改过程中的分词算 法、句法分析算法、权值设定算法和语句相似度计算算法详细设计。 第五章主观题自动批改系统实现与分析本章主要是系统设计与实现，以及实现 3 西安科技大学硕士学位论文 系统过程中的数据分析。 第六章结论对本文的进行总结和展望 4 2 主观题自动批改相关理论 2 1 知识表示 2 主观题自动批改相关理论 知识表示是对知识的一种描述约定，一种计算机可以接受的用于描述知识的数据结 构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。 知网是一个以汉语和英语所代表的概念为描述对象，揭示概念与概念之间以及概念 所具有的属性之间的关系为基本内容的常识知识库。它是一个网状的知识系统，作为面 向汉语计算需求的知识库，提供了设计智能软件所需的知识，为自然语言处理提供了一 个新的研究资源。 2 1 1 知网的系统概述 知网作为一个知识系统，着力反映的是概念的共性和个性( 能够准确的放映概念的 共性和个性) 。在知网中概念是对词语语义的一种描述，每一个词语有不同的语义，那 么每一个词可以表达为几个概念。概念是用一种知识表示语言来描述的，这种知识表示 语言所用的“词汇”叫做“义原”。例如，对于“医生”和“患者”，“人”是它们的 共性。知网在主要特性文件中描述了“人”所具有的共性，那么“医生”的个性是他是 “医治”的施事，而。患者”的个性是他是“患病”的经验者。对于“富翁”和“穷 人”，“美女”和“丑八怪”而言，。人”是它们的共性。而它们的个性，即：“贫”， “富”与“美”、“丑”等不同的属性值。 知网还着力要反映概念和概念之间以及概念的属性和属性之间的各种关系。知网描 述了下列各种关系： 上下位关系( 由概念的主要特征体现) 同义关系 反义关系 对义关系 部件整体关系( 整体前标注体现，如“心”，“c p u ”等) 属性宿主关系( 宿主前标注& 体现，如“颜色”，。速度”等) 材料成品关系( 成品前标注? 体现，如“布”，“面粉”等) 施事经验者，关系主体- 事件关系( 事件前标注体现，如“医生”，“雇主”等) 受事内容领属物等事件关系( 事件前标注$ 体现，如“患者”，“雇员”等) 工具事件关系( 事件前标注体现，如“手表”，。计算机”等) 场所事件关系( 事件前标注 体现，如“银行”，。医院”等) 5 西安科技大学硕士学位论文 时间- 事件关系( 事件前标注 体现，如“假日”，“孕期”等) 值属性关系( 直接标注无须借助标识符，如“蓝”，“慢”等) 实体值关系( 直接标注无须借助标识符，如“矮子”，“傻瓜”等) 事件角色关系( 由加角色名体现，如“购物”，“盗墓”等) 相关关系( 相关概念前标注撑体现，如“谷物”，“煤田”等) 知网系统的哲学贯穿于整个知识系统的各个方面，是系统的重要组成部分。首先体 现在它对概念的主要属性的确定上，概念的主要属性也是概念分类的类别【4 】。知网系统 的最高层有n 范畴、v 范畴、a 范畴三类。n 范畴包含实体，属性和单位。实体的直接 下位有万物、时间、空间，部分。万物包括物质、精神和事情三类，它们通常是运动和 变化的主体，运动和变化总是发生在一定的时空之中，运动和变化体现于属性，并由属 性值显示。 2 1 2 知网的系统词典 知网系统主要包括知网管理系统和中英双语知识词典。知网的主要文件是知网词 典，可以由知网管理系统导出反义词表、实体表、属性值表、角色事件表等构成了一个 有机结合的知识系统。 知识词典是知网系统的基础文件，知识词典中每一个词语的概念称义项，都描述形 成一个记录【5 】。每一个记录有8 项内容，每一项两部分组成，中问以“= ”分隔。每一个 。= ”的左侧是数据的域名，右侧是数据的值。它们捧列如下： n o = 编号 wc = 汉语词语 gc 窖汉语词语词性 ec - 汉语词语例子 we 英语词语 ge = 英语词语词性 e e _ 英语词语例子 d e f _ 概念的定义 每个词语由d e f 来描述其概念的定义，d e f 项称之为一个语义表达式，d e f 的值 由若干个义原以及它们与主干词之间的语义关系描述组成f 6 】。义原是知网中最基本的不 易于再分割的意义的最小单位。例如，。入”虽然是一个非常复杂的概念，它可以是多 种属性的集合体，但我们也可以把它看作为一个义原。d e f 部分表示概念与义原的关系， 因此可以认为词是由义原通过某种关系构成的。所有这些，都通过知网提供的知识词典 描述语言( k d m l ) 来实现。 6 2 主观题自动批改相关理论 表2 1 知同知识描述语言中的符号及其含义 多个属性之问，表示“和”的关系 群 表示“与其相关” 表示“是其部分” $表示可以被该。v ”处置，或是该“v ”的受事，对象，领有物，或者内容 表示会。v ”或主要用于。v ”，即施事或工具 +对v 类，它表示它所标记的角色是一种隐性的，几乎在实际语言中不会出现 & 表示指向 一 表示多半是，多半有，很可能的 国表示可以傲。v ”的空间或时间 ?表示可以是。n ”的材料。如对于布匹，我们标以。7 衣服”表示布匹可以是。衣服” 的材料 ( 1 ) 对于v 类，置于 中的是该类v 所有的。必备角色”如对于。购买”类一旦 它发生了，必然会在实际上有如下角色参与：施事，占有物，来源，工具尽管在 多数情况下，一个句子并不把全部的角色都交代出来 ( 2 ) 表示动态角色，如介词的定义 0 置于其中的应该是一个词袁记，例如，( c h i n a i 中国) 一 表示不存在，或没有，或不能 i 表示某一属性为一种敏感的属性，例如，“味道”对于“食物”，。高度”对于“山 脉”，。温度”对于“天象”等 n标识概念的共性属性 d e f 的形式化语言的定义为： d e f = m a r k p d m i f i v e , m a r k p r i m i f i v e m a d c = - + i i ? l ! l l 群i $ i i “l & p r i m i t i v q a r i m i t i v e i i p r i m i f i v e 2 1 i p r i m i t i v e t 。 m a r k 中符号( k d m l 语言的关系标识符号) 的含义如上表2 1 所示。 知网知识描述语言归纳如下； ( 1 ) 知网收录的词语主要归为两类，一类是实词，一类是虚词。 ( 2 ) 虚词的描述比较简单，用“ 句法义原 ”或“ 关系义原 ”进行描述。 ( 3 ) 实词的描述比较复杂，由一系列用逗号隔开的“语义描述式”组成，这些“语义 描述式”又有以下3 种形式： 独立义原描述式。用“基本义原”，或者。( 具体词) ”进行描述。 关系义原描述式。用“关系义原= 基本义原”或者“关系义原= ( 具体词) ”或者 7 西安科技大学硕士学位论文 。( 关系义原= 具体词) ”来描述。 符号义原描述式。用“关系符号基本义原”或者。关系符号( 具体词) ”来描述。 “) 对于实词描述，第1 个描述式总是一个基本义原，这也是对该实词最重要的一个 描述式，这个基本义原描述了该实词的最基本的语义特征，称作第一独立义原描述式。 知网的特色主要表现在如下方面； ( 1 ) 知网是利用一种知识词典的描述语言来描述概念与概念之间的关系以及概念的 属性与属性之间的关系的知识系统。知网并不是一个在线的词汇数据库。 ( 2 ) 知网所描述的不仅包含同类概念之间的关系，如上下位关系、同义关系、反义关 系、对义关系、部件与整体关系、属性和宿主关系，还包含非同类概念之间的关系，如 属性值和属性的指向关系、事件和角色关系。 ( 3 ) 从语言学的角度。知网被认为是语义研究的结果。知网对语义研究的贡献可以归 结为两点：一是把语义研究置于知识描述的基础上；二是语义描述为网状。网状概念描 述的关键是对个别概念进行静态的、孤立的描述，最终形成动态的、相关的知识网。 ( 4 ) 知识词典是知网最主要的数据库，包含了若干文件，比如主要特征、次要特征文 等文件。这些文件都是知网不可或缺的组成部分。 ( 5 ) 知网从知识词典的建设看，是一个工程性项目，但它本身又是一项科学研究。它 提出了知识描述的系统框架和方法论。它们将成为专业知识库建设的基础。 2 2 语法分析 语法分析是对自然语言进行表层的形式化分析，包括词法分析和句法分析两部分。 2 2 1 词法分析 语言学上一般将“词”定义为“能够独立运用的、有意义的最小语法单位7 。词法 分析在自然语言理解中的重要性表现在两个方面： “词”是组成句子的基础单位，只有在对“词”的分析的基础上，才可能进行 更高一个层次的句法分析； 计算机关于自然语言的知识很大一部分是以机器语言词典( 给出词语的各项信 息，包括语法信息、语义信息、语用信息等) 的形式储存的。 词法分析是句法分析的基础。词法分析的主要任务是把接收到的自然语言进行切 分，并为每个切分的词加上词性标记，即自动分词和词性标注。为了能够达到快速准确 的自动分词和词性标注，在各环节中要考虑切分歧义的消除、未登录词的识别、兼类词 性的消除等问题。 词法分析的第一个任务自动分词就是把输入的字符串分割为词串，即把汉字符中包 含的“词”分离出来。 8 2 主现题自动批改相关理论 词法分析的第二个任务，在找出“词”之后，按照词性标准，给句子中词加上句法 范畴标记( p a r to f s p e e c ht a g g i n g ) 和语义范畴标记( w o r ds e n s et a g g i n g ) ，即词性标注。 现代汉语的书面形式是采用分句连写的方式，只有句与句之间有显式的标点符号作 为分隔标记，词与词之间没有显式的分隔标记，因此，必须先对句子进行词的切分 近2 0 年来，国内众多研究机构对计算机汉语文本自动切分进行了深入的研究，在 分词技术上取得了很大成就，提出了最大匹配法、最优路径法、特征词库法、邻接约束 法、人工神经网络方法、无词典分词法等分词方法。将这些方法归结为以下三类【”。 ( 1 ) 基于词典的方法 基于词典的方法称为机械分词法，它利用预先编制的词典，将待分析汉字串中各种 长度的字符串按照一定策略与词典中的词条进行匹配。能够匹配上的词串，就有可能成 为一个切分单位。根据不同的标准，基于词典的方法又可细分。按照扫描方向的不同， 可分为正向匹配和逆向匹配；按照优先匹配字符串的长度不同，可分为最大( 最长) 匹配 和最小( 最短) 匹配。机械分词方法的缺点是无法解决分词阶段的两大基本问题，即歧义 切分问题和未登录词识别问题。 ( 2 ) 基于概率统计的方法 概率方法是利用语料库和统计学的方法，找出可能的词边界或词。虽然概率方法不 要求有词典，但是它依赖于己训练的语料库，因而如果切分文本和训练语料库中的文本 类型不一样，切分的效率并不理想。从形式上看，词是稳定的字的组合，因此在上下文 中，相邻的字同时出现的次数越多，它们构成词的可能性就越大。因此字与字相邻共现 的频率或概率可以较好地反映词的可信度。可以对语料中相邻共现的各个字的组合的频 度进行统计，计算它们的互现信息，从而得到词的切分。互现信息体现了汉字之间结合 关系的紧密程度，当紧密程度高于某一个阀值时，便可认为此字组可能构成了一个词。 这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词 法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高但并不 是词的常用字组，如“这一”、“之一”，“有的”、。我的”、“许多的”等，并且 对常用词的识别精度差，时空开销大。 ( 3 ) 基于理解的方法 通常的分词系统都力图在分词阶段消除所有歧义切分现象。而有些系统则在后续过 程中来处理歧义切分问题，其分词过程只是整个语言理解过程的小部分。其基本思想就 是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象，通常 包括分词子系统、句法语义子系统、总控部分三个部分。在总控部分的协调下，分词子 系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人 对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识 的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理 9 西安科技大学硕士学位论文 i i 一ii i ；i i i 一 解的分词系统还处在试验阶段。 词法分析结果的准确性将在很大程度上影响后来的句法分析和语义分析。要提高词 法分析的准确性，需要在其过程中注意以下问题： 切分排歧 歧义处理是自动切分的难点之一，一般把切分歧义分为两种结构类型：交集型歧义 ( 交叉歧义) 和组合型歧义( 覆盖歧义) 。当前，能够较好处理切分歧义的分词算法( 8 1 有：交 叉歧义检测法、基于记忆的交叉歧义排除法、n 元语法和最大压缩方法等。 未登录词识别 未登录词是指没有包括在分词词表中但必须切分出来的词，包括各类专有名词、术 语、缩略词和新词等。未登录词的识别对于各种汉语处理系统不仅有直接的实用意义， 而且起到基础性的作用。 词性消歧 词性兼类是词性标注的主要问题，进行词性标注时的难点在于兼类词的消歧。汉语 中词的应用非常灵活，可充当不同的句子成分，所以词性兼类现象很普遍。通过统计， 兼类词在语料库文本中所占总词次的比例为2 5 7 6 。在有大规模标注语料库的情况下， 统计方法( 如隐马尔可夫模型) 可用于解决词性标注问题，而且结果通常也很好。 ， 虽然在词法分析申尚有这些问题没有解决，但相对来说，在自然语言理解的研究中， 词法分析是一个相对成熟，人们研究得较为深入的领域。 2 2 2 句法分析 句法分析是对构成句子短语内部的结构成分、结构层次和结构关系进行分析，不涉 及句子语气、语调和语用因素，也不考虑句首修饰语，故句法分析也称为短语分析。 目前对句法分析存在两种方法；一种是不对语句进行语法结构分析，只利用句子的 表层信息，称为浅层句法分析；另一种方法是对语句完全的句法分析，将分析结果以依 存树【9 】的形式表示，称为传统的分析方法。传统分析方法句法分析器的目标是获得完全 的句法树。 为了实现句法分析器，必须赋予计算机两项内容。 一是语法。为了让机器可以分析句子，需要让机器知道这些语法，这种面向机器处 理的语法称为形式语法，它是规定语言中允许出现结构的形式化说明。其中很重要的是 形式语法的表示方式。 二是语法分析算法。机器依据形式语法来识别和分析句子并决定其结构的方式。在 计算机自然语言处理中，更多地关心句法分析器的算法，因为句法分析器比识别器具有 更强的能力，能够提供更多的信息。句法分析算法还应包括采用的数据结构的构造，在 分析之后如何表示句子的句法结构等各个方面。在通常的人类自然语言中，未经分析的 1 0 2 主观题自动批改相关理论 句子是线性的符号串表示。 ( 1 ) 短语结构语法 为描述短语结构语法，需要介绍重写规则。重写规则是一种形式化表示方法，可以 用来描述规则，例如s _ n pv p 。其中，s 代表一个句子，n p 表示一个名词短语，v p 表示一个动词短语。该规则的意思是说左边的符号s 所代表的项可以被合乎语法的替换 成右边符号所代表的两个项，即被重写为右边两项的组合。 一个形式语法可以包含若干条重写规则，重写规则的集合用p 来表示。除此之外， 组成一个完整的形式语法还有另外几个要烈l o 】：一是所谓终结符号集合，用t 来表示， 一个终结符号代表一个这样的项，它在此语法中不能再被重写为其他项的组合，通常是 该形式语法所描述的语言中的词汇的语法类别( 如n ，v ，a d j 等等) ，或者就是该语言中 使用的词汇：二是非终结符号集合，用n 来表示，一个非终结符号代表一个这样的项， 它在此语法中可能再被重写为其他项的组合，如果上述终结符号指的是语言中的词汇本 身，那么非终结符号也包括词的语法类别；三是一个特殊的非终结符s ，表示句子。句 法分析针对的单位是句子，句子s 是对句子进行句法分析的开始或结束符号 这样，一个完整的用来描述一种语言的形式语法就可以表示为四元组 1 烈，s p ) ，且 t n n = ，即一个符号不能同时既是终结符号又是非终结符号。词汇表v - - t u n ，v 表 示由v 中的符号所构成的全部符号串( 包括空符号串妒) ，而矿+ 表示y 中除之外的一切 符号串的集合。p 中的每条规则形如：a 寸b ；其中a e v + ，b 矿，且a # b 。 短语结构语法的基本思想是【】：句子是由短语结构组成的。从整体句子开始，到句 子符号序列的产生，可以通过短语结构规则一步步推导出来。所以用短语结构语法来对 句子进行句法分析，就意味着是寻找一个从起始符到该句子的推导，这个推导通常表现 为一棵句法树。举例来说，我们有下面一部语法： 规则是： s n p v p n p n n p 寸r n p - - * a d jn p v p 专v n p 词典是： r 寸我 v 专喜欢 a d j 一红 n 一苹果 那么句子“我喜欢红苹果”的推导是： 西安科技大学硕士学位论文 查词典，使用规则s - , , n pv p 使用规则n p - , , r 词典匹配成功r j 我 使用规则v p - - c vn p s 词典匹配成功v _ 喜欢 s l rv n p i 我喜欢 使用规则n p 专r ，与词典不匹配，回溯。 使用下一条规则，n p - + a d jn p 与词典进行匹配，a 礴斗红 s n i v p i rv n p i 钠 我喜欢 1 2 人入。人人o r 今 2 主观题自动批改相关理论 、 7 v n pr ”p 我喜欢红 信用规i ) j n p - - - ) n 与词典进行匹配n 专苹果得到如图2 1 所示句法分析树 ，、 图2 1 句法树示意图 ( 2 ) 语法分析算法 线图( c h a r t ) 分析算法是一种通用的句法分析算法，具有简单、直观的特性。线图就 是一组结点和边的集合。 例如：系统是我们开发出来的。 词典中的词条有； r 一我们 n 系统 v 一是l 开发 出来 所使用的规则为： s 寸n p v p n p r n p jn n p s 。d e v p v n p s n pv p - v p v v 西安科技大学硕士学位论文 其中s ，v p ，分别表示带空位的s 和v p ，可以把s 和v p | 分别看成两个独立的短语类 型。 线图( c h a n ) 是一个无环有向图 线图是c h a r t 算法中最重要的数据结构【1 2 1 。线图是把词与词之间的间隔作为结点， 结点的标记一个序号来表示，把词和短语当作连接结点的边。边的方向总是从左到右， 边上面不仅要标记短语的类型，还需要标记产生该短语的规则。于是这个句子表示为图 2 2 或表2 2 ， 边 的 终 止 位 置 图2 2 传统线图的表示法 活跃边与非活跃边 活跃边就是没有完成的待处理的成份，非活跃边就是已经完成的成份。我们注意到， “系统是我们”和。系统是我们开发出来的”都是由规则s 岭n p 、，p 生成的，而且其中 “n p ”都是对应同一个结点( “系统”) 也就是说，这两次规则使用的过程中，有一个 表2 2 线图的另一种表示方法 6sv pn p v s v v v n , n p n , n p 0123455 边的起始位置 1 4 2 主观题自动批改相关理论 冗余的操作：将规则右部的第一个结点n p 与同一个结点( “系统”) 进行匹配。如果规则 很多，c h a r t 的结构很复杂，这种冗余是很严重的。为了消除操作过程中的冗余，在c h a r t 算法中，将边分为两种，一种叫做非活跃边，就是如图2 2 中我们已经见过的这种边。另 一种叫做活跃边，用于记录一条规则部分被匹配的情形。活跃边的引入，可以减少规则 匹配中的冗余操作，提高句法分析的效率。于是，规则s n pv p 生成结点“系统是我 们”的匹配过程可以记录为两条活跃边和一条非活跃边，如表2 3 所示。 表2 j 线圈的匹配过程 日程表( a g e n d a ) ， 在c h a n 算法中，还有一个重要的数据结构，称为“日程表( a g e n d a ) ”。线图分析的 过程就是一个不断产生新的边的过程。但是每一条新产生的边并不能立即加入到c h a r t 中，而是要放到日程表( a g e n d a ) 中。日程表( a g e n d a ) 实际上是一个边的集合，用于存放 已经产生，但是还没有加入到c h a r t 中的边。日程表( a g e n d a ) 中边的排序和存取方式，是 c h a r t 算法执行策略的一个重要方面。 点规则 在线图算法中，使用点规则来更加直观的表示。活跃边”和“非活跃边”。所谓点 规则1 1 3 1 ，是在规则的右部的终结符或非终结符之间的某一个位置上加上一个圆点，表示 规则右部被匹配的程度，其中圆点的位置表示规则已经匹配成功的位置( 从左边开始) 。 用c h a r t - 算法表示如图2 3 。 图2 3 线图的点规则表示 1 5 西安科技大学硕士学位论文 传统c l ! 雠算法的过程描述 将待分析字符串w 置入输入缓冲区，a g e n d a 清为空栈； 循环，反复执行下面步骤，直至输入缓冲区和a g e n d a 均为空； ( a ) 若a g e n d a 为空，则从输入缓冲区取一个字符，并把该字符及其起止位置( p l ， p 2 ) 推入a g 蚰d a 栈； ( b ) ) a a g e n d a 中弹出栈顶的边，该边的起止位置为( p l ，边上标记为l ； ( c ) 检查规则集中的规则，对所有形如a _ l 这样的规则，在活跃边集合中增加一 条起止位置为p l ，p 2 ，弧上为a l - 参这样的点规贝l j ； ( d ) 把, ) l a g e n d a 中弹出的标记为l 的边，加入到线图中的p l ，p 2 之间； 、 ( c ) 检查所有活跃边集合，如果存在起止位置为p o ，p l ，且弧上点规则为a - - - a l f l 的 活跃边