（计算机应用技术专业论文）一个基于词典与统计的中文分词算法.pdf

摘要 摘要 本文重点介绍了一个基于字符串匹配与基于统计相结合的中文分词方法，解 决了一定条件下的人名，地名，数量词等未登录词以及交集型歧义和自然语言的 二义性引起的歧义等问题。本文的算法首先对待分词的字符串进行断句( 优先在 待分词的字符串中识别和切分出标点符号，以这些符号作为断点，可将原来的字 符串分解为较小的串再进基于字符串匹配的分词，从而减少匹配的错误率) ，然后 对断句结果运用正向和逆向最大匹配算法依次进行分词处理，再对处理结果进行 比较，如果分词结果不同则表明可能存在歧义，就采用基于统计的方法进行歧义 处理，从而提高了分词的准确率。 本文设计的算法在两个方面进行了改进，首先是在分词词典方面，将原来单 一的词典分为基本词典和特征词词典两个部分。改进了基本分词词典在内存中的 存储结构，根据汉语中两字词的数量最多的特点和哈希索引表查找效率高的特点， 采用了双字哈希索引结构将词典中的词按前两个字为索引关键字进行存储，同时 改进了剩余字串的存储方式，将词剩余字串按词长逆序存放，提高了匹配查找的 速度。在匹配过程中结合特征词词典对歧义进行探测和处理，提高了机械分词的 准确率，大大提高了对姓名、地名和数量词的正确切分率减少这些词所引起的歧 义数量节省了歧义处理时间，提高了分词速度。其次是在统计分词方面的改进， 本算法中利用统计方法处理未登录词和歧义。统计方法的最大缺点就是要求字串 要在待分析的字符串中出现一次以上，所以基于统计的分词方法的分全率和准确 性比较低，针对这一缺点在歧义处理上，我们加入了一些对汉语语言分析所得的 规则，来弥补单纯的统计分词方法的不足。本文采取的歧义处理算法是统计与规 则相结合的复合歧义处理算法，结合了根据大量语料统计所得的若干规则，以及 语言学的一些知识，同时考虑了语言环境在歧义处理上的重要作用。歧义消解结 果比较理想，在一定程度上提高了分词的准确性。 关键词：中文分词，统计分词，正向最大匹配算法，逆向最大匹配算法，哈希表 a b s t r a c t a b s t r a c t i nt h i sp a p e rw ed e s i g nan e wa l g o r i t h m t h i sa l g o r i t h mc o m b i n e st w om e t h o d s ： d i c t i o n a r ym e t h o da n ds t a t i s t i cm e t h o d f i r s t l y , w ed i v i d et h ew h o l et e x ti n t os h o r t e r s e n t e n c e sa c c o r d i n gt ot h ep u n c t u a t i o n si nt h i st e x t s e c o n d l y ，w et a k ep o s i t i v ea n d r e v e r s em a x i m a lm a t c h i n gt os e g a n e n te v e r ys e n t e n c eo ft h i st e x t t h i r d l yw ec o m p a r e t h es e g m e n t a t i o nr e s u l t so ft h e p o s i t i v ea n dr e v e r s em a x i m a lm a t c h i n gt o d e c i d e w h e t h e rt h e r ea r ea m b i g u o u s n e s s e sa n dt h e ni ft h er e s u l t sa r ed i f f e r e n t ，i ti n d i c a t e st h a t t h e r ea r ea m b i g n o u s n e s s e si nt h i sp a r t ，a n dw ee l i m i n a t et h e s ea m b i g u o u s n e s s e sb y u s i n gt h es t a t i s t i cm e t h o da n dr e g u l a t i o n sb a s e do nt h ef o r m e r s r e s e a r c hr e s u l t s d u r i n g t h ep r o c e s sa b o v e ，w eg i v et h eh i g h e rp r i o r i t yt ot h er e s u l t so ft h er e v e r s em a x i m a l m a t c h i n gb e c a u s eo fi t s h i g h e rv e r a c i t y t h i sp a p e ri n c l u d e st w ob e t t e r m e n t s i nt h ef i r s tp l a c e ，w ei n c r e a s et h en u m b e ro f d i c t i o n a r i e s ，w ea d ds o m es p e c i a ld i c t i o n a r i e sw h i c hc a nb eu s e dt oe l i m i n a t et h e a m b i g u o u s n e s s e sa n dr e c o g n i z en e ww o r d sd u r i n gt h es e g m e n t a t i o np r o c e s sb e s i d e st h e b a s i cd i c t i o n a r y a tt h es a m et i m ew er e c o n s t r u c t e dt h ed a t as t r u c t u r eo fb a s i cd i c t i o n a r y i nt h em e m o r yo fc o m p u t e rb yu s i n gd a t as t r u c t u r e h a s h t a b l e ”，w ec h o o s et h ef i r s tt w o s i n g l ec h a r a c t e r so fe v e r yw o r di nt h eb a s i cd i c t i o n a r ya st h ek e y w o r d so ft h em a i na n d s u bh a s h t a b l e s ，t h er e m a n e n tw o r d sa r es t o r e di na na r r a ya c c o r d i n gt ol e n g t h w i t h t h e s ed a t as t r u c t u r e s ，w h e n e v e ro u rp r o g r a mm e e t saw o r d ，t h ep r o g r a mw i l lb ea b l et o l o c a t e t h ew o r ds t r a i 曲t l ya n dq u i c k l yi n d i c t i o n a r y s ot h ec o s to ns c a n n i n gt h e d i c t i o n a r yw i l lb ek n o c k e dd o w nl a r g e l ya n dt h es p e e do fm a t c h i n gw i l lb eq u i c k e du p b yal a r g ed e g r e e i nt h es e c o n dp l a c e ，w ed os o m ei m p r o v e m e n t so nt h em e t h o do f s t a t i s t i c o u ra l g o r i t h mu s e ss t a t i s t i cm e t h o dt os o l v es p e c i a ln o u n s ，n e wc h a r a c t e r sa n d e l i m i n a t ea m b i g u o u s n e s s e s t h eb i g g e s ts h o r t c o m i n go fs t a t i s t i ci st h a ti tn e e d st h a tt h e c h a r a c t e r st ob es o l v e da p p e a ra tl e a s tm o r et h a no n et i m ed u r i n gt h es e g m e n t a t i o n p r o c e s s ，s ot h ev e r a c i t yo fs t a t i s t i ci sn o ts og o o dw h e nt h es e n t e n c ei ss h o r t b e c a u s eo f t h e s er e a s o n s ，w eu s es o m er o l e sg o tf r o ma n a l y s i so fc h i n e s el a n g u a g et or e m e d yt h e s h o r t c o m i n go fs t a t i s t i c b a s e do nt h e s ew a y sa b o v e ，w ed e s i g n e dan e wa l g o r i t h m w h i c hc o m b i n e sl a n g u a g er u l e sa n ds t a t i s t i cr e s u l t st oe l i m i n a t ea m b i g u o u s n e s s e sa n d a b s t r a c r r e c o g n i z en e ww o r d s i ti n c l u d e sm a n yr u l e sb a s e do ns t a t i s t i co fc h i n e s el a n g u a g ea n d s o m ek n o w l e d g eo fl a n g u a g ea n dw ea l s oc o n s i d e rt h ei m p o r t a n ti n f l u e n c eo fl a n g u a g e e n v i r o n m e n ta n dc o n t e x to ne l i m i n a t i n ga m b i g n o u s n e s s e s a f t e ra l lt h e s ea b o v eh a v e b e e nd o n e ，a m b i g u o u s n e s s e sc a nb ee l i m i n a t e de f f e c t i v e l ya n de f f i c i e n t l y , a n dt h e v e r a c i t yo fs e g m e n t a t i o ni si m p r o v e d i ns o m ec o n d i t i o n s k e y w o r d s ：c h i n e s ew o r ds e g m e n t ，p o s i t i v ea n dr e v e r s em a x i m a lm a t c h i n g ，h a s h t a b l e ， s t a t i s t i c ，a m b i g u o u s n e s s i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：张他日期：洳年住月寥日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲签垫靳繇趟 日期：侧年) - f j 扩日 第一章绪论 1 1 中文分词产生的必然性 第一章绪论 我们正处在一个信息革命的时代，随着信息的飞速增长，计算机在人类生活 的各个方面起着越来越大的作用。中文信息处理技术是我国重要的计算机应用技 术，是指用计算机对汉语、汉字的音、形、义等信息进行处理，包括对字、词、 句、篇章的输入、输出、识别、分析、理解、生成等的操作与加工。它是介于语 言学、数学和计算机科学之间的边缘性的交叉学科，同时涉及文科、理科和工科 三大领域。国务院制定的国家中长期科技发展纲领中明确指出：“中文信息处理技 术是高新技术发展的重点。概括地说，中文信息处理可分为字处理平台、词处理 平台和句子处理平台这三个层次。字处理平台的研究与开发，包括汉字编码输入、 汉字识别、汉字系统以及文书处理软件等。其中，汉字输入法的发展和革新，在 中国的计算机普及推广过程中起到了至关重要的作用，并且还对计算机在华夏大 地的本土化应用奠定了必要的基础。汉字输入法经过“万码奔腾”、优胜劣汰的过 程己基本上得到了解决。曾经奔腾的万“码”，现在也基本上只有五笔字型输入和 拼音输入两类。但是，就是为了在屏幕上显示出汉字、提高输入速度，我国的科 学技术人员已经花费了将近2 0 年的心血。这是个重要的开端，是我们走向未来的 坚实的基础。目前字处理技术，都已经比较成熟了，现在的关键是词处理平台以 上的研究。词处理平台上最典型、最引入瞩目的应用领域是面向i n t e r a c t 的中文检 索技术，包括通用搜索引擎、文本自动过滤( 如对网上不健康内容或对国家安全有 危害内容的过滤) 、文本自动分类( 在数字图书馆中应用) 以及个性化服务软件等。 目前我们比较熟悉而且影响比较大的商品化中文通用搜索引擎有：百度、雅虎、 搜狐、新浪等。但这些只用了基于字的全文检索技术，或者仅做了简单的分词处 理，还不是真正意义上的自动检索。对于英文，由于英文中词与词之间是用空格隔 开，检索起来很方便，故计算机采用了词处理的方式，大大减轻了用户与计算机的工 作量；相对来讲，中文的情形就复杂得多。中文的词与词之间是没有分隔符隔开的， 因此若想建立基于词的索引，就需要专门的技术，这种技术被称之为“汉语词语切分 技术”。根据是否采用词语切分技术，中文搜索引擎又可分为基于字的搜索引擎和基 于词的搜索引擎。由于中文信息处理的特殊性和复杂性，中文搜索引擎技术还很不 电子科技大学硕士学位论文 成熟，开发中文搜索引擎决不像西文软件的汉化那样简单。在实现中文搜索引擎时， 不能照搬国外现成的技术，需要对中文的信息处理技术作专门地研究。自然语言理 解领域的应用已经越来越广，但是几乎任何一个基于汉语的系统，都必须经过分词 这一步。自动分词系统是中文信息处理中的一个主要组成部分，是中文自然语言理 解、文献检索、机器翻译及语音合成系统中最基本的一部分。在搜索引擎中，为了 进行中文信息小型化，需要提取关键知识，也就是说首先要分隔出单个的中文词语， 然后进行词频统计得到关键词。要开发中文搜索引擎，快速的汉语分词算法和可靠 的汉化技术是至关重要的。属于这个平台的其他应用还有语音识别、文本自动校 对、汉字简繁体自动转换等。总的说来，字平台研究已取得了初步有成效；句平台 上的研究还很薄弱，离实用还有一段距离。现在的中心任务是词平台上的研究， 中文文本分词在中文信息处理中有着重要的作用。 汉语自动分词是对汉语文本进行自动分析的第一个步骤。此过程的一个主要 问题是对大量歧义现象的处理。词是最小的、能独立活动的、有意义的语言成分。 计算机的所有语言知识都来自机器词典( 给出词的各项信息) 、句法规则( 以词类 的各种组合方式来描述词的聚合现象) 以及有关词和句子的语义、语境、语用知 识库。汉语信息处理系统只要涉及句法、语义( 如检索、翻译、文摘、校对等应用) ， 就需要以词为基本单位。分词以后在词的层面上进行处理，处理的确定性就大大提 高了。在更高一级的文本处理中，例如句法分析、语句理解、自动文摘、自动分 类和机器翻译等，更是少不了词的详细信息。自动分词技术看似简单( 它也的确是 最低层次的语言处理，相对句法分析、语义分析，难度要大大降低1 ，但面临的困 难却很多，其中歧义切分是自动分词技术的最大困难之处。 1 2 中文分词的发展概况及现状 1 2 1 几个早期的自动分词系统 自8 0 年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系统 逐步得以开发，其中几个比较有代表性的分词系统在当时产生了较大的影响 1 4 1 。 c d w s 分词系统是我国第一个实用的自动分词系统，由北京航空航天大学计算 机系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以词尾字构 词纠错技术。其分词速度为5 一l o 字秒，切分精度约为1 6 2 5 ，基本满足了词频统 计和其他一些应用的需要。这是汉语自动分词实践的首次尝试，具有很大的启发 2 第一章绪论 作用和理论意义。 a b w s 是山西大学计算机系研制的自动分词系统，系统使用的分词方法称为” 两次扫描联想一回溯”方法，用联想一回溯来解决引起组合切分歧义。系统词库运用 了较多的词法、句法等知识。其切分正确率为9 8 6 ( 不包括非常用、未登录的专 用名词) ，运行速度为4 8 词分钟。 c a s s 是北京航空航天大学于1 9 8 8 年实现的分词系统。它使用的是一种变形的 最大匹配方法，即正向增字最大匹配。它运用知识库来处理歧义字段。其机械分 词速度为2 0 0 字秒以上，知识库分词速度1 5 0 字秒( 没有完全实现) 。 书面汉语自动分词专家系统是由北京师范大学现代教育研究所于1 9 9 1 前后研制实 现的，它首次将专家系统方法完整地引入到分词技术中。系统使知识库与推理机 保持相对独立，知识库包括常识性知识库( 词条的词类2 4 种、歧义词加标志及其 消除规则编号、消歧的部分语义知识，使用关联网络存储) 和启发性知识库( 消 歧产生式规则集合，用线性表结构存储) ，词典使用首字索引数据结构。通过引入 专家系统的形式，系统把分词过程表示成为知识的推理过程，即句子”分词树”的 生长过程。 1 2 2 中文分词系统的发展 中文计算机分词目前已经成为了中文信息处理学界解决中文文本分词采用的 主要方法，这方面，北京大学计算语言研究所、清华大学、北京工业大学计算机 学院以及北京邮电大学等都取得了突破性的进展，下面简要介绍几个具有代表性 的系统 1 4 ： i ) 清华大学s e g 分词系统 此系统提供了带回溯的正向、反向、双向最大匹配法和全切分一评价切分算法， 由用户来选择合适的切分算法。其特点则是带修剪的全切分一评价算法。系统考虑 到了切分盲点的问题( 某些字串永远不会被某种分词方法匹配出来) ，由此提出 了全切分的概念，即找出输入字串的所有可能的子串，然后利用某种评价方法从 所有这些可能的子串中选出最佳子串序列作为分词结果。为了解决全切分所带来 的组合爆炸问题，又引进了对全切分过程进行修剪的方法，强制性地截止某些全 切分的进行。用户在使用时，对于歧义较少的语料，可采用正向或反向最大匹配 法；对于有较多交叉歧义的语料，可使用双向最大匹配法；对于其它歧义较大的 语料，则采用全切分一评价算法，并需要采用一个合适的评价函数。由于对具体语 3 电子科技大学硕士学位论文 料的统计参数设置了不确切初值，全切分一评价算法在第一、二遍切分过程中的正 确率较低，随着切分的多遍进行，评价函数逐渐得以矫正，系统的切分精度逐步 得以提高。经过封闭试验，在多遍切分之后，全切分一评价算法的精度可以达到9 9 9 6 左右。 2 ) 清华大学s e g t a g 系统 此系统着眼于将各种各类的信息进行综合，以便最大限度地利用这些信息提 高切分精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标志、 预切分模式、其他切分单位。为了实现有限的全切分，系统对词典中的每一个重 要的词都加上了切分标志，即标志“c k ”或“q k ”。“q k ”标志表示该词可进行 绝对切分，不必理会它是否产生切分歧义；“c k ”标志表示该词有组合歧义，系 统将对其进行全切分，即保留其所有可能的切分方式。系统通过这两种标志并使 用几条规则以实现有限的全切分，限制过多的切分和没有必要的搜索。规则包括： 无条件切出q k 类词； 完全切分c k 类词( 保留各个子串) ； 对没有标记( q k 或c k ) 的词，若它与别的词之间存在交叉歧义，则作全切 分；否则将其切出。 为了获得切分结果，系统采用在有向图d a g 上搜索最佳路径的方法，使用一个评 价函数e v a l u a t e ( p a t h ) ，求此评价函数的极大值而获得最佳路径p m a x 。所运用的 搜索算法有两种，即“动态规划”和“全切分搜索+ 叶子评价”，使用了词频、词 类频度、词类共现频度等统计信息。通过实验，该系统的切分精度基本上可达到 9 9 左右，能够处理未登录词比较密集的文本，切分速度约为3 0 字秒。 3 ) 复旦分词系统 此系统由四个模块构成。一、预处理模块，利用特殊的标记将输入的文本分 割成较短的汉字串，这些标记包括标点符号、数字、字母等非汉字符，还包括文 本中常见的一些字体、字号等排版信息。一些特殊的数词短语、时间短语、货币 表示等，由于其结构相对简单，即由数词和特征字构成构成，也在本阶段进行处 理。为此系统特别增加一次独立的扫描过程来识别这些短语，系统维护一张特征 词表，在扫描到特征字以后，即调用这些短语的识别模块，确定这些短语的左、 右边界，然后将其完整地切分开；二、歧义识别模块，使用正向最小匹配和逆向 最大匹配对文本进行双向扫描，如果两种扫描结果相同，则认为切分正确，否则 就判别其为歧义字段，需要进行歧义处理；三、歧义字段处理模块，此模块使用 构词规则和词频统计信息来进行排歧。构词规则包括前缀、后缀、重叠词等构词 4 第一章绪论 情况，以及成语、量词、单字动词切分优先等规则。在使用规则无效的情况下， 使用了词频信息，系统取词频的乘积最大的词串作为最后切分结果：最后，此系 统还包括一个未登录词识别模块，以解决未登录词所造成的分词错误。未登录词 和歧义字段构成了降低分词准确率的两大因素，而未登录词造成的切分错误比歧 义字段更为严重，实际上绝大多数分词错误都是由未登录词所造成的。系统对中 文姓氏进行了自动识别，它利用了中文姓名的用字规律、频率，以及姓名的上下 文等信息。通过对十万以上的中文姓名进行抽样综合统计，建立了姓氏频率表和 名字用字频率表，由此可获得任意相邻的二、三个单字构成姓氏的概率大小和某 些规律，再利用这些字串周围的一些称谓、指界动词和特定模式等具有指示意义 的上下文信息，可对字串是否构成姓名进行辨别。实验过程中，对中文姓氏的自 动辨别达到了7 0 的准确率。系统对文本中的地名和领域专有词汇也进行了一定的 识别。 4 ) 哈工大统计分词系统 该系统是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词匹 配结合起来。系统由三个部分构成：一、预处理模块，利用显式和隐式的切分标 记( 标点符号、数字、a s c i i 字符以及出现频率高、构词能力差的单字词、数词+ 单字常用量词模式) 将待分析的文本切分成短的汉字串，这大大地减少了需要统 计的( 无效) 字串的数量和高频单字或量词边界串；二、串频统计模块，此模块 计算各个已分开的短汉字串中所有长度大于1 的子串在局部上下文中出现的次 数，并根据串频和串长对每个这样的子串进行加权。根据经验，局部上下文中取 为2 0 0 字左右局部上下文的串频计算使用一个滑动窗口( 为一个队列式缓冲区， 保存当前待切分汉字串及其前后2 0 个短串) ，当当前待切分汉字串处理完之后， 窗口下移一个短串( 中心变为相邻下一个短串) 。系统采用一个外散列表来记录 窗口中的短串，以加快窗口中串频计数。散列函数取为汉字的6 b - 8 0 位码( - - 级 汉字共用入口9 5 ) ，每个桶中保存窗口中每一行( 短串) 上的汉字位置：( 短串 的行号，汉字列号) ，并且对于在窗口中出现多次的汉字位置用一个链指针连接 起来，则计算某个字串在窗口中出现的频度时，不必将该字串与窗口中的短串逐 个匹配，而只需统计在该字串中的各个汉字所对应的位置链表中能够相邻的位置 的序列的个数即可。此外，还需要根据词缀集( 前、后缀集合) 对字串的权值进 行提升，例如“处理器”中“处理”的权值很高，但由于对“处理器”的权值作 了提升( 达到或超过了“处理”) ，就不会切成“处理器”如果某个汉字串的 权值超过某一阈值d ( 取为4 0 ) ，则将此汉字串作为一个新识别的词，将其存入 s 电子科技大学硕士学位论文 一临时词库中；三、切分模块，首先用临时词库对每个短的汉字串进行切分，使 用的是逐词遍历算法，再利用一个小型的常用词词典对汉字短串中未切分的子串 进行正向最大匹配分词。对于短汉字串中那些仍未切分的子串，则将所有相邻单 字作为一个权值很低的生词( 例如“玛”、“莉”) 。其中每个模块都对待分析 的文本进行了一次扫描，因而是三遍扫描方法。此系统能够利用上下文识别大部 分生词，解决一部分切分歧义，但是统计分词方法对常用词识别精度差的固有缺 点仍然存在( 例如切出“由来”、“语用”、“对联”等) 。经测试，此系统 的分词错误率为1 5 ，速度为2 3 6 字秒。 5 ) 杭州大学改进的姗分词系统 考虑到汉语的歧义切分字段出现的平均最大概率为1 1 1 0 ，因而机械分词的精 度在理论上能够达到i - 1 1 0 0 = 9 9 1 。那么是否还有更一般、精度更高的机械分词 系统呢? 根据统计，汉语的局部( 词法一级) 歧义字段占了全部歧义的8 4 ，句法 歧义占1 0 ，如果提高系统处理这两类歧义的准确率，则可以大幅度提高切分精度。 这方面的改进导致了改进的姗分词算法。将其阐述如下。 通过对交叉歧义字段的考察，发现其中8 0 以上可以通过运用一条无需任何 语言知识的“归右原则”( 交叉歧义字段优先与其右边的字段成词) 就可以获得 正确切分，这是因为在多数情况下汉语的修饰语在前、中心词在后，因而“归 右”好于“归左”。“归右原则”可以使机械分词的精度上升到9 9 7 0 。这种考 察给出了鼓舞人心的结果，有可能使机械分词系统达到这样的理论精度。 不过“归右原则”还有需要修正的地方，既对于“连续型交叉歧义”会发生 错误，需要补充一条“左部结合”原则：若a b c d e 为连续型交叉歧义字段，“归 右原则”产生切分abcd e ；再由“左结合原则”( 合并最左边的a 、b ) 而得到 a bcd e 。例如“结合成分子”一 “结合成分子”一 “结合成分子”。 但是仍然还有例外，例如“当结合成分子时”一 “当结合成分子时”； 为此引入“跳跃匹配”，在词典中定义“非连续词”( 实际上为串模式) “当幸时”， 然后在切分时首先分出“当结合成分子时”，然后再用“归右+ 左结合”切分中 间的歧义字段。以上3 项技术将机械分词的理论切分精度提高到了9 9 7 3 。 综合以上思想，就建立了如下改进的删分词算法： 正向扫描+ 增字最大匹配( 包括“跳跃匹配非连续词”) + 词尾歧义检查( 逐次去掉首字做删匹配以发现交叉歧义字段) + “归右原则”( 对于“连续型交叉歧义”还需要“左结合原则”) 系统的词典采用一级首字索引结构，词条中包括了“非连续词”( 形如c 1 6 第一章绪论 丰c n ) 。系统精度的实验结果为9 5 ，低于理论值9 9 7 3 ，但高于通常的m m 、r m m 、 d m m 方法。 6 ) 北大计算语言所分词系统 本系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结合 的分词系统。由于将分词和词类标注结合起来，系统可利用丰富的词类信息对分 词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，同时 将基于规则的标注排歧与基于语料库统计模型的排歧结合起来，使规则的普遍性 与灵活性得到统一，而且对未登入词的估算到达了相当高的准确率。系统的处理 过程包括了自动切分和初始词性标记、切分歧义字段识别、组词和标注预处理、 词性标记排歧、切分和词性标注后处理等过程，系统的算法综合了多种数据组织 和搜索技术，以很低的时空开销实现了高速匹配和查找，同时采用了当代计算语 言学的统计方法，运用隐m a r k o v 过程进行词类标注和排歧，对算法的效率和稳固 性都作了尽可能的优化。此系统的一大特色是对通用性的强调，将最稳定、最常 用的4 万6 千余条现代汉语基本词汇( 即将扩充到7 万多条) 及其有关属性组织 成为基本词典，这些词的基本地位都是由汉语语言学家逐一检验认可的，这是本 系统通用性的保证；在此词典的基础上充分利用汉语构词法的研究成果，可以识 别出大部分的常用词。同时系统对用户词典机制作了最大限度的扩展，允许用户 加入3 部到3 0 部以上的自定义词典，并允许用户对这些词典的优先顺序自由排列， 这样就可以用较小规模的多个特殊词典更有针对性地解决具体领域的文本处理。 因此本系统的语言模型实现了通用性与多样性的有效结合，并到达了极高的效率。 1 3 中文分词中的困难 在过去的十几年里，汉语自动分词工作虽然也取得了很大成绩，但无论按照人 的智力标准，还是和实用的需要相比较，差距还很大。我们首先需要对这一困难 的各个方面有充分的认识。 1 3 1 分词的规范 1 3 1 1 汉语词的概念 分词结果是否正确需要有一个通用、权威的分词标准来衡量。分词标准的问 题实际上是汉语词与语素、词与词组的界定问题，这是汉语语法的一个基本、长 7 电子科技大学硕士学位论文 期的问题。它涉及到许多方面：核心词表问题，词的变形结构问题，词缀的问题 和非词语素问题等。 1 3 1 2 对切分规范的要求 汉语自动分词规范必须支持各种不同目标的应用，但不同目标的应用对词的要 求是不同的，甚至是有矛盾的。以下几种系统要求个不相同【2 1 ： 1 ) 以词为单位的键盘输入系统：为了提高输入速度，一些互现频率高的相互邻 接的几个字也常作为输入的单位，如：”这是”、”每一”、”再不”、”不多”、”不在”、” 这就是”、”也就”等。 2 ) 校对系统：校对系统将含有易错字的词和词组作为词单位，如许多人”作”、 ”做”分不清。计算机自动判别时，若把它们当作单字词也不好区分，但在同前后文构 成的词或词组中往往可以有确定的选择，故应把有关的词和词组都收进词库，如”敢 做”、”敢作敢为”、”叫做”、”做出”、”看作”、”做为”等。校对系统要求分词单位较 大。 3 ) 简繁转换系统，干”的繁体形式有”乾”和”斡”，它的简繁转换是非确定的。但 在词和词组的层面上，它的转换常常是确定的。 4 ) 语音合成系统：语音合成系统收集多音字所组成的词和词组作为分词单位， 如”补给”、”给水”，因为在这些词或词组中，多音字”给”的音是确定的。 5 ) 检索系统：检索系统的词库注重术语和专名，并且一些检索系统倾向于分词 单位较小化。分词单位的粒度大小需要考虑到查全率和查准率的矛盾。 1 3 2 分词面临的困难 要将汉语文本的字序列切分成词的序列，即使确定了一个合适的分词标准，要 实现这个标准也还存在算法方面的困难【2 1 。 1 3 2 。1 歧义的切分 汉语文本中含有许多歧义切分字段，典型的歧义有交集型歧义( 约占全部歧 义的8 5 以上) 和组合型歧义。只有向分词系统提供进一步的语法、语义知识才 有可能作出正确的决策。排除歧义常常用词频、词长、词间关系等信息，比如”真正 在”中，”真”作为单字词的频率大大低于”在”作为单字词的频率，即”在”常常单独使用 而”真”作为单字词使用的可能性较小，所以应切成”真正在”。有时切分歧义发生在 - - , j , 段文字中，但为了排除歧义，需要看较长的一段文字。如n 学生会”既可能是一个 b 第一章绪论 名词，指一种学生组织，也可能是”学生，会”，其中”会”为”可能”或”能够”的意思。在” 学生会主席”中只能是前者，在”学生会去”中只能是后者，在”学生会组织义演活动” 中歧义仍然排除不了，则需要看更多的语境信息。 1 3 2 2 未登录词的识别 未登录词即未包括在分词词表中但必须切分出来的词，包括各类专名( ，人名、地 名、企业字号、商标号等) 和某些术语、缩略词、新词等等。”李大海喜欢爱尔肤护 肤液”需要切分成”李大海喜欢爱尔肤护肤液”，并需要识别出”李大海”是人名，”爱 尔肤”是商标名，“护肤液”是术语名词。专名中还包括外族、外国名的汉译名，如”斯 普林菲尔德是伊里诺州首府”，”丹增嘉措7 0 多岁了”，其中的美国地名、藏族人名都 需识别。 未登录词的识别对于各种汉语处理系统不仅有直接的实用意义，而且起到基础 性的作用。因为各种汉语处理系统都需要使用词频等信息，如果自动分词中对未登 录词识别不对，统计到的信息就会有很大误差。比如，一个分词系统若不做中外人名 识别，分词后进行词频统计，可能会发现”张”、”王”、”李”、”刘”、”尔”、”斯”的频率 比”却”、”如”、”你”的频率还要高，用这样的统计结果做汉语处理，其效果肯定有问 题。又比如校对系统，如果系统不具备生词识别能力，就无法判断句子中大部分 词的使用是否合理，也就不能检查真正的错误所在。 1 3 2 3 计算机分词的特点 计算机无法像人那样在阅读汉语文章时一边理解一边分词，而只能是先分词 后理解，因为计算机理解文本的前提是识别出词、获得词的各项信息。这就是逻 辑上的两难：分词要以理解为前提，而理解又是以分词为前提。由于计算机只能 在对输入的文本不理解的条件下进行分词，所以任何分词系统都不可能企求百分 之百的切分正确率。 1 ，4 中文分词系统的目标 中文分词系统的目标是：准确、高效、通用及适用。我们可以从这四个方面 来判断一个汉语自动分词系统是否达到了适应实际信息处理的要求。【1 4 1 9 电子科技大学硕士学位论文 1 4 1 准确性 准确率是分词系统性能的核心指标。现在有些分词系统的准确率达到9 8 ，似 乎已经很高了，其实不然。若这种分词系统被用来支持句法分析、汉夕 机器翻译系 统，假定平均每句话有1 0 个汉语词，那么1 0 句话中会错切2 个词，含有切分错误的2 句就不可能被正确处理。因此仅仅由于分词阶段的准确度不够，语言理解的准确率 就会减少2 0 。可见，分词系统的准确率应达到很高才能基本满足上层使用的要求。 1 4 2 高效性 分词是各种汉语处理应用系统中共同的、基础性的工作，这步工作消耗的时间 应尽量少，应只占上层处理所需时间的一小部分，并应使用户没有等待的感觉，在普 遍使用的平台上大约每秒钟处理1 万字或5 千词以上为宜。 1 4 3 通用性 随着i n t e r n c t 的普遍应用，中文平台的处理能力不能仅限于我国，仅限于字处理， 仅限于日常应用领域。作为各种高层次中文处理的共同基础，自动分词系统必须具 有很好的通用性。同时，系统还应该具有良好的可移植性，能够方便地从一个系统 平台移植到另一个系统平台上而无需很多的修改。当然，完全的通用性很难达到。 1 4 4 适用性 汉语自动分词是手段而不是目的，任何分词系统产生的结果都是为某个具体 的应用服务的。好的分词系统具有良好的适用性，可以方便地集成在各种各样的 汉语信息处理系统中。 1 5 中文分词算法的分类 我们可以将现有的分词算法分为三大类：基于字符串匹配的分词方法、基于 理解的分词方法和基于统计的分词方法。 1 5 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一 个”充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功 1 0 第一章绪论 ( 识别出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆 向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最 短) 匹配：按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与 标注相结合的一体化方法。常用的几种机械分词方法有：正向最大匹配，逆向最 大匹配，最少切分( 使每一句中切出的词数最小) 等，除此之外还可以将上述各 种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来 构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般 很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也 较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最 大匹配的错误率为1 2 4 5 。【1 6 】( 这是因为汉语的语言重心靠后的特点。) 但这种精 度还远远不能满足实际的需要。由于分词是一个智能决策过程，机械分词方法无 法解决分词阶段的两大基本问题：歧义切分问题和未登录词识别问题。实际使用 的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言 信息来进一步提高切分的准确率。一种方法是改进扫描方式，称为特征扫描或标 志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词 作为断点，将原字符串分为较小的串再来迸机械分词，从而减少匹配的错误率。 另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供 帮助，并且在标注过程中又反过来对分词结果进行检验、调整从而极大地提高切 分的准确率。对于机械分词方法，可以建立一个一般的模型，形式地表示为 a s m ( d , a , m ) ，即a u t o m a t i cs e g m e n t a t i o nm o d e l 。其中， d ：匹配方向，+ 1 表示正向，1 表示逆向； a ：每次匹配失败后增加，减少字串长度( 字符数) ，+ 1 为增字，1 为减字； m ：最大最小匹配标志，+ l 为最大匹配，1 为最小匹配。 例如，a s m ( + ，+ ) 就是正向减字最大匹配法( 即m m 方法) ，a s m ( - ，d 就是逆 向减字最大匹配法( 即r m m 方法) ，等等。对于现代汉语来说，只有m = + 1 是实用 的方法。用这种模型可以对各种方法的复杂度进行比较，假设在词典的匹配过程 都使用顺序查找和相同的计首字索引查找方法，则在不记首字索引查找次数( 最 小为l o g = 1 2 1 4 ) 和词典读入内存时间的情况下，对于典型的词频分 布，减字匹配a s m ( d , ，m ) 的复杂度约为1 2 3 次，增字匹配a s m ( d , + ，m ) 的复杂度约 为1 0 6 。另外，还可以证明，早期曾流行一时的”切分标志字串”预处理方法是一个 毫无必要的技术，它增加了一遍扫描”切分标志词典”的时空复杂性，却并没有提高 分词精度，因为所谓的切分标志其实都已经隐含在词典之中，是对词典功能的重 1 1 电子科技大学硕士学位论文 复。实际上”切分标志”也没有标记歧义字段的任何信息。因此，在近来的分词系统 中，已经基本上废弃了这种”切分标志”预处理方法。 1 5 2 基于理解的分词方法 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则 在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部 分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信 息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义 信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需 要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种 语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试 验阶段。 1 5 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息为公式( 1 - 1 ) 所示： p ，l ，y 、 ( 石，l ，) 1 1 0 9 茜董蔷南 公式( 1 - 1 ) 其中e ( x ，】，) 是汉字x 、y 的相邻共现概率，p 皤) 、p o ，) 分别是x 、y 在语料中 出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某 一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组 频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但 这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字 组，例如”这一”、”之一”、”有的”、”我的”、”许多的”等，并且对常用词的识别精 度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典( 常 用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计 和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词 典分词结合上下文识别生词、自动消除歧义的优点。 第一章绪论 1 6 论文组织结构 本文接下来的