（计算机软件与理论专业论文）单向扫描分词算法研究与主观题评分系统实现.pdf

人迮理一l ：人学硕士学位论文 摘要 主观题评分系统是自动考试系统的重要的组成部分。中文分词技术是该系统实现的 技术基础。中文词法分析是中文信息处理中的一项基础性工作。词法分析结果的好坏将 直接影响中文信息处理上层应用的效果。本文针对词法分析中的中文分词进行了较深入 的研究并实现了一个实用化的分词系统，并在此基础上设计了一个具有一定应用意义的 主观题评分系统。 本文首先介绍了现有的各种分词方法，并基于最大正向匹配算法设计了一个分词系 统。由于基于理解的分词方法很难实现，而基于统计的分词方法又不适用于文字量比较 小的简答题情况，所以对最大工f 向匹配算法进行改进，提出了一种改进的单向扫描算法。 该算法对词典中的索引表进行改进，索引表实际上是一个哈希表，而设计的哈希函数是 参考汉字编码原理编写的，因此冲突率是o ，即无冲突。这样对索引表的查找就可以使 用哈希法，大大地提高了分词速度。 改进的单向扫描算法使用了带索引表和词性标注的词典，不但提高了分词速度，并 为后期的语意理解提供了词性信息，也是实现基于得分点简答题评分系统的必要前提。 该系统是根据现实中简答题按点给分的特点提出的。由于在分词阶段对词性进行了标 注，这样就可以提出得分点中的实词与学生作答答案中的实词进行匹配，当一个得分点 得到匹配时，就得到相应得分点的对应分值。所有得分值的和，即为最后得分。因此， 消除了整体匹配整体得分的缺点，提高了评分的精度，具有一定的应用价值。通过评测 和实际应用表明，该分词系统是一个可靠的，具有一定精度的分词系统。 关键词：评分系统；中文分词；最大正向匹配算法；改进的单向扫描算法 大连理：人学硕十学位论文 t h er e s e a r c ho fs i n g l es c a nc h i n e s ew o r ds e g m e n t a l g o r i t h ma n d r e a l i z a t i o no fs u b j e c tg r a d i n gs y s t e m a b s t r a c t t h es y s t e mo fg r a d i n gf o rs u b j e c tg r a d i n gs y s t e mi sa ni m p o r t a n tp a r to fa u t o m a t i c e x a m i n a t i o ns y s t e m t h ec h i n e s ew o r ds e g m e n t a t i o ni sat e c h n i c a lb a s ef o rt h es y s t e m c h i n e s el e x i c a la n a l y s i si st h ef o u n d a t i o no fc h i n e s el a n g u a g ep r o c e s s i n g t h er e s u l to f l e x i c a la n a l y s i sw i l la f f e c tt h ep e r f o r m a n c eo ft h ea p p l i c a t i o nf o ru p p e rl e v e l t h i sp a p e r m a k e sa ni n t e n s i v er e s e a r c ho fc h i n e s ew o r ds e g m e n t a t i o na n dd e s i g n e dac h i n e s ew o r d s e g m e n t a t i o n b a s e do nt h ef o u n d a t i o n ，d e s i g n e das u b j e c tg r a d i n gs y s t e mb a s e do nc h i n e s e s e g m e n t i n g f i r s t l y ，t h i sp a p e ri n t r o d u c e ds e v e r a lc h i n e s ep h r a s es e g m e n tm e t h o d sa n dd e s i g n e da s y s t e mo fc h i n e s ew o r ds e g m e n t a t i o nb a s e do nm a x i m u mp o s i t i v em a t c hm e t h o d b u tt h e s y s t e mb a s e do na p p r e h e n di sv e r yd i f f i c u l t yt oi m p l e m e n ta n dt h es y s t e mb a s e do ns t a t i s t i c a l i si n a p p l i c a b l et ot h es i t u a t i o no fs i m p l ea n s w e rq u e s t i o n sw i t hl e s sw o r d s s ow em a d es o m e i m p r o v e m e n to nt h em a x i m u mp o s i t i v em a t c hm e t h o d ，d e s i g n e da ni m p r o v e d - s i n g l es c a n c h i n e s ep h r a s es e g m e n tm e t h o d t h ea r i t h m e t i cd os o m ea m e l i o r a t i o no nt h ei n d e xt a b l eo f c h i n e s ed i c t i o n a r y ，a c t u a l l yt h ei n d e xt a b l ei sah a s ht a b l e ，t h eh a s hf u n c t i o nw ed e s i g n e di s c o n s u l tt h ep r i n c i p l eo fc h i n e s ec o d i n g ，s ot h e c o n f l i c t i n gr a t ei sz e r o ，i tm e a n sn oc o n f l i c t s o w eu s et h eh a s hm e t h o dt os c a nt h et a b l eo fi n d e x ，i m p r o v e dt h er a t eo ft h ec h i n e s ew o r d s s e g m e n t i m p r o v e d s i n g l es c a nc h i n e s ep h r a s es e g m e n tm e t h o du s i n gd i c t i o n a r yw i t hi n d e x t a b l ea n dp a r to fw o r di m p r o v e st h es p e e do fs e g m e n t a t i o n a n dt h i sd i c t i o n a r yp r o v i d e s m e s s a g ef o rp h r a s ep r o c e s s i ti sa l s ot h ep r e c o n d i t i o no ft h es u b j e c tp r o c e s ss y s t e m t h e s u b j e c tp r o c e s ss y s t e mb a s e so nt h ep r o c e s so fm a n u a lg r a d i n g b e c a u s ee a c hp h r a s ei n s t a n d a r da n s w e ro ri nt h es t u d e n t sa n s w e rh a sam a r ks i g n e dt h ep a r to fw o r d 。s ow ed i s t i l l t h es u b s t a n t i v e sf o r m a t c h i n g a f t e re a c hs u c c e s s f u lm a t c h i n g ，w ec a ng a i nt h es c o r e c o n n e c t e dt ot h ek e y t h es u m m a t i o no fa l ig a i n e ds c o r ei st h ef i n a ls c o r e s ot h i ss y s t e mc a n a v o i dt h ed i s a d v a n t a g eo fw h o l em a t c h i n ga n di ti m p r o v e st h eg r a d i n gp r e c i s i o n o fc a u s ei t h a st h ev a l u eo fa p p l i c a t i o n a c c o r d i n gt ot h et e s ta n da p p l i c a t i o n ，t h i ss y s t e mi sar e l i a b l e s y s t e mw i t hh i g hp r e c i s i o n 一i i i 单向扫描分词算法研究与土观题评分系统实现 k e yw o r d s ：s y s t e mo fg r a d i n g ：c h i n e s ew o r ds e g m e n t a t i o n ；m a x i m u mp o s i t i v em a t c h m e t h o d ：i m p r o v e d - s i n g l es c a nc h i n e s e p h r a s es e g m e n tm e t h o d i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：蛰望整日期：丝堕：厶z 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：兰垦生 聊躲出僻 迎应年月日 大连理j ：人学硕十学位论文 1绪论 1 1 本文的研究目的和背景 随着网络通讯技术的飞速发展，远程教育必将成为未来教育发展的一个显著趋势。 网上答题系统是网络教育平台一个必不可少的部分，远程考试作为当今教育界的热点一 直得到了众多教育界人士的推崇和赞誉。目前在国内多家著名学府已经设计了数量众多 的远程考试系统，使众多的优质教育资源得以跨越时间和空间的限制，被更多的学子所 享用。作为课堂教学的有益补充，它极大地提高了学生的学习兴趣，取得了良好的教学 效果。同时，远程考试系统在部分课程考试及平时自我测验过程中的应用，在很大程度 上缓解了教师的教学压力。针对于各类专门考试( 如计算机等级考试等 ) 的远程考试系统 也蓬勃发展起来，更由当初的仅仅局限于高等教育领域，向众多的初等教育领域扩展。 所以，远程考试系统的应用前景是非常广阔的，在今后很长一段时间里，将保持比较旺 盛的市场需求。所以对远程考试系统的开发具有很高的实用经济效益。 考试系统中对于客观题( 选择题、判断题、填空题) 等题型的自动阅卷算法采用的办 法就是用学生的答案与标准答案进行比较，比较结果一致，则答案正确，否则答案错误， 实现起来比较容易。如果一个考试系统中的考题都是客观题，这样的试卷不是一份好的 试卷，仅有这类题型的试卷对测试考生的能力还存在欠缺。因此，理想的试卷应针对不同 的学科还应该包括有主观题题型。对于主观题，由于它的答题特点和复杂性，目前还没有 一种考试系统能很好地完成其自动阅卷。主观题的自动评分涉及到人工智能、模式识别 以及自然语言理解等方面的理论和知识，需要解决很多技术上的问题，因而成为在线考试 系统中的一个技术难点。 要想解决这类问题，关键是采用何种分词算法以及如何对分词序列进行语义处理。 首先要解决的第一个问题就是如何分词。对于语言来说，词是最小的具有独立活动的有 意义的语言成分，然而汉语中词与词之间没有明确的分隔标记，而是连续的汉字串。显 然，自动识别词的边界，将连续的汉字串切分为带有分割标记的词串将是实现中文信息处 理的首要问题。 计算机不能像人一样直接处理或识别自然语言，只能通过人们编写的计算机应用程 序来处理。这些应用程序的目标是能使计算机快速f 确处理自然语言，缩小人与计算机 的理解差距。在当今信息化的社会，人们需要通过计算机来传递信息。而计算机在处理 信息时还无法解决人机交互的困难。信息处理程序就是为解决这些困难而来。 单向扫描分词算法研究与主观题评分系统实现 在西方，信息处理技术已经发展得比较成熟。而中文信息处理技术由于起步晚，更 为主要的原因是汉字是象形字，组成句子不需要像西文那样用空格来分隔单词，因而当 计算机处理中文时，更加深了人机之间对自然语言理解的差距。因此中文信息处理技术 无法直接应用西文信息处理技术。中文信息处理技术是我国重要的计算机应用技术，中 文信息处理软件是我国软件产业发展的重点之一。由于汉字文本的特点，在中文信息处 理中，首先就遇到中文分词的问题。中文分词技术是中文信息处理技术的基础，也是中 文信息处理技术发展的瓶颈。中文分词技术的发展直接影响着中文信息处理技术的发 展。我国自八十年代初期开始重视研究自动分词技术以来，分词技术取得了很大的进展， 提出了各种分词算法和分词模型，开发出了各种分词软件。而中文信息处理技术的广泛 使用，对分词技术的要求也越来越高。 中文分词的意义在于，使得计算机能够快速准确的处理中文信息。作为中文信息处 理的基础，分词的重要性不言而喻。主要表现在以下几个方面： ( 1 ) 分词是中文信息处理的基础性工作 汉语语言理解有着极其广泛的应用价值，在人机接口、问答系统、机器翻译等众多 的应用领域中，对输入文本进行句法分析是一项必不可少的处理任务。计算机从事句法 分析所凭借的语法信息不外乎来自机器词典和句法规则库。机器词典收录了每个词条的 语法、句法和语义知识，而句法规则一般来讲是在词类等知识基础上构造的。因此，对 汉语句子必须先进行词语切分处理，才有可能进行句法分析。如果对输入的源文件中的 句子未经分词处理，仍然是一些字符串序列，就无法根据句子中出现的每个具体的词到 机器词典中去查找相应的语言知识；而且如果不知道每个具体词的词性等词汇知识，也 就不可能直接调用相关的句法规则来判断句子的句法结构。 ( 2 ) 自动分词在中文信息处理的广泛应用 语词的计算分析已广泛应用于词频统计、新词辨识、计算机辅助编纂、词语搭配研 究和文章或风格学研究等众多领域。例如，词典编纂中选入词典中的词条，每条词语的 用法( 或义项) 以及相应的例句，不应是由编辑者生造，而都应从大规模真实语料中获取。 这些语料库的每个文本或实体，都应是在对语料进行切分、词性标注等处理后才能提供 使用。 ( 3 ) 汉语处理要求以词性等知识为依据 语言文献处理自动化只有根据词的文本特征，词性、词义和句法结构等更深层次的 语言知识才有用武之地，主要有汉语自动索引( a u t o m a t i ci n d e x i n g ) 、类( a u t o m a t i c 大连理上人学硕十学位论文 c l a s s i f i c a t i o n ) 、相似度( d o c u m e n ts i m i l a r i t y ) 、关键词聚类( t e r mc l u s t e r i n g ) 、信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 、信息抽取( i n f o r m a t i o ne x t r a c t i o n ) 等这些了领域。 ( 4 ) 以词为单位处理汉字语音、错别字、简繁转换“以词定字”、“以词定音”方 法是解决错别字辨识、多音字的字音辨识和简繁转换等的主要手段【。 1 2 国内外研究概况 目前国内外对中文分词的研究取得了很大的进展，然而还没有满足现实的需要。对 于自动分词中一些存在的主要的问题，没有得到很好的解决。表现在分词算法的运行速 度和精度难以达到理想的结果，对歧义切分和未登录词的识别也未能达到令人满意的程 度，更为主要的是至今未能对分词的标准达成统一的标准。目前研究中文分词的大多是 科研院校，清华、北大、中科院、北京语言学院、东北大学、i b m 研究院、微软中国研 究院等都有自己的研究队伍，专业研究的公司有海量科技一家。其中，目前认为最为成 功的中文分词技术是海量科技公司的中文分词组件产品，该功能公司的分词组件基本上 能满足一些中文信息处理领域的应用。 1 3 本文研究的主要内容 已有的分词算法已有多种，例如：基于理解的分词方法、将分词和词类标注结合起 来的分词算法、基于统计的分词方法、基于字符串匹配的分词方法等。基于字符串匹 配的分词方法作为最为古老的分词算法，其中的最大正向匹配算法具有结构清晰明确， 易于建立，在实践的过程中可以方便有效的建立数据结构，有效易读，便于理解与实现 等优点。在综合考虑了当今分词的几种主要算法的优劣之后，在选择算法的阶段，决定 使用最大正向匹配算法作为个人所使用的首选算法，在初期设计一个初级的分词系统。 之后，经过一段的实践应用，考虑到简答题文字量一般比较小，不适合采用串频统 计方法，在这罩设计了一种基于最大正向匹配算法的改进的单向匹配算法来进行分词。 希望能得到更高的效率。 进行比较成功的分词之后，在已有分词的基础上又设计实现处理主观题的评分系 统，现有简答题处理系统缺乏智能性，答疑系统只是根据做答答案是否于标准答案完全 匹配来决定是否得分，处理精度满足不了用户的需求。主观题在答题时一般采用语言叙 述的方式，而每个人对知识的理解程度不同，表达方式也不一致，即便学生的答案准确，也 很难与标准答案完全一致，若要象对客观题评分那样准确地对主观题进行评分几乎是不 可能的。但通过分析阅卷教师在评阅主观题时的常规思维，设计一套算法，模拟阅卷教师 的这种思维活动，在对学生答案和标准答案进行分析之后，就可较准确地给出学生的实际 单向扫描分词算法研究与主观题评分系统实现 得分。本文正是基于这种思想，采用与得分点进行匹配的方法，设计了一个用于主观题自 动评分的算法，测试结果初步达到预期目标。 简答题处理系统结合人工智能、自然语言理解和自动搜索技术等进行简答题的自动 评分是远程教育简答题处理系统的发展趋势。学生可以采用自然语言方式主观地回答问 题，具有良好测试效果。系统对教师输入的标准答案进行自动分词并溶入语意理解，同 时对学生给出的答案进行自动分词和语意理解，然后判断两个语意是否相同或相近，决 定能否得分。 大连理工大学硕士学位论文 2 汉语自动分词技术 2 1分词技术概述 2 1 1 中文分词的目的 任何一种语言其文章都是由字、词、短语、句、段、章组成，词是最小、能独立 活动的、有意义的语言成分，词汇处理是自然语言处理的基础。目前国内网页主要以汉 语和英语两种为主，在网页的分类和过滤系统中考虑中英文两种语言的分词处理。中英 文最根本的区别是中文以字为最小单位，句子中所有的字连接起来才能表达一个意思， 而英文是以词为单位的，词和词之间是靠空格隔开。因此分词技术在英文中根本没有必 要，而在中文中则必不可少 2 1 。 2 1 2 分词的概念 分词就是将连续的字序列按照一定的规则重新组合成连续的词序列的过程。在英文 的行文中，单词之间是以空格为自然的分界符的，而中文只是字、句和段可以通过明显 的分界符进行简单划分，唯独词没有一种形式上的分界符，虽然英文也存在短语的划分 问题，但是在词这一层上，中文要比英文复杂的多，也困难得多【3 】。 从实际应用上来说，汉语自动分词在汉语分析与理解、机器翻译、中文文献自动标 引或全文检索、汉字识别、汉语语音识别与合成、中文简繁体自动转换及文本处理( 中 文文本自动校对) 等领域中得到了广泛的应用。 作为中文信息处理的基础，中文分词的研究已经开展了近二十年，得到了许多研究 成果。然而到目前为止还没有真正成熟实用的中文分词系统面世，这成为严重制约中文 信息处理技术发展的瓶颈之一。 在介绍现有的中文分词方法之前，有必要先介绍一下中文分词的主要概念、中文分 词的应用领域以及研究成果。对中文分词技术的现状有个整体上的认识，将会有助于进 一步了解中文分词。 什么是中文分词? 众所周知，在英文中单词之间是以空格作为自然分界符的，在英 文的行文中，单词之间是以空格为自然的分界符的，而中文只是字、句和段可以通过明 显的分界符进行简单划分，唯独词没有一种形式上的分界符，句子所有的字连接起来表 达一个意思1 4 1 。例如，英文句子“i a l n as t u d e n t 用中文则为：“我是一个学生。 ， 计算机可以很简单的通过空格知道s t u d e n t 是个单词，但不能很容易明白“学”、“生 单向扫描分词算法研究与主观题评分系统实现 和起来构成一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有人也叫切 词。“我是一个学生 ，分词结果是：我是一个学生。 2 2 现有的中文分词技术 2 2 1基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充 分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功( 识别出 一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照 不同长度优先匹配的情况，可以分为最大匹配和最小匹配；按照是否与词性标注过程相 结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法【5 】。常用的几种机械 分词方法如下： ( 1 ) 正向最大匹配法( 由左到右的方向) 。 ( 2 ) 逆向最大匹配法( 由右到左的方向) 。 ( 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配 方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹 配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也 较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最大匹 配的错误率为1 2 4 5 t 6 ，但这种精度还远远不能满足实际的需要。实际使用的分词系统， 都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切 分的准确率。对于机械分词方法，可以建立一个一般的模型，在这方面有专业的学术论 文，这里不做详细论述。 2 2 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思 想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下， 分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模 拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语 言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前 基于理解的分词系统还处在试验阶段1 7 j 。 一6 一 大连理工大学硕士学位论文 2 2 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越 多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的 可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。 定义两个字的互现信息，计算两个汉字x 、y 的相邻共现概率。互现信息体现了汉字之 间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一 个词。这种方法只需对语料中的字组的频度进行统计，不需要切分词典，因而又叫做无 词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度 高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的 、“许多 的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用 一部基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词， 即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用 了无词典分词结合上下文识别生词、自动消除歧义的优点。 2 3 现有分词系统介绍 自8 0 年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系统逐步 得以开发，其中几个比较有代表性的自动分词系统在当时产生了较大的影响。 ( 1 ) 清华大学s e g 分词系统 此系统提供了带回溯的正向、反向、双向最大匹配法和全切分评价切分算法，由 用户来选择合适的切分算法。其特点则是带修剪的全切分评价算法。系统考虑到了切 分盲点的问题( 某些字串永远不会被某种分词方法匹配出来) ，由此提出了全切分的概念， 即找出输入字串的所有可能的子串，然后利用某种评价方法从所有这些可能的子串中选 出最佳子串序列作为分词结果。为了解决全切分所带来的组合爆炸问题，又引进了对全 切分过程进行修剪的方法，强制性地截止某些全切分的进行。用户在使用时，对于歧义 较少的语料，可采用正向或反向最大匹配法；对于有较多交叉歧义的语料，可使用双向 最大匹配法：对于其它歧义较大的语料，则采用全切分评价算法，并需要采用一个合 适的评价函数。由于对具体语料的统计参数设置了不确切初值，全切分评价算法在第 一、二遍切分过程中的正确率较低，随着切分的多遍进行，评价函数逐渐得以矫正，系 统的切分精度逐步得以提高。经过封闭试验，在多遍切分之后，全切分评价算法的精 度可以达到9 9 左右。 ( 2 ) 清华大学s e g t a g 系统 单向扫描分词算法研究与主观题评分系统实现 此系统着眼于将各种各类的信息进行综合，以便最大限度地利用这些信息提高切分 精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标志、预切分模式、 其他切分单位。为了实现有限的全切分，系统对词典中的每一个重要的词都加上了切分 标志，即标志“c k ”或“q k ”。“q k ”标志表示该词可进行绝对切分，不必理会它是否 产生切分歧义；“c k 标志表示该词有组合歧义，系统将对其进行全切分，即保留其所 有可能的切分方式。系统通过这两种标志并使用几条规则以实现有限的全切分，限制过 多的切分和没有必要的搜索。规则包括： 无条件切出q k 类词： 完全切分c k 类词( 保留各个子串) ； 对没有标记( q k 或e k ) 的词，若它与别的词之间存在交叉歧义，则作全切分；否 则将其切出。 为了获得切分结果，系统采用在有向图d a g 上搜索最佳路径的方法，使用评价 v a l u a t e ( p a t h ) ，求此评价函数的极大值而获得最佳路径p m a x 。所运用的搜索算法有 两种，即“动态规划”和“全切分搜索+ 叶子评价 ，使用了词频、词类频度、词类共 现频度等统计信息。通过实验，该系统的切分精度基本上可达到9 9 左右，能够处理未 登录词比较密集的文本，切分速度约为3 0 字秒。 ( 3 ) 国家语委文字所应用句法分析技术的汉语自动分词 此分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分歧义。切 词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分可能中选择出合理 的切分结果。其过程由两步构成：一、对输入字串进行处理，得到一个所有可能的切分 字串的集合，即进行( 不受限的) 全切分；二、利用句法分析从全切分集合中将某些词选 出来，由它们构成合理的词序列，还原为原输入字串。系统使用一个自由传播式句法分 析网络，用短语文法描述句法规则，并将其表示为层次化网络图，通过此网络的信息传 递过程来进行选词。网络的节点分为词类节点( 终结符节点) 和规则类节点( 非终结符节 点) 。词类节点保存词的信息；规则类节点对信息进行合并和句法、语义分析，生成新 的信息，并将本节点的信息传递出去( 也就是用文法产生式进行归约，并进行属性计算 作者注) 。网络运行的初态是所有节点状态为n o ，各种可能切分的字串进入响应相应 的词类节点( 终结符节点) ，然后开始运用文法进行计算。当网络的最高层节点s ( 文法 起始符号) 达到稳定状态o k 时，计算结束，在最高节点处输出最后的切分结果。 从一般的角度来看，应用句法分析技术进行切词的方法是一种“生成测试”方法， 它是一种常用的a j 问题求解方法，包括两个步骤：生成步一找出所有可能的解( 假设) ； 大连理工大学硕士学位论文 测试步一对各个假设进行检验，找出合格者。在应用句法分析进行切词时，其测试步是 使用汉语的句法规则检验某种切分结果是否构成合法的汉语句子。这样可以将句法分析 理论的各种成果用于切词之中，有多种句法分析技术可以应用，常见的是a t n 分析、 c y k 分析( c h a r tp a r s i n g ) 、g l r 分析等。可以将这种方法称作“切词句法分析一体化” 方法。随着软硬件水平的不断提高，直接运用时空消耗比较大的句法分析来检查分词结 果的方法正在日益显现其优越性。 ( 4 ) 复旦分词系统 此系统由四个模块构成。一、预处理模块，利用特殊的标记将输入的文本分割成较 短的汉字串，这些标记包括标点符号、数字、字母等非汉字符，还包括文本中常见的一 些字体、字号等排版信息。一些特殊的数词短语、时间短语、货币表示等，由于其结构 相对简单，即由数词和特征字构成，也在本阶段进行处理。为此系统特别增加一次独立 的扫描过程来识别这些短语，系统维护一张特征词表，在扫描到特征字以后，即调用这 些短语的识别模块，确定这些短语的左、右边界，然后将其完整地切分开；二、歧义识 别模块，使用正向最小匹配和逆向最大匹配对文本进行双向扫描，如果两种扫描结果相 同，则认为切分正确，否则就判别其为歧义字段，需要进行歧义处理；三、歧义字段处 理模块，此模块使用构词规则和词频统计信息来进行排歧。构词规则包括前缀、后缀、 重叠词等构词情况，以及成语、量词、单字动词切分优先等规则。在使用规则无效的情 况下，使用了词频信息，系统取词频的乘积最大的词串作为最后切分结果；最后，此系 统还包括一个未登录词识别模块，以解决未登录词造成的分词错误。未登录词和歧义字 段构成了降低分词准确率的两大因素，而未登录词造成的切分错误比歧义字段更为严 重，实际上绝大多数分词错误都是由未登录词造成的。系统对中文姓氏进行了自动识别， 它利用了中文姓名的用字规律、频率，以及姓名的上下文等信息。通过对十万以上的中 文姓名进行抽样综合统计，建立了姓氏频率表和名字用字频率表，由此可获得任意相邻 的二、三个单字构成姓氏的概率大小和某些规律，再利用这些字串周围的一些称谓、指 界动词和特定模式等具有指示意义的上下文信息，可对字串是否构成姓名进行辨别。实 验过程中，对中文姓氏的自动辨别达到了7 0 的准确率。系统对文本中的地名和领域专 有词汇也进行了一定的识别。 ( 5 ) 哈尔滨工业大学统计分词系统 该系统是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词匹配结合 起来。系统由三个部分构成：一、预处理模块，利用显式和隐式的切分标记( 标点符号、 数字、a s c i i 字符以及出现频率高、构词能力差的单字词、数词+ 单字常用量词模式) 将 待分析的文本切分成短的汉字串，这大大地减少了需要统计的( 无效) 字串的数量和高频 一9 一 单向扫描分词算法研究与主观题评分系统实现 单字或量词边界串；二、串频统计模块，此模块计算各个已分开的短汉字串中所有长度 大于l 的子串在局部上下文中出现的次数，并根据串频和串长对每个这样的子串进行加 权，加权函数为( f 为串频，l 为串长，即串中汉字个数) 。根据经验，局部上下文中取 为2 0 0 字左右。局部上下文的串频计算使用一个滑动窗口( 为一个队列式缓冲区，保存 当前待切分汉字串及其前后2 0 个短串) ，当当前待切分汉字串处理完之后，窗口下移一 个短串( 中心变为相邻下一个短串) 。系统采用一个外散列表来记录窗口中的短串，以加 快窗1 3 中串频计数。散列函数取为汉字的g b 8 0 位码( 二级汉字共用入口9 5 ) ，每个桶中 保存窗口中每一行( 短串) 上的汉字位置：( 短串的行号，汉字列号) ，并且对于在窗口中 出现多次的汉字位置用一个链指针连接起来，则计算某个字串在窗口中出现的频度时， 不必将该字串与窗口中的短串逐个匹配，而只需统计在该字串中的各个汉字所对应的位 置链表中能够相邻的位置的序列的个数即可。此外，还需要根据词缀集( 前、后缀集合) 对字串的权值进行提升，例如“处理器 中“处理 的权值很高，但由于对“处理器 的权值作了提升( 达到或超过了“处理) ，就不会切成“处理器。如果某个汉字串的 权值超过某一阈值d ( 取为4 0 ) ，则将此汉字串作为一个新识别的词，将其存入一临时词 库中；三、切分模块，首先用临时词库对每个短的汉字串进行切分，使用的是逐词遍历 算法，再利用一个小型的常用词词典对汉字短串中未切分的子串进行正向最大匹配分 词。对于短汉字串中那些仍未切分的子串，则将所有相邻单字作为一个权值很低的生词 ( 例如“玛”、“莉 ) 。其中每个模块都对待分析的文本进行了一次扫描，因而是三 遍扫描方法。此系统能够利用上下文识别大部分生词，解决一部分切分歧义，但是统计 分词方法对常用词识别精度差的固有缺点仍然存在( 例如切出“由来 、“语用 、“对 联 等、) 。经测试，此系统的分词错误率为1 5 ，速度为2 3 6 字秒。 ( 6 ) 杭州大学改进的m m 分词系统 考虑到汉语的歧义切分字段出现的平均最大概率为1 ，1l o ，因而机械分词的精度在 理论上能够达到1 1 1 0 0 = 9 9 1 。那么是否还有更一般、精度更高的机械分词系统呢? 根据统计，汉语的局部( 词法一级) 歧义字段占了全部歧义的8 4 ，句法歧义占1 0 ，如 果提高系统处理这两类歧义的准确率，则可以大幅度提高切分精度。这方面的改进导致 了改进的m m 分词算法。将其阐述如下。通过对交叉歧义字段的考察，发现其中8 0 以上可以通过运用一条无需任何语言知识的“归右原则( 交叉歧义字段优先与其右边 的字段成词) 就可以获得正确切分，这是因为在多数情况下汉语的修饰语在前、中心词 在后，因而“归右 好于“归左 。“归右原则 可以使机械分词的精度上升到9 9 7 0 。 这种考察给出了鼓舞人心的结果，有可能使机械分词系统达到这样的理论精度。不过“归 人连理i ：人学硕+ 学位论文 右原则 还有需要修诈的地方，既对于“连续型交叉歧义”会发生错误，需要补充一条 “左部结合”原则：若a b c d e 为连续型交叉歧义字段，“归右原则”产生切分a b c d e ； 再由“左结合原则”( 合并最左边的a 、b ) 而得到a b c d e 。例如“结合成分子 一“结 合成分子”一“结合成分子”。但是仍然还有例外，例如“当结合成分子时”一“当 结合成分子时 ；为此引入“跳跃匹配”，在词典中定义“非连续词”( 实际上为串模 式l “当事时”，然后在切分时首先分出“当结合成分子时，然后再用“归右+ 左结合” 切分中间的歧义字段。以上3 项技术将机械分词的理论切分精度提高到了9 9 7 3 。综 合以上思想，就建立了如下改进的m m 分词算法： + 增字最大匹配( 包括“跳跃匹配非连续词 ) + 词尾歧义检查( 逐次去掉首字做m m 匹配以发现交叉歧义字段) + “归右原则”( 对于“连续型交叉歧义”还需要“左结合原则 ) 。 系统的词典采用一级首字索引结构，词条中包括了“非连续词”( 形如c 1 事c n ) 。 系统精度的实验结果为9 5 ，低于理论值9 9 7 3 ，但高于通常的m m 、r m m 、d m m 方法。 ( 刀m i c r o s o f tr e s e a r c h 汉语句法分析器中的自动分词 微软研究院的自然语言研究所在从9 0 年代初开始开发了一个通用型的多国语言处 理平台n l p w i n ，最初阶段的研究都是对英语进行的。大约从1 9 9 7 年开始，增加了中 文处理的研究，从而使n l p w i n 成为能够进行7 国语言处理的系统( 其中日语和韩语部 分的研究已较早地开展起来) 。中文部分的研究在开始时缺少必要的基础资源，于是经 过细致的研究分析之后，购买了北大计算语言所的现代汉语语法信息词典，从此进 展顺利，在短短的一年半的时间里达到了其它东方语种的处理水平。据报道，n l p w i n 的语法分析部分使用的是一种双向的c h a r tp a r s i n g ，使用了语法规则并以概率模型作导 向，并且将语法和分析器独立开。 其中文部分的一个特点是将词的切分同句法分析融合起来，即是一种前面提到过 的“切词一句法分析一体化”方法：在其匹配切词阶段保留所有可能的切分结果( 包括 歧义切分l ，然后在句法分析阶段使用汉语的句法规则判断切分的合理性，如果对句子 的某种切分能够成功地建立起完全的句法树，则表示该切分结果是正确的。对于有上下 文及语用歧义的歧义切分字段，系统将生成两棵以上的分析树( 可以使用某种标准进行 排序) 。 当然，为了提高系统效率，有必要在分词阶段排除尽可能多的局部一级的切分歧义。 其中使用的技术有：消除所有导致词典中没有对应词条的单字的切分，为词典中的每一 个词条增加一项“a t o m i c ”属性( 为1 表示不需要分析其内部字串，为0 表示需要保留 单向扫描分词算法研究与土观题评分系统实现 其内部的切分，即是一种组合歧义标志作者注) ，以及为每个词增加l e f l c o n d l 、 r i g h t c o n d l 、l e f l c o n d 2 、r i g h t c o n d 2 四类字符集合( 前两项表示歧义绝对生效，后两项 表示歧义有比较高的可能性生效，即歧义的直接前后文一作者注) ，还包括一些排歧规 则( 例如对于连续型歧义字段a b c d ，如果a b 和c d 不与前后词交叉、a 或d 是名词、 a b c 和b c d 都不是词，则切分出a b c d ：“昨天下午 一“昨天下午”) 。 实验结果表明，系统可以j 下确处理8 5 的歧义切分字段，在p e n t i u m2 0 0p c 上的速 度约6 0 0 9 0 0 字秒。考虑到系统对多种切分结果进行了完全的句法分析、对词典每个属 性进行了完全的查找，这是相当可观的效率。 ( 8 ) 北大计算语言所分词系统 本系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结合的分词 系统。由于将分词和词类标注结合起来，系统可利用丰富的词类信息对分词决策提供帮 助，并且在标注过程中又反过来对分词结果进行检验、调整，同时将基于规则的标注排 歧与基于语料库统计模型的排歧结合起来，使规则的普遍性与灵活性得到统一，而且对 未登入词的估算到达了相当高的准确率。系统的处理过程包括了自动切分和初始词性标 记、切分歧义字段识别、组词和标注预处理、词性标记排歧、切分和词性标注后处理等 过程，系统的算法综合了多种数据组织和搜索技术，以很低的时空开销实现了高速匹配 和查找，同时采用了当代计算语言学的统计方法，运用隐m a r k o v 过程进行词类标注和 排歧，对算法的效率和稳固性都作了尽可能的优化。此系统的一大特色是对通用性的强 调，将最稳定、最常用的4 万6 千余条现代汉语基本词汇( 即将扩充到7 万多条) 及其有 关属性组织成为基本词典，这些词的基本地位都是由汉语语言学家逐一检验认可的，这 是本系统通用性的保证；在此词典的基础上充分利用汉语构词法的研究成果，可以识别 出大部分的常用词。同时本系统对用户词典机制作了最大限度的扩展，允许用户加入3 部到3 0 部以上的自定义词典，并允许用户对这些词典的优先顺序自由排列，这样就可 以用较小规模的多个特殊词典更有针对性地解决具体领域的文本处理。因此本系统的语 言模型实现了通用性与多样性的有效结合，并到达了极高的效率。经过最近在搜索算法 上的改进，系统的分词连同标注的速度在p e n t i u m1 3 3 h z 1 6 m b 内存机器上的达到了每 秒3 千词以上，而在p e n t i u mi i 6 4 m b 内存机器上速度高达每秒5 千词。 2 0 0 3 年7 月s i g h a n 在同本札幌举办了首届国际中文分词评测b a k e o f f 。b a k e o f f 采用了不同于国内8 6 3 、9 7 3 评测的另外一种分词评测方案。即事先在网上公布四种不 同标准的训练语料( 带标语料) ，一个月后公布与这四种标准相应的测试语料( 原始语料) 。 参评系统可以在这些语料中任意选择一种或多种标准来考评自己的分词系统。在每种语 人连理l ：人学硕士学位沦文 料库上又分封闭和丌放两种测试：封闭测试只允许使用从指定训练语料中获取的知识 ( 如词表、n 元文法等) 来从事自