（计算机应用技术专业论文）基于最大匹配的书面汉语自动分词研究.pdf

硕士学位论文 摘要 书面汉语自动分词是中文信息处理中的重要步骤，它是文本校对、机器翻译、 文本分类、文本检索、计算机人机接口等诸多中文信息应用领域的基础。目前汉 语自动分词方法主要包括基于字符串匹配的方法、基于统计的方法和基于理解的 方法。本文存深入分析现有自动分词算法的基础i 二，着重研究了基于字符串匹配 的汉语自动分词算法，引入最大匹配法预处理分词，同时运用统计方法进行歧义 切分和未登录词识别。 根据汉语中二字词较多的特点，给出一种改进的自动分词词典机制，该机制 在词典数据结构中增加二字词检测位图表。在此基础上，对最大匹配分词算法进 行改进，实现了一种基于二字词检测位图表的最大匹配分词算法，本算法利用二 字词检测位图表快速判断二字词，减少词典匹配次数，以提高自动分词速度。针 对伪歧义型高频最大交集型歧义字段在大型语料库中表现出较强的稳定性和一 定的覆盖能力，歧义处理着重于研究该类歧义字段的自动获取，将它们的正确切 分形式记录到歧义库中，其歧义消解通过直接查表实现，这在本质上是一种基于 记忆的策略。未登录词识别技术研究着眼于w e b 资源中未登录词的获取，并提 出一种基于w e b 查询日志的来登录词识别算法，本算法分析w e b 查询日志的搜 索关键字频度表识别未登录词。 基于上述研究结果，设计并实现了一个面向实际应用的书面汉语自动分词系 统。实验结果表明：在相同条件下，基于二字词检测位图表的最大匹配分词算法 较原算法分词速度更快。利用卡耐基梅隆大学分词评估系统进行评测，评测结果 表明，基于二字词检测位图表的最大匹配分词算法的查准率提高了3 5 7 ，f - 1 测度提高了o o l ，较原算法具有更好的性能。系统还具有较好的稳定性。 关键词：汉语自动分词；最大匹配；二字词；歧义切分；伪歧义；未登录词识别 查准率 耋三苎查竖璧墼童堑堡重垦塑坌望墼塞 a b s t r a c t w r i t t e nc h i n e s ea u t o m a t i c s e g m e n t a t i o ni s a n i m p o r t a n ts t e pi nc h i n e s e i n f o r m a t i o np r o c e s s i n g i ti st h ef o u n d a t i o ni nm a n ya p p l i c a t i o nf i e l d so fc h i n e s e i n f o r m a t i o n ，s u c ha s t e x tc h e c k i n g ，m a c h i n et r a n s l a t i o n ，t e x tc l a s s i f y i n g ，t e x t r e t r i e v i n g ，m a n - m a c h i n ei n t e r f a c eo fc o m p u t e r ，e t c a tp r e s e n t ，t h r e em a i nm e t h o d s h a v eb e e nu s e df o rc h i n e s ew o r ds e g m e n t a t i o n ，w h i c hi n c l u d ec h a r a c t e rm a t c h i n g m e t h o d ，s t a t i s t i c a lm e t h o da n du n d e r s t a n d i n gm e t h o d t h r o u g ha n a l y z i n gt h ee x i s t e d c h i n e s ew o r ds e g m e n t a t i o na l g o r i t h m s ，t h i sp a p e re m p h a s i z e so nt h er e s e a r c ho f c h a r a c t e rm a t c h i n gm e t h o d ，u s em a x i m u mm a t c hm e t h o dt os e g m e n tw o r df i r s t l y ， t h e na p p l ys t a t i s t i c a lm e t h o dt oa m b i g u o u ss e g m e n t a t i o na n dt h er e c o g n i t i o no f u n k n o w nw o r d s a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fm o r et w o w o r dw o r d si nc h i n e s e ，p r o v i d ea n i m p r o v e dd i c t i o n a r ym e c h a n i s m ，w h i c ha d dt w o w o r d - b i t m a pi n t ot h ed a t as t r u c t u r e o ft h ed i c t i o n a r y o nt h i sb a s i s ，w ei m p r o v et h em a x i m u mm a t c hm e t h o d ，r e a l i z ea m a x i m u mm a t c hm e t h o dt h a tb a s e do n t w o - w o r d - b i t m a p ，w h i c h u t i l i z e t w o w o r d b i t m a pt or e c o g n i z et w o w o r dw o r d sf a s t ，r e d u c et h en u m b e ro f t i m e so f m a t c h i n gt h ed i c t i o n a r y ，s oa st oe n h a n c et h es p e e do fa u t o m a t i cw o r ds e g m e n t a t i o n a s w ef i n dt h a tt h ep s e u d ot y p eo fh i g hf r e q u e n tp a r to fm a x i m a lc r o s s i n g a m b i g u i t i e si ss t r o n gi nc o v e r a g ec a p a c i t ya n dr a t h e rs t a b l ew i t hr e g a r d t od o m a i n s h i f t i n g ，w ep r o p o s ef o ro b t a i n i n gt h eh i g hf r e q u e n tm a x i m a lc r o s s i n ga m b i g u i t i e s a u t o m a t i c a l l y ，a d d t h ec o r r e c tf o r mo ft h e h i g hf r e q u e n t m a x i m a l c r o s s i n g a m b i g u i t i e si n t o t h ea m b i g u i t i e sd a t a b a s ea n dc l e a ru pt h ea m b i g u o u st h r o u g h m a t c h i n gt h ea m b i g u i t i e sd a t a b a s ed i r e c t l y ，w h i c hi s am e m o r y 。b a s e ds t r a t e g yi n e s s e n c e t h es t u d yo ft h er e c o g n i t i o nt e c h n o l o g yo fu n k n o w nw o r d sf o c u s e s o n o b t a i n i n gt h eu n k n o w nw o r d sf r o mw e br e s o u r c e s ，a n dp r o p o s ea na l g o r i t h mo nt h e b a s i so fw e bq u e r yl o g s ，w h i c ha n a l y z eq u e r yw o r df r e q u e n c yf o ru n k n o w nw o r d s r e c o g n i t i o n o nt h eb a s i so ft h e r e s e a r c h e sm e n t i o n e da b o v e ，w ed e s i g na n dr e a l i z eaw r i t t e n c h i n e s ea u t o m a t i c s e g m e n t a t i o ns y s t e mf a c i n g p r a c t i c a la p p l i c a t i o n t h e e x p e r i m e n t a lr e s u l ts h o w s ：u n d e rt h es a m ec o n d i t i o n ，t h ei m p r o v e dm a x i m u m m a t c h a l g o r i t h mt h a tb a s e do nt h et w o - w o r db l t m a ph a sf a s t e n e ds e g m e n t a t i o ns p e e dt h a n o r i g i n a la l g o r i t h m t h r o u g ht e s t i n gt h es y s t e mb y c h i n e s ew o r ds e g m e n t a t i o n e v a i u a t i o nt o o l k i to fc a r n e g i em e l l o nu n i v e r s i t y ，t h er e t u r n e dd a t as h o wt h a tt h e i i p r e c i s i o nv a l u eo ft h ei m p r o v e dm a x i m u mm a t c hm e t h o db a s e do nt h et w o w o r d b i t m a ph a sr a i s e d3 7 5 a n df - 1m e a s u r eh a sr a i s e d0 0 1 t h e s ed a t ah a v ep r o v e d t h a to u rs y s t e mh a sab e t t e rp e r f o r m a n c e 。b e s i d e s ，t h es y s t e mh a sag o o ds t a b i l i t y k e y w o r d s ：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 mm a t c h ；t w o w o r dw o r d s ； a m b i g u i t i e ss e g m e n t a t i o n ；p s e u d ot y p e o fa m b i g u i t i e s ；u n k n o w n w o r dr e c o g n i t i o n ；p r e c i s i o n 耋三塞查些堡墼童雪坚曼窒垫丝堡丝塞 插图索引 图1 1 全文结构图 图3 tm m 算法流程 图32m p 算法流程 图4 ，1 ( a ) p f r l 0 中词数分布信息 图4 1 ( b ) p f r l 0 中词频分布信息 图4 2 词典组织结构 图4 3 词典文件类定义 图4 4 分词词典存储结构图 图4 5 二字词位图映射表类定义 图4 6 函数s e t v a ig o 算法流程 图4 7 函数is e x j t 算法流程 图4 8 函数c h e c k 2 c w o r d 算法流程 图49 快速判断二字词算法流程 图4 1 0 基于二字词检测位图表咖算法流程 图4 11 交集型歧义切分字段定义 图4 12 最大交集型歧义切分字段定义 图4 13 真歧义定义 图4 1 4 伪歧义定义 图4 1 5 歧义检测算法流程 图4 16 歧义切分算法流程 图4 17 歧义库加载算法流程 图4 ，1 8 歧义切分前后p 值变化 图4 1 9 竣义切分前后r 值交化 图4 2 0 歧义切分前后f 一1 测度变化 图4 2 1y a h o o 和b a i d u 中u r l 地址分析 图4 2 2 基于w e b 查询日志挖掘的未登录词识别算法流程 图4 2 3 函数c h e o k u n l o g i n w o r d 算法流程 图5 1 自动分词系统框架- - ， 2 l 2 2 一2 5 一2 5 2 6 ，2 7 2 7 。2 8 2 9 3 0 3 0 3 l 3 3 3 5 3 5 3 5 3 6 3 7 3 8 3 9 4 0 ，4 0 4 0 。4 2 4 3 4 4 4 7 顼士学位沦文 附表索弓 表3 1 现有词典机制比较 表3 2m m 和m p 分词算法比较 表4 1p f r l 0 中词统计信息 表4 2 基于二字词检测位图表的删算法测试结果 表4 3 歧义切分前分词结果 表4 4 歧义切分后分词结果 表4 5 未登录词识别测试， 表5 1 分词系统测试结果， v 2 0 2 2 2 4 3 4 3 9 3 9 4 4 4 8 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 橱超日期：硎乒年胆月引日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“4 ”) 作者签名：搠超 导师签名：乞茗勿嵋 日期：工卯牟年f 二月弓j 日 日期：z 口p 争年，2 月弓j 日 1 1 课题来源 第1 章绪论 本课题来源于湖南省自然科学基金资助项目，项目名称：基于数据挖掘技术 的语音合成方法研究，项目编号：0 3 j j y 3 0 9 7 。 1 2 研究目的与意义 i n t e r n e t 的迅速发展，使得网上的网页、电子邮件、数据库、聊天室和数字 图书馆等信息资源成指数级不断增长，如何自动处理这些海量信息就成为目前重 要的研究课题。2 0 0 4 年4 月1 日，中国互联网信息中心( c n n i c ) 在北京发 布了2 0 0 3 年中国互联网络信息资源数量调查报告，截至2 0 0 3 年1 2 月3 1 日， 中国网页总数为3 1 l ，8 6 4 ，5 9 0 个，2 0 0 3 年中文信息资源数量与2 0 0 2 年同期相比 增长了1 0 4 8 t 扪。为了适应中文海量信息处理的要求，自动中文信息处理已成 为一项重要的任务。本论文主要研究自动中文信息处理中书面汉语的自动分词问 题。 众所周知，书面汉语是由汉字串构成的，词与词之间没有空格等明显的分隔 标记，在自动中文信息处理时，如果简单地以字为单位进行分析和理解，就因为 表达意思不明确而没有太多实用价值；如果以甸为单位进行分析和理解，则因重 现率太低，在统计意义上也没有什么价值。词是最小的、能够独立活动的、有意 义的语言成分，是构成和分析语言的基本单位，因此，要将汉语纳入以词法、句 法、语义等按层次分析的体系中去，建立汉语中词的规范并将汉语的基本语言单 位由字转换为词，就成为必需的环节，这就是词的切分( 即分词) 问题1 3 j 。词的 切分使得书面汉语词与词之间有了形态上的切分标记。使用计算机自动进行词的 切分，就是汉语的自动分词问题。目前中文信息处理技术要落后于西文信息处理 技术，许多西文的处理方法不能被中文直接采用，究其原因，就是因为中文必须 有分词这道工序。 书面汉语自动分词作为中文信息处理技术的基础，有着极其广泛的实际应 用，从基本的输入系统，如智能语句输入法、语音输入、手写输入；到文字处理， 如文本校对、简体繁体转换、拼音标注；以及语音合成，文本检索，文本分类， 自然语言接口，自动文摘等等，无处不渗透着分词系统的应用【4 1 。通过对自动分 词技术的深入研究，开发出高质量，多功能的分词系统，必将促进中文信息处理 系统更加广泛的应用。 迄今为止，书面汉语自动分词的研究已经取得了很大的进展，但是对于自动 ：一 耋王墨奎竖堡墼童堡堡重璺2 2 ：塑耋 分词中所涉及的一些关键问题，如：词表规范、词典结构、歧义切分、未登录词 识别技术等，目前仍然没有很好的解决方案。汉语自动分词是其它中文信息处理 技术的基石，因此，中文信息处理技术的进步和中文信息处理系统的广泛应用， 有待于尉分词中的关键问题进行迸一步的深入研究和探索，如：制定和颁布国家 通用的分词词表规范，优化词典的数据结构，研究歧义切分字段类型，增强歧义 判别的能力，提高专有名词的识别率，研究汉语的构词规则和词法规则，研究未 登录词识别技术等等。 本论文旨在比较目前汉语自动分词所采用的主要算法，分析这些算法对分词 结果的影响，找出分词系统研制的重点和难点，在此基础上，对书面汉语自动分 词的切分算法、歧义切分和未登录词识别技术进行改进，阻提高自动分词系统的 效率。 1 3 研究内容 本论文以书面汉语的自动分词为研究目标。自动分词课题的研究内容主要包 括： 1 如何确立什么是词、哪些是词，即分词规范问题。 2 如何自动进行词的切分，以建立合适的符合实际含义的词边界，即自动 分词的切分算法问题。 3 如何进行歧义字段的检测和切分，即自动分词的消歧问题。 4 如何识别新词、人名、地名、机构名等等，即自动分词的宋登录词识别 问题。 分词规范应尽可能同中国国家标准g b l 3 7 1 5 “信息处理用现代汉语分词规 范1 5 ”保持一致，以该规范为参照，北京大学与富士通集团共同制作了1 9 9 8 年 人民日报语料标注语料，是目前世界上最大的汉语标注语料库，并提供了1 个月 人工切分标注后的语料p f r i o f 6 j 免费下载和使用。目前，p f r i 0 已被国内外多 家科研机构、大学和研究所应用。本课题通过解析p f r l 0 得到一个包含了5 6 ，3 8 2 个词条的词典，并应用到基于字符串匹配的书面汉语自动分词算法中。自动分词 算法主要包括基于字符串匹配的分词算法、基于统计的分词算法和基于理解的分 词算法，目前自动分词切分算法的研究仍然是基于上述三类算法的研究。自动分 词消歧问题的研究包括交集型歧义字段消歧研究和组合型歧义字段消歧研究，由 于交集型歧义字段占全部交集型歧义的8 5 以上，因而目前的研究主要集中在 交集型歧义字段的消歧。末登录词的识别技术已经在人名、地名、机构名的识别 方面取得了很大的进展，但对于网络上不断涌现的一些新词，目前仍然没有较好 的解决方法。 1 4 本文主要工作 本文主要研究了作为中文信息处理技术基石的书面汉语自动分词算法及自 动分词所涉及的一些重点和难点问题，如：词典机制、歧义切分、未登录词识别 技术。词典机制研究主要集中在如何有效的组织词典结构，减小查找词典的时间 复杂度、降低空间复杂度等；分词算法研究主要集中在如何有效的提高分词的准 确率和速度；歧义切分研究主要集中在伪歧义型高频最大交集型歧义字段的处 理；未登录词识别技术研究主要集中在基于w e b 查询日志中未登录词的自动识 别，这些问题的探讨和研究将对实现高效的汉语自动分词系统有着重要的实际意 义。为此，本文研究分析了现有的自动分词词典机制、自动分词算法，分析比较 了最大匹配分词算法和最大概率分词算法的性能，给出了一种改进的添加二字词 检测位图表的分词词典机制，在此基础上，设计并实现了基于二字词检测位图表 的最大匹配自动分词算法。同时，实现了基于记忆的伪歧义型高频最大交集型歧 义字段的切分和基于w e b 查询日志挖掘的末登录词识别算法。最后，初步实现 了一个书面汉语自动分词系统。 论文主要工作如下； 1 最大匹配( m a x i m u mm a t c h ) 自动分词算法的改进 在研究分析常用自动分词算法的基础上，重点研究分析了基于词典的最大匹 配( m a x i m u mm a t c h ，以下简称m m ) 自动分词算法，实现了种基于二字词检 测位图表快速判断二字词与匹配词典切分词交叉进行的改进的m m 自动分词算 法，并对改进的分词算法进行了实验测试。 对于改进的m m 自动分词算法，主要包括以下工作： ( 1 ) 研究分析基于词典的最大匹配自动分词算法，并对最大匹配法( m m ) 和最大概率法( m a x i m u mp r o b a b i l i t y ，以下简称m p ) 进行性能评价，在此基础 上，给出在词典匹配的基础上结合概率统计方法的自动分词算法思想。 ( 2 ) 实现了基于二字词检测位图表的最大匹配自动分词算法，本算法利用 二字词检测位图表快速判断二字词，减少词典匹配次数，以提高分词的速度。 ( 3 ) 利用人民日报语料p f r l 0 进行样本测试，实验结果表明，基于二字词 检测位图表的m m 自动分词算法有效地提高了自动分词的速度。 2 自动分词中若干关键问题的研究 本文对自动分词中存在的若干关键问题，如：词典机制、歧义切分及未登录 词识别技术进行了研究分析，主要包括以下工作： ( 1 ) 在研究分析现有自动分词词典机制的基础上，给出了基于二字词检测 位图表的词典机制。本词典机制根据汉语词汇中二字词较多的特点，在词典中增 加二字词检测位图表，以快速判断二字词。 董三矍奎坚堡墼塞耍堡重窒垫坌鎏矍塞 ( 2 ) 据统计，交集型歧义占全部歧义的8 5 以上，因而着重研究了交集型 歧义字段切分。采用双向匹配法检测歧义字段，并记录伪歧义型高频最大交集型 歧义字段的正确切分形式到歧义库中，其歧义消解通过直接查表实现。 ( 3 ) 对未登录词的处理，通过w e b 查询日志挖掘，获得用户搜索关键字频 度表，利用该频度表来识别未登录词。 ( 4 ) 采用查全率r ( r e c a l l ) 与查准率p ( p r e c i s i o n ) 以及f 1 测度对歧义 切分前后得到的分词结果进行比较分析。 3 自动分词系统的设计与实现 在自动分词算法、词典机制、歧义切分、未登录词识别技术研究的基础上， 初步实现了一个书面汉语自动分词系统，主要包括以下工作： ( 1 ) 根据书面汉语自动分词系统的设计原则，采用面向对象的程序设计风 格，设讣了自动分词系统的系统框架及主要功能模块，并实现了一个书面汉语自 动分词系统； ( 2 ) 利用卡耐基梅隆大学的在线分词评估系统，采用查全率r ( r e c a l l ) 与 查准率p ( p r e c i s i o n ) 以及p - 1 测度对自动分词系统进行了性能评价。 1 5 本文组织结构 全文分为五章，主要内容如下： 第一章概述了本文的课题来源、研究目的与意义、研究内容、主要工作以及 组织结构等。第二章为相关研究综述，介绍了汉语自动分词的研究进展，包括自 动分词算法、歧义切分算法、未登录词识剐技术的研究进展。第三章分析比较了 现有词典机制和汉语自动分词算法的优缺点，引入卡耐基梅隆大学的在线评价系 统对其中的m m 和m p 分词算法进行了比较，并根据评价结果，给出词典匹配 结合概率统计的自动分词算法思想。第四章统计了汉语中词汇的分布概率，根据 汉语中二字词较多的特点，提出了一种增加二字词检测位图表的自动分词词典机 制。在此基础上，实现了基于二字词检测位图表快速判断二字词与匹配词典切分 词交叉进行的改进的m m 自动分词算法。针对交集型歧义占全部歧义字段的8 5 以上，重点研究了交集型歧义字段，通过双向匹配法来检测歧义字段，并记录伪 歧义型高频最大交集型歧义字段的正确切分形式到歧义库中，其歧义消解通过直 接查表实现。最后研究未登录诃的识别技术，通过挖掘w c b 查询日志获得用户 搜索关键字频度表，利用该频度表来识别未登录词。第五章初步实现了一个书面 汉语自动分词系统，并利用卡耐基梅隆大学的在线分词评估系统，通过查全率r ( r e c a l l ) 与查准率p ( p r e c i s i o n ) 以及f - 1 测度对整个分词系统进行评价。最 后总结全文。 本文各章的联系与全文的结构如图】。1 所示。 一：茎三塞奎竖里墼耋至坚要! 量2 鎏竺耋 ( 2 ) 据统计，交集型歧义占全部歧义的8 5 以i - ，因而着重研究了交集型 歧义字段切分。采用双向匹配法检测歧义字段，并记录伪歧义型高频最大变集型 歧义字段的正确切分形式到歧义库中，其歧义消解通过直接查表实现。 ( 3 ) 埘未登录词的处理，通过w e b 查询日志挖掘，获得用户搜索关键字频 度表，利用该频度表来识别未登录词。 ( 4 ) 采用查全率r ( r e c a l l ) 与查准率p ( p r e c i s i o n ) 以及f 1 测度对歧义 切分前后得到的分词结果进行比较分析。 3 自动分词系统的设计与实现 在自动分词算法、词典机制、歧义切分、未登录词识别技术研究的基础上， 初步实现丁一个书面汉语自动分词系统主要包括以下工作： ( 1 ) 根据书面汉语自动分词系统的设计原则，采用面向对象的程序设计风 格，设计了自动分词系统的系统框架及主要功能模块，并实现了一个节面汉语自 动分词系统； ( 2 ) 利用卡耐基梅隆大学的在线分词评估系统，采用查全率r ( r e c a l l ) 与 查准率p ( p r e c i s i o n ) 以及f 1 测度对自动分词系统进行了性能评价。 1 5 本文组织结构 全文分为五章，主要内容如下： 第章概述了本文的课题来源，研究目的与意义、研究内容、主要工作以及 组织结构等。第_ = 章为相关研究综述，介绍了汉语自动分词的研究进展，包括自 动分词算法、歧义切分算法、未登录词识别技术的研究进展。第三章分析比较了 现有词典机制和汉语自动分词算法的优缺点，引入卡耐基梅隆大学的在线评价系 统对其中的m m 和m p 分词算法进行了比较，并根据评价结果，给出词典匹配 结合概率统计的自动分词算法思想。第四章统计了汉语中词汇的分布概率，根据 汉语中二字词较多的特点，提出了一种增加二字词检测位图表的自动分词词典机 制。在此基础上，实现了基于二字词检测位闰表快速判断二字词与延配词典切分 词交叉进行的改进的m m 自动分词算法。针对交集型歧义占全部歧义字段的8 5 以上，重点研究了交集型歧义字段，通过双向匹配法来检测歧义字段，并记录伪 歧义型高频最大交集型歧义字段的正确切分形式到歧义库中，其歧义消解通过直 接查表实现。最后研究未登录词的识别技术，通过挖掘w e b 查询日志获得用户 搜索关键字频度表，利用该频度表来识别来登录词。第五章初步实现了一个书两 汉语自动分词系统，井利用卡耐基梅隆大学的在线分词评估系统，通过查全率r ( r e c a i i ) 与奁准率p ( p r e c i s i o n ) 以及f 1 测度对整个分词系统进行评价。最 后总结全文。 本文各章的联系与全文的结构如图1 1 所示。 本文各章的联系与全文的结构如图1 1 所示。 圈i i 全文结构图 5 2 1 自动分词 第2 章相关研究综述 2 1 1 基本概念 汉语自动分词是对汉语文本进行自动分析的第一个步骤。词是最小的、能独 立活动的、有意义的语言成分。计算机的所有语言知识都来自机器词典( 给出词 的各项信息) 、句法规则( 以词类的各种组合方式来描述词的聚合现象) 以及有 关词和句子的语义、语境、语用知识库。汉语信息处理系统只要涉及句法、语义 ( 如信息检索、机器翻译、自动文摘、文本校对等应用) ，就需要以词为基本单 位。 分词体现了汉语与英语的显著的不同。英语文本是小字符集上的已充分分隔 开的词串，而汉语文本是大字符集上的连续字串。把连续的字串分隔成词串，就 是分词系统需要做的工作。可以这样设想汉语自动分词过程的困难：如果把某个 英语文本中的所有空格符都去掉，然后让计算机自动恢复文本中原有的空格符， 这就是词的识别过程，这个过程需要解决的首要问题就是_ 歧义字段的切分闯题。 分词可以由人工完成，也可以由计算机根据事先编好的程序来自动完成。人 工分词工作量大，难以处理大规模语料。计算机自动分词速度快，一致性好，但 是难以运用人工的各种分词知识，一般来说分词结果的准确率要低于人工分词。 现在通常是先由计算机自动分词，然后辅之以人工校对。 无论是人工分词还是计算机自动分词，都需要有一个分词标准或规范，以说 明怎样分词是正确的，这个规范也为中文信息处理的后续工作提供了统一的输 入。不过，即使贯彻了这个规范，分词结果也未必都是正确的。自动分词通常存 在两大难题，一是歧义切分问题，二是未登录词识别问题。 陈力为在文献【7 】中提出，为了从根本上解决分词问题，应该改变汉语的书 写习惯，实行按词连写的输入方式。从历史上看，汉语原来连标点符号也不用， 可见养成新的书写习惯是可能的。张小衡在文献 8 e e 以分词连写的形式撰写论 文，提出书面汉语分词连写的十太好处。不过，这涉及到国家的语言文字政策问 题，即使能够实行，改变书写习惯也需要假以时日。到目前为止，现代汉语书面 语料还是要先经过分词才能做后续分析和处理的。 2 1 。2 分词算法研究现状 汉语自动分词算法的研究最早可追溯到上世纪5 0 年代后期的俄汉机器翻译 时期，大约在1 9 6 0 年左右，苏联学者酋先提出了“6 - 5 4 - 3 - 2 l ”的正向最大 匹配分词方法，它的基本思想是先取一句话的前六个字查字典，若不是个词， - 6 硕士学位论文 = = = = = = = 自= ! = = = ! - - _ ! = ! = | = z = = = ! 一 则删除六个字中的最后一个，然后再查字典，这样一直查找下去直到找到一个词 为止，对句子剩余部分重复此工作，直到把所有词切分出来为止。这种方法中的 匹配思想成为后来许多分词方法的基础。反向最大匹配法和正向最大匹配法思想 一样，不同之处在于它从句子的最后六个字开始切分，每次匹配不成功时，去掉 汉字串最前面的一个字。梁南元首次将这个方法大规模应用到汉语自动分词系统 c d w s 中【9 1 。 揭春雨提出了机械匹配分词方法的形式化描述模型，讨论了基于字符串的机 械匹配分词算法的结构( 最大匹配和最小匹配，正向扫描和反向扫描，增字匹配 和减字匹配) 及其时间复杂度等问题，并指出最大匹配法较为实用【m 】。 从最大匹配法出发导出了“双向最大匹配法”，即f m m + r m m 。s u n m s 和 b e n j a m i nk t 注意到；汉语文本中9 0 0 左右的句子，f m m 和r m m 的切分完 全重合且正确，9 0 左右的句子f m m 和r m m 切分不同，但其中必有一个是 正确的( 歧义检测成功) ，只有不到1 0 的句子，或者f m m 和r m m 的切分 虽重合却是错的，或者f m m 和r m m 切分不同但两个都不对( 歧义检测失败) 】。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所 在。 吴胜远分析了最大匹配法、最小匹配法、逐词遍历法、最佳匹配法，并提出 基于最大匹配的单扫描分词方法，该方法的时间复杂度为2 8 9 ，比当时分词方法 的时间复杂度1 2 3 2 小得多【”j 。黄德根、朱和台等提出了一种基于最长次长匹配 的汉语自动分词算法1 1 3 。陈桂林、王永成等介绍了一种高效的中文电子词典数 据结构，该词典支持首字h a s h 和标准的二分查找，且不限词条长度。然后提出 一种改进的快速分词算法，该算法在快速匹配词典查找二字词的基础上，利用近 邻法匹配方法来查找多字词，明显提高了分词效率1 1 4 1 。李振星等通过对汉字编 码体系、汉语词特点的分析，提出了一种新的词典结构，该词典支持首字h a s h 和完全二分查找，并在此基础上，提出了全二分最大匹配快速分词算法，有效地 提高了分词速度【”】。这些方法都是基于词典匹配来实现自动分词的。 人工智能和专家系统的迅速发展，使得许多人工智能领域的计算手段应用到 书面汉语的自动分词中来，如：专家系统法【1 “、神经网络法1 1 ”、有限状态自动 机法、隐m a r k o v 模型法f 19 1 、b r i l l 式转换法【2 0 】等。这些新的探索体现了自动 分词研究的不同侧面，在一定范围内取得了各自的成效。 为克服知识规则和人工智能方法的弊端，研究人员将概率统计方法应用到书 面汉语自动分词中，该方法是建立一个自动分词的统计模型，获取模型的各种参 数，然后从各种可能的词串中挑选概率最高的词串作为输出结果。 王开铸等介绍了无词典分词法l2 1 1 ，该方法利用统计手段从被切分语料中抽 词，又将所抽取的词汇用于自动分词。这种方法适用于有一定规模的语料库。白 童三苎查彗墼墼耋窑鋈墓窒垫坌望塑塞 栓虎提出将自动分词跟基于m a r k o v 链的词性自动标注相结合的二元语法统计模 型“。l a ib y 和s u nm s 的初步实验表明，同“先做最大匹配分词，再作词性 自动标注”( 词性标注对分词无反馈作用，两者串行) 相比，这种做法的分词精 度和词性标注精度分别提高了1 3 和1 4 1 9 1 。刘挺给出了基于一元模型的最 大概率分词算法【2 ”，其基本思路是从各种可能的词串中，找出各词串概率乘积 最大的词串。韩客松等从知识的自动获取出发，研究了汉语语言的无词典分词模 型1 2 。李家福等根据词的出现概率，提出基于最大似然原则构建的汉语自动分 词系统的零阶马尔科夫模型【2 5 。孙茂松、肖明等探讨了基于无指导学习策略的 无词表条件f 的汉语自动分词方法【2 6 1 。这些方法都是基于概率统计方法来实现 自动分词的。 通过不断的实践，汉语自动分词的发展经历了一个由浅入深，由简单到复杂 的演变过程，其中最大匹配法和最大概率法是最基本的两种自动分词算法，而基 于词典的最大匹配分词算法因开发周期较短，程序实现较为容易，在实际应用领 域中常常被用来预处理分词，然后再利用统计方法切分歧义和识别未登录词。 2 1 3 歧义切分研究现状 歧义的切分是书面汉语自动分词的个难鼹，汉语中歧义切分字段主要有以 下两种类型：一种是交集型歧义字段，在字段a b c 中，设a ，b ，c 分别代表由一 个或多个汉字组成的字串。若a ，a b ，b c ，c 分别都是词表中的词，则称该字段为 交集型歧义字段。另一种是组合型歧义字段，在字段a b c 中，同样设a ，b ，c 分 别代表由一个或多个汉字组成的字串。若a ，b ，a b 分别都是词表中的词，则称 该字段为组合型歧义字段。据统计，交集型歧义字段占全部歧义字段的8 5 以 上，因而交集型歧义字段的切分是分词系统所要重点解决的问题。 何克抗、徐辉等断言，9 5 0 左右的歧义切分可以借助句法以下的知识解 决，只有5 0 必须诉诸语义和语用知识f m 】。 基于规则的几个分词系统都自觉 或不自觉地受到这个结论的支配，歧义消解主要诉诸词法与句法规则。存在的缺 陷是，规则集由人凭主观编制而成，会受到系统性、有效性、一致性、可维护性 等“天然”问题困扰。 白栓虎提出将自动分词与基于m a r k o v 链的词性自动标注相结合的二元语法 统计模型，利用从人工标注语料库中提取出的词性二元统计规律来切分歧义( 词 性标注对分词有反馈作用，两者并行) 【2 孙。孙茂松、左正平等提出了“最大交 集型歧义切分字段”、“真歧义”、“伪歧义”等概念t 对伪歧义型高频交集型歧义 切分，将它们的正确切分形式预先记录在一张表中，其歧义消解通过直接查表即 可实现【2 ”。本质上，这是一个基于记忆的模型。实验证明，这种简单的基于记 忆的处理策略来解决歧义切分问题，取得了比较满意的结果。周昌乐等通过仔细 研究分析汉语分词歧义的规律，将追求整体最优效果的松弛算法引入到汉语自动 分词的排歧研究中，借助于语词之间搭配关系等上下文约束条件以及词频、字频 等统计数据，提出了一种基于语境松弛算法的汉语分词排歧方法【28 1 。郑德权等 提出基于汉语二字应成词的歧义字段切分方法，利用汉语中的二字应成词，计算 汉语旬内相邻字之间的互信息及t 信息差这两个统计信息量，并将计算结果应用 到歧义字段的切分中【2 9 。冯素琴等在对组合型歧义进行深入研究的基础上，提 出一种决策表加学习的排歧算法，该方法具有较强的学习能力，从而获得较高的 排歧正确率【3 0 】。王显芳、杜利民提出了一种能够检测所有交叉歧义的汉语分词 算法【3 ”，该算法基于“长词优先”的切分原则实现，运算复杂度为o ( n ) ，n 为句子长度，它的输出使得下一步处理的运算量大大减少。 2 1 4 未登录词研究现状 由于词典的不完备性，许多词可能不会在词典中登录，因而，在处理句子时， 我们会遇到未登录词，包括人名、地名、机构名、译名和新词等，这些未登录词 也会造成分词错误。在汉语自动分词处理中，未登录词的识别是一个难点。未登 录词大致包含两大类： 1 新涌现的通用词或专业术语等。 2 专有名词，如中国人名、外国译名、地名、机构名( 泛指机关、团体和 其它企事业单位) 等。 前- - e e 未登录词理论上是可预期的，能够人工预先添加到词表中( 但这也只 是理想状态，在真实环境下并不易做到) ；后一种未登录词则完全不可预期，无 论词表多么庞大，也无法囊括。张普等提出“有穷多层列举”的方法来解决双字 未登录词的问题f 3 2 】，该算法只判定单字词和多字词，余下的词一律以二字词处 理，该算法具有较大的片面性。孙茂松、邹嘉彦指出，真实文本中( 即便是大众 通用领域) ，未登录词对分词攘度的影响超过了歧义切分1 3 ”。未登录词处理在实 用型分词系统中占的份量举足轻重。 对第一种未登录词的处理，一般是在太规模语料库的支持下，先由机器根据 某种算法自动生成一张候选词表( 无监督的机器学习策略) ，再人工筛选出其中 的新词并补充到词表中。鉴于经过精加工的千万字、甚至亿字级的汉语分词语料 库目前还无法得到，所以这个方向上现有的研究无一不以从极大规模生语料库中 提炼出的n 元汉字串之分布( n 兰2 ) 为基础。s p r o a tr 和s h i hc l 借用信息论中 的“g t f - g g ”定量描述任意两个汉字之间的结合力i ”】。s u nm s 和s h e n d y 沿这 个思路前进了一步，提出了汉字间t 一测试差的概念作为互信息的有益补充p “ 黄萱菁、吴立德等则引入经典统计论中的“四分联立表”及检验联立表独立性的 皮尔逊x 2 1 一统计量，对长度分别为2 字、3 字和4 字的任意汉字串做内部关联 ：。：一 董王耋奎矍堡墼耋堑望塞! 塑坌璺至塞 性分析，继而获得候选词表【3 6 】。n i ej y 、j i nw y 、刘挺、吴岩等的工作仅利用 了相对简单的字串频信息m 3 8 】。这里提到的几个统计量( 互信息、t 测试差、x f 2 1 一统计量、字串频) 都是依赖于极大规模语料库的，故而称之为全局统计量。 处理第二种未登录词的做法通常是：首先依据从各类专有名词库中总结出的 统计知识( 如姓氏用字及其频度) 和入工归纳出的专有名词的某些结构规则，在 输入句子中猜测可能成为专有名词的汉字串并给出其置信度，之后利用对该类专 有名词有标识意义的紧邻上下文信息( 如称谓) ，以及全局统计量和局部统计量， 进行进一步的鉴定。已有的工作涉及了四种常见的专有名词：中国人名的识别 m 4 ”、外国译名的识别1 4 2 1 、中国地名的识别1 4 3 1 及机构名的识别 4 4 - 4 5 。从各家报 告的实验结果来看，外国译名的识别效果最好，中国人名次之，中国地名再次之， 机构名最差。而任务本身的难度实质上也是循这个顺序由小增大。 张华平提出了基于角色标注的末登录词识别算法【4 “，采用v i t e r b i 算法，确 定句子概率最大的角色序列，在角色序列的基础上，进行模式识别。 2 1 5 主要应用领域 书面汉语自动分词的研究具有重要的理论意义和现