（通信与信息系统专业论文）基于局部viterbi算法的中文分词研究与应用.pdf

武汉邮电科学研究院硕+ 论文 摘要 中文分词是中文信息处理领域的基础课题，也是中文信息处理发展的瓶颈 之一，其中对歧义字段的处理是影响分词精度的关键，国内外许多研究人员在这一 领域都进行了深入的研究，但就目前现状来看，仍不能满足实际应用的需要。 本文针对分词中的三个方面词典结构、歧义处理、地名识别进行了深 入的研究。在词典结构方面，通过对词典中各个词语进行统计，最终形成以词首为唯 一索引，与之可能成词的字符有序无重复索引的网格数据结构。通过逐级索引的结构， 可以大大提高遍历词典的速度；在歧义处理方面，对n - b e s t 最优路径和v i t e r b i 算 法的模型进行深入研究并结合本文的具体应用作出相应改进，主要体现在改进了 v i t e r b i 算法对全路径的逐一计算，而是先通过前向最大匹配与逆向最大匹配对待分 词文本进行预处理并获得粗分结果集，其次，利用v i t e r b i 算法对此粗分结果集进行 词频信息统计，降低了算法复杂度并提高了算法效率，同时，根据v i t e r b i 计算出的 最优路径达到了消除歧义的目的；在地名识别方面，由于地名识别依据多个地名词典 进行匹配，因此本文所设计的中文分词系统，在对待分词文本进行粗分处理时，标记 了可能为地名的词语，而不是对所有词语均启动地名识别模块，从而在一定程度上使 得地名处理与分词速率达到一个比较理想的均衡状态； 在系统测试阶段，本文针对普通文本、地名文本、综合文本分别进行了分词正 确率测试与分词速率测试，其中普通文本的分词平均正确率与分词平均速率分别为 9 5 6 和1 2 3 4 6 k s ，地名文本的分词平均正确率与分词平均速率分别为9 2 0 和 7 1 1 8 k s ，综合文本的分词平均正确率与分词平均速率分别为9 2 8 和9 3 5 9 k s 。 通过以上测试结果，可以看出本文对词典结构的设计、消除歧义与地名识别的 研究、以及v i t e r b i 算法应用于局部路径的设计符合预定的分词目标，达到了比较理 想的分词效果。 关键词：中文分词；局部v i m r b i 算法；前向最大匹配；后向最大匹配 武汉邮电科学研究院硕士论文 a b s t r a c t c h i n e s ew o r ds e g m e n t a t i o ni st h ef u n d a m e n t a lt a s ko ft h ec h i n e s ei n f o r m a t i o n p r o c e s s i n g i tb e c o m e so n eo ft h eb o t t l e n e c k si nc h i n e s ei n f o r m a t i o np r o c e s s i n g n l e c h i n e s ew o r dd i s a m b i g u i t yi st h ek e yf a c t o ro fp r e c i s i o no fc h i n e s ew o r ds e g m e n t a t i o n m a n y r e s e a r c h e r sh a v es t u d i e di nt h i sf i e l d b u tc o m et ot h ep r e s e n tc o n d i t i o n , i tc a nn o t s a t i s f yt h ed e m a n do fa p p l i c a t i o n t h i sa r t i c l eh a sd o n ed e e p l yr e s e a r c hi nt h r e ea s p e c t so fc h i n e s ew o r ds e g m e n t a t i o n ： s t r u c t u r eo fd i c t i o n a r ya n dd i s - a m b i g u i t y , r e c o g n i t i o no fp l a c e n a m e a tt h ed i c t i o n a r y s t r u c t u r ea s p e c t ，t h r o u g hc a l c u l a t i n ga n dh a s h i n g ，c o m ei n t ob e i n gah a s h m a pw h i c hi s i n d e x e db yt h ec h a r a c t e ro fe v e r yw o r di nt h ed i c t i o n a r ya n do t h e rc h a r a c t e ri nt h ew o r di s i n d e x e ds i n g l y t h r o u g ht h ed a t as t r u c t u r eo fi n d e x e db yd e g r e e s ，c o u l dr a i s et h es p e e do f w o r d s e e k i n g a tt h ed i s - a m b i g u i t ya s p e c t ，t h r o u g hd e e p l yr e s e a r c h i n gi nn b e s t - p a t h sp a t h a n dv i t e r b ia l g o r i t h m ，t h i sp a p e rh a si m p r o v e dt h e mb a s e do np r a c t i c a l i t y r e c o g n i t i o no f p l a c e n a m em o d u l eb u i l du p o nt h r e ep r o f e s s i o n a lp l a c e n a m ed i c t i o n a r y , s ot h ec h i n e s e w o r ds e g m e n t a t i o ns y s t e mo ft h i sp a p e ru s i n gp l a c es t a r m pi d e n t i f i e rt od e t e r m i n ew h e n a n dh o wt ow a k e nt h ep l a c e n a m er e c o g n i t i o nm o d u l e i nt h ep a r to fs y s t e mt e s t ，t h i sp a p e rh a st e s t e dt h es e g m e n t a t i o ne x a c t i t u d ea n d s e g m e n t a t i o ns p e e do fo r d i n a r yt e x ta n dp l a c e n a m et e x t , c o m p o s i t i v et e x tr e s p e c t i v e l y t h e s e g m e n t a t i o ne x a c t i t u d ea n ds e g m e n t a t i o ns p e e do fo r d i n a r yt e x ta n dp l a c e n a m et e x t , c o m p o s i f i v et e x tr e s p e c t i v e l yi s9 5 6 a n d1 2 3 4 6 k s ，9 2 o a n d7 11 8 k s ，9 2 8 a n d 9 3 5 9 k s t h r o u g ht h et e s t i n gr e s u l t ，s h o u l dp r o v et h a tt h ec h i n e s ew o r ds e g m e n t a t i o ns y s t e mo f t h i sp a p e rh a sa c h i e v e das a t i s f a c t i o n a lr e s u l ti nd i s - a m b i g u i t ya n dr e c o g n i t i o no f p l a c e n a m e k e yw 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 ；s t r u c t u r eo fd i c t i o n a r y ；d i s a m b i g u i t y ；v i t e r b ia l g o r i t h m 1 1研究背景与意义 1 1 1 研究背景 第1 章绪论 随着i n t e m e t 的迅速发展，信息时代己经来临。如何有效、快速、准确的从大量 的信息中找到我们所需要的信息，是摆在我们面前的一个重要和迫切的任务。但对这 些信息进行检索之前，我们还必须要解决分词问题。众所周知，英文是以词为单位的， 词和词之间是靠空格隔开。和英文不同，虽然汉语口语存在音节上的一定变化，形成 了某种程度的界限，但书面上是以连续的汉字串形式出现，没有明显的分词标志。因 此，必须首先对文本进行分词，将汉字串切分为正确的词串，称之为汉语自动分词。 自八十年代初，中文信息处理领域提出自动分词以来，相关方面的众多专家、学 者为之付出了不懈的努力。自动分词研究的全面兴起，取得了一些重要的进展和一些 实用性的成果。 在自动分词研究的初级阶段，对于自动分词的可行性曾出现过一些不同的观点： 一部分研究者认为只要根据汉语词汇的声韵进行匹配即可分词，也有研究者认为使用 m m 算法就能解决自动分词问题；一部分人认为【，自动分词是不可行的；另有一些 观点则对自动分词的必要性和可行性给予肯定，同时也指出了许多难点。显然第一种 观点没有充分估计到自动分词的困难，而第二种观点则过多地考虑了自然语言中的歧 义问题，认为既然连人工都不易做好的事情，计算机更不能完成。 在开始阶段对自动分词的研究主要是进行一些理论上的探讨和作一些定性分析， 同时提出许多自动分词算法，如：m m 方法、r m m 方法、逐词遍历法、基于词频的 统计法等。目前，许多人对歧义产生的原因、歧义的分类进行了研究，并提出了一些 解决歧义的方法。另外，对于中文处理中大量的如姓名、机构名、地名等命名实体的 处理技术也进行了一定的研究。概括地说，可以把这些成果中的分词方法分为两类： 机械分词和理解性分词 2 1 。机械分词，如m m 方法、r m m 方法、基于词频的统计方 法等f 3 】，主要是基于词典、词库的匹配和词的频度统计，这类方法实用、具体，比较 容易实现。理解性分词，其基本思想就是在分词的同时进行句法、语义分析，利用句 1 法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子 系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法 和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法 需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语 言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段 【4 】【5 】 0 汉语自动分词的研究，主要是从词层面进行的研究，这一问题很早就受到了广泛 的关注。目前，许多分词方法己得到了实现。在这一长期的研究和实践过程中，歧义 字段处理和未登录词识别成为困扰我们的主要难题。 尽管有这些难题的困扰，汉语自动分词仍得到很多现实的应用。如在中文文本的 自动检索、过滤、分类，文本的自动校对【6 】，手写汉字识别【7 】等。 1 1 2 研究意义 当代科技革命的主要特征，是以计算机为支持手段进行信息处理。随着计算机的 广泛应用，计算机已由过去的数据处理、信息处理发展到现在的知识处理，对语言文 字的信息处理。而语言是人类最重要的交际工具，是信息最主要的负荷者，人们对语 言文字的处理要求的深度和广度越来越高。在我国，将计算机应用于事务处理、办公 自动化、印刷排版、情报检索、机器翻译、人机对话等方面，都离不开中文，因为所 有这些方面的信息，都是以中文作为其载体的，因而语言文字的信息处理成为我国信 息化建设的“瓶颈”e 9 l 。 中文信息处理技术是重要的计算机应用技术，它已渗透到计算机应用的各个领 域，如计算机网络、数据库技术、软件工程等。国务院制定的国家中长期科技发展纲 领中明确指出：“中文信息处理技术是高新技术发展的重点”。我国软件产业发展的重 点是中文信息处理软件，中文信息处理的发展已经得到国家的重视。因此，解决中文 信息的处理技术成为我国信息化进程中的“必决之役，必胜之战”【lo 】。 据统计，在信息领域中8 0 以上的信息是以语言文字为载体的【1 1 】。这些语言信 息的自动输入和输出，文本的校勘和分类，信息的提取和检索以及语言翻译等语言工 程，都是国民经济和国防信息化建设的重要基础。中文信息处理涵盖了字词、短语、 2 句子、篇章等多层面的信息加工处理任务。中文自动分词是中文信息处理的一项重要 的基础性工作，许多中文信息处理项目中都涉及到分词问题，如机器翻译、自动文摘、 自动分类、中文文献库全文检索等【1 2 】f 1 3 】。中文自动分词也是中文搜索引擎实现所必 须的关键技术之一。词是最小的、能独立活动的、有意义的语言成分。因此，通常的 搜索引擎都是以每一个独立的词为单位建立索引，在查询时按照检索词出现的位置和 频率对文档进行输出。英语文本是小字符集上的已充分分隔开的词串，而汉语文本是 大字符集上的连续字串，并且在词与词之间并没有明显的分割标记。故而存在一个对 汉语中的词加以识别的问题，即中文搜索引擎首先必须对原文进行切分词。如果不分 词，而是按单字来进行检索，则可能检索的结果与用户的查询要求相去甚远【1 4 儿1 5 】。 在八十年代中期，自动分词技术就受到重视，陆续出现各种分词模型和分词软件。 近年来，随着国民经济信息化的不断发展及i n t e r n e t 的普及应用，在中文信息处理的 广泛应用中，迫切要求实现汉语词典和语料库等中文信息的共享和复用，对自动分词 技术的要求趣来越高。在信息产业需求的强大动力推动下，自动分词已经成为中文信 息处理的一个前沿课题【1 6 】【1 7 1 。正如陈力为院士所说【1 8 】“：汉语书面语的分词技术已 经悄悄地形成一门新兴的富有挑战性的学问”。 1 2 国内外研究现状 1 2 1 中文分词的研究现状 ， 汉语自动分词系统的早期研究主要采用基于机械匹配的方法，切分精度比较低。 北京航空航天大学计算机科学与工程系于1 9 8 3 年设计完成了我国第一个实用性的自 动分词系统c d w s 。它采用最大匹配的机械分词方法，辅助以词尾字构词检错技术， 实用知识库进行纠错。随着研究的发展，许多分词系统又增加了规则排歧能力。但是， 由于基于规则的分词系统需要人工提供大量的切分知识，难以满足人们对系统开放性 的要求，暴露出了许多问题。 近年来，国内采用统计方法的分词系统逐渐增多，统计信息也不局限于简单的词 频统计，而是采用词性等层次比较高的信息来校正切分歧义。清华大学人工智能实验 室于9 0 年代末研制的“c s e g & t a g 系统 就是其中之一。它的设计理念是：汉语自动 3 分词与词性标注不应该看作两个孤立的模块，它们之间存在着互馈，这样有利于两者 性能的提高。 十几年来，汉语自动分词系统主要有：早期8 0 年代北航的c d w s 和c w s s 、山 西大学的a b w s 分词系统。9 0 年代至今有：清华大学的一个基于评价的全切分汉语自 动分词系统s e g 、北师大的自动分词专家系统、东北工学院的基于规则的汉语分词 系统、杭州电子工业学院的h d c a w s 系统、中科院计算所i c t c l a s 分词系统。 1 2 2 中文分词的难点 汉语自动分词是进行汉语自然语言处理的基础，但是到目前为止，还有一些难题 困扰我们，最主要的就是歧义字段处理和未登录词识别这两大困难。 汉语分词的一个重要问题是如何从连续字串的汉语句子对应的所有合法可能词 序列中，选出一个正确的结果，即歧义字段处理。歧义切分字段在汉语书面文本中所 占的比例并不大，一些可以通过字段内部的词法特征信息来唯一地判定和正确地切 分，另外一些则需要用到词频、词长、词间关系等信息才能判定和正确地切分【1 9 】。 汉语自动分词算法的另外一个重要问题是未登录词识别问题。我们知道，词表中 不可能囊括所用的词。一方面是因为语言在不断的发展和变化，新词会不断的出现。 另一方面是因为词的衍生现象非常普遍，没有必要把所用的衍生词都收入词典中。未 登录词，也就是那些在字典中没有收录过，但又确实能称为词的那些词。特别是人名、 地名等专有名词，在文本中有非常高的实用频率和比例。而且由于未登录词引入的分 词错误往往比单纯的词表切分歧义还要严重。这就要求分词系统具有一定的未登录词 识别的能力，从而提高分词的正确性。 1 2 2 1 歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如，“表面的 因 为“表面”和“面的”都是词，那么这个短语就可以分成“表i 面的和“表面i 的， 这种称为交叉歧义。像这种交叉歧义十分常见，像“化妆和服装 可以分成“化妆i 和i 服装”或者“化妆i 和服l 装 。由于没有人的知识去理解，计算机很难知道到 底哪个方案正确叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据 4 整个句判断了。例如，在句子“这个门把手坏了 中，“把手”是个词，但在句子“把 手拿开”中，“把手”就不是一个词；在句子“将军任命了一名中将”中，“中将”是 个词，但在句子“产量三年中将增长两倍”中，“中将 就不再是词。 歧义切分是自动分词中不可避免的现象，是自动分词中一个比较棘手的对歧义的 处理严重影响分词的精度。如果只是机械匹配进行分词，其精度不能满足中文信息处 理高标准的要求。 歧义现象一般分为三类：第一类为交集型歧义切分字段，第二类为组合型歧义切 分字段，第三类为混合型歧义切分字段【2 0 1 。 交集型歧义字段：在字段a j b 中，如果a j 属于w 且j b 属于w ，则称a j b 为 交集型歧义字段，其中a 、j 、b 为字串，w 为词表。例如：“中国家庭 中，“中国 家”字段既可划分为“中国家 ，也可以划分为“中国家，因此“中国家是一个 交集型歧义字段。 组合型歧义字段：字段a b 中，a 属于w ，b 属于w 且a b 属于w ，则a b 为 组合型歧义字段。其中a 、b 为字串，w 为词表。例如：“什么是计算机网络 中， “计算机网络”字段可以切分为“计算机网络”，也可只切分成一个词“计算机网络”， 因此它为组合型歧义字段。 混合型歧义，是由交集型歧义和组合型歧义字段自身嵌套或者两者交叉组合而产 生的歧义。如：“城市中心”可以拆分为：“城市中心，“城市中心 和“城市中 心 。 中文分词产生歧义的原因有很多种，但总的来说，主要原因有中文的书写格式、 分词词典的构建不完善、新词汇的出现以及地名产生的歧义现象。 ( 1 ) 书写格式：中文的书写使得词和词之间没有界限标志，一个句子看起来只 是一段字串，这是歧义字段形成的根本原因。如果中文文本也像英文文本那样分词书 写的话，中文信息处理中也就不会有分词问题。 ( 2 ) 词典不完善：词典规模的大小，以及词典的构建是否合理都直接关系到切 分中歧义的产生。如：“北京师范大学政法学院办公室 ，如果词典中含有“院办公室” 和“办公室”两个词语，切分后的结果会有： 北京师范大学政法学院办公室； 5 北京i ) i l i 范大学政法学院办公室： 这就使切分结果产生了歧义。又如：“富阳市中医学会 ，如果词典录“中医学会”， 而只收录了“中医学 一个词语的话。切分结果是：富阳市中医学会。 ( 3 ) 新词汇的出现：随着社会的发展，每年都会有许多新词汇出现，有些词语 是各个领域的最新发展，有些是社会最新变化，它们成为一时的常用词语。如：“互 联网易实现信息交流 中的“互联网”和“网易”这些新词汇使切分结果产生了歧义。 ( 4 ) 地名产生歧义：地名造成的歧义字段，是歧义切分中的一个重要方面。地 名只占很少的一部分，而这很少的一部分就造成了不少的歧义切分。例如： 经济南：经济、济南； 大兴趣：大兴、兴趣； 目前，对地名的研究主要采用首、中、尾字覆盖的方法，但是仍有小部分未能覆盖， 而且一些新地名也在不断的出现，也为排除歧义字段增加了障碍。 解决歧义的常用方法可以分为两类：基于规则的方法和基于统计的方法。基于规 则的方法主要根据句法、语义规则和语法、语义解析进行分词判断。这些规则仅涉及 若干毗邻词之间的线性关系，没有反映句子中各成分之间的层次关系，可靠性不强， 难以建立完整、有效、无矛盾的体系【2 1 1 。基于统计的方法主要有：基于互信息和t - t e s t 的方法【2 2 1 、基于m a r k o v 模型的方法】、基于s v m 和k 心m 结合的汉语交集型歧义 切分方法阴】、基于e m 的方法圆等。 处理混合型歧义目前主要有两种方法：一是增加构词知识，扩大词典。二是增加 临时词典。此外，还可以人工干预分词，人工分词与计算机自动分词结合。在遇到计 算机解决不了的歧义时，借助于人工干预来完成。为了有效地消除歧义字段，还可以 在上述方法的基础上建立分词歧义知识库或规则库。随着计算机技术和汉语语言研究 的发展，汉语自动切分歧义处理将会有更大的突破【2 引。 1 2 2 2 地名识别 目前，国内有关中文姓名识别的研究较多，提出了基于统计和基于语料库的中文姓 名识别方法，达到了很好的识别效果。而中文地名识别相对比较少。主要有：采用统计 模型，利用属性矩阵和频级进行筛选，达到了较高的召回率，但精确率偏低。采用基于语 6 料库的方法，根据地名词典统计分析地名用字的信息以及这些字在真实文本中使用程 度信息进行地名识别，对地名识别取得了一定的效果。基于交换的地名识别方法，得到 地名上下文的规律，对规律再进行筛选，这种方法有效地提高了系统的精确率( 精确率 提高了7 ) 【2 6 】【2 7 1 。 中文地名主要有如下特点障8 】 ( 1 ) 中文地名数量大，没有明确规范的地名定义。并且随着经济和社会的发展， 会有新的地名不断出现。 ( 2 ) 中文地名用词比较自由、分散，同时中文地名用词又有相对集中的覆盖能力。 ( 3 ) 地名结尾经常有地名特征词出现，如“自治区、路、水库”。但地名特征词 出现的情况比较复杂：既可以作为普通用词出现，又可以出现在地名其它位置。 ( 4 ) 地名长度没有严格限制，短的如“京 ，长的如“双江拉祜族佤族布朗族傣族 自治县”。 ( 5 ) 可作单字词的汉字在地名中经常出现，如“西i 直i 门、马l 家i 塔。” ( 6 ) 地名中不同位置可含有多字词，如“龙王i 洞l 山、兵书i 宝剑l 峡 等。 ( 7 ) 地名有时同一些介词、动词、方位词之类的指示词出现，但有些指示词也可 以作为地名组成部分。 ( 8 ) 经常多个地名一起出现，如“i 吉林省l 四平市l 梨树县i 梨 树镇i 霍家店村l 。其中，1 、4 增加了地名识别难度，3 、7 可能使候选地名 产生交叉歧义，2 、5 、6 使部分地名边界模糊，8 则有助于地名识别。 1 3本文研究的目的和内容 1 3 1 本文的研究目的 中文分词发展中，分词正确率提高越来越困难，每提高一点就要付出巨大的代价， 同时，依赖词典的中文分词系统，由于对词典的遍历模式不同，分词速率有明显的不 同，而地名、人名、称谓识别等也是产生歧义的重要因素。 通过研究与分析得知，有词典正向最大匹配与逆向最大匹配虽然分词正确罩有待 提高，但是其分词速率比较理想；而v i t e r b i 算法选取最优路径模型如果直接用于分 7 词系统中，则需要对待分词语句做全分词处理之后选取最优路径，即在目标分词语句 的全分词结果集中依次搜索每一条组合路径，之后按照概率最大的原则选取最优路 径，这种方式虽然可以提高分词正确率，但综合考虑分词速率的影响，则仍需对分词 速率做进一步的改进。 因此，本文希望改进词典的遍历模式，并采取一种综合了双向最大匹配与v i t e r b i 选取最优路径相结合的算法模型，利用有词典支持的快速筛选粗分结果集，同时利用 v i t e r b i 算法分析相关词频信息，对粗分结果集进一步筛选出总词频最大的分词结果作 为最优路径，得出最终的分词结果，本算法的优点是利用正向最大匹配与逆向最大匹 配速度快的优点，缩小了v i t e r b i 算法遍历路径的范围，从而既利用了v i t e r b i 算法在 词频信息提取上的优势，消除歧义，又加快了t e r b 算法的计算速度，最后根据地点 专有词典以及前后地名标志进行分词匹配，实现对地名进行正确切分，以此设计并实 现一套中文分词系统来满足某公司的需要。 1 3 2 本文的研究内容 本文的研究内容如下： ( 1 ) 设计一种快速遍历模式的词典结构基于g r i d 网格的词典结构； ( 2 ) 利用双向扫描正向最大匹配与逆向最大匹配，来确定分词中的歧义字 段； ( 3 ) 通过深入研究v i t e r b i 算法与n b e s t 最优路径算法，针对中文分词中的歧义 字段，利用词频的v i t e r b i 算法选取最优路径的分词方法，进行消除歧义； ( 4 ) 根据地名专有词典，利用前后匹配模式，识别未登录的地名； ( 5 ) 利用样本和一些语料库来证明本文所设计的中文分词系统的可行性。 1 4本章小结 本章论述了中文分词的研究背景、国内外现状，在总结与学习以往中文分词系统 的基础上，提出了本文的研究目的与研究内容。 8 第2 章算法与语言模型 2 1中文分词的基本算法 现有的分词算法主要可分为三大类：基于字符串匹配的分词方法、基于理解的分 词方法和基于统计的分词方法，本文所设计的分词系统是基于字符串匹配与基于统计 的相结合的分词方法。 2 1 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个 “充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功 ( 识别出一个词) 。按照扫描方向的不同，字符串匹配分词方法可以分为正向匹配和逆 向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配； 按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一 体化方法。常用的几种机械分词方法如下： ( 1 ) 正向最大匹配( m m ) 以词典中词条的最大长度是6 为例，它的基本思想是先取一句话的前六个字查词 典，若不是一个词，则删除六个字中的最后一个，然后再查词典，这样一直查下去直 到找到一词为止，对句子剩余部分重复此工作，直到把所有词分出为止。 ( 2 ) 逆向最大匹配( r m ) 这种方法和正向最大匹配法思想一样，不同之处在于它是从句子的最后六个字开 始切分，每次匹配不成功时，去掉汉字串前面的一个字。反向最大匹配法对交集型歧 义字段处理精度比正向最大匹配法略高。 ( 3 ) 最少切分( 使每一句中切出的词数最小) 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹 配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最 小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义 现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆 9 向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。由于分词是 一个智能决策过程，机械分词方法无法解决分词阶段的两大基本问题：歧义切分问题 和未登录词识别问题。实际使用的分词系统，都是把机械分词作为一种初分手段，还 需通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识 别和切分出一些带有明显特征的词，以这些词作为端点，可将原字符串分为较小的串 再来进行机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起 来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结 果进行检验、调整，从而极大地提高切分的准确率。 对于机械分词方法，可以建立一个一般的模型，形式地表示为a s m ( d ，钆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 ：匹配方向，+ l 表示正向，1 表示逆向； a ：每次匹配失败后增加减少字串长度( 字符数) ，+ l 为增字，1 为减字； m ：最大最小匹配标志，+ l 为最大匹配，1 为最小匹配； 例如，a s m ( + ，- ，+ ) 就是正向减字最大匹配法( 即m m 方法) ，a s m ( - ，- ，+ ) 就是逆向 减字最大匹配法( i ir m i v i 方法) ，等等。对于现代汉语来说，只有m ：+ l 是实用的方 法。用这种模型可以对各种方法的复杂度进行比较，假设在词典的匹配过程都使用顺 序查找和相同的计首字索引查找方法，则在不记首字索引查找次数和词典读入内存时 间的情况下，对于典型的词频分布，减字匹配a s m ( d ，m ) 的复杂度约为1 2 3 次，增 字匹配a s m ( d ，+ ，m ) 的复杂度约为1 0 6 。 2 1 2 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数 越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成 词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互 现信息。定义两个字的互现信息为：m ( ) ( ，y ) = l o g p ( x ，y ) p ( x ) p ( y ) ，其中p ( x ，是汉字 x 0y 的相邻共现概率，p ( x ) 、p ( y ) 分别是x 、y 在语料中出现的概率。互现信息体 现了汉字之间结合关系的紧密程度。当紧密程度高于某一个闭值时，便可认为此字组 l o 可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典， 因而又叫做无词典分词法或统计取词方法。 但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用 字组，例如“这一 、“之一”、“有的”、“我的”、“许多的 等，并且对常用词的识别 精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典( 常用 词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹 配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合 上下文识别生词、自动消除歧义的优点。 2 1 3 基于理解的分词方法 通常的分词系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在后 续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。其基 本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义 现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分 的协调下，分词子系统可以获得有关词、句子等句法和语义信息来对分词歧义进行判 断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。 由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形 式，因此目前基于理解的分词系统还处在试验阶段。 2 2 语言模型 语言模型是描述自然语言内在规律的数学模型。常见的语言模型主要有基于文法 的语言模型和基于分布理论的语言模型【5 1 。基于分布理论的语言模型通常是概率模 型，计算机借助于统计语言模型的概率参数，可以估计出自然语言中每个句子出现的 可能性，而不是简单地判断该句子是否符合文法。这种语言模型通过对语料库进行深 层加工、统计和学习，获取自然语言文本中的语言知识，从而客观地描述大规模真实 文本中细微的语言现象。本文采用的主要是基于分布理论、利用v i t e r b i 算法与n b e s t 最优路径的综合语言模型，具体描述如下。 2 2 1v i t e r bi 算法模型 v i t e r b i 算法即是当给定模型入( a ，b ，丌) 以及观察序列q 时，关于如何选取相应 的在某种意义上为最佳的状态序列q 宰的问题，其中a = a i j ) ：状态转移概率分布。兀 = i ) ：初始状态概率分布。绚：表示t 时刻为状态s i ，而时刻t + 1 的状态转移到s j 的概率分布，b = b j ( k ) ) ：观察符号的概率分布，b j ( k ) ：表示在状态s j 时，输出某一 观察符号的概率。 根据选择的判据的不同，该问题的解法可以有许多种。最广泛应用的判据为寻 找单个最佳状态序列q 掌，亦即使p ( q l q ，入) 最大。 假设一段中文句子a 由八个汉字a ，b ，c ，d ，e ，f ，g ，h 依次构成，记为集合 s = a ，b ，c ，d ，e ，f ，g ，h ，其全分词结果集记为s 。= a ，b c ，c d ，e f ，e f g ，g h ) ，由此 可见，s 中存在交集歧义词汇b c 、c d 以及e f g 、g h ，同时含有e f 、e f g 歧义词汇，s 。 的词频集合记为p t = p b 。，p c 。，p mp 啦，p 曲 ，其中单字未组成词的词频均记为零。正向最 大匹配与逆向最大匹配的分词结果分别记为：s = a b c ，d ，e f g ，h ) ，s l 洲= a b ，c e ，e l , g h ，则观察序列q 即为s ，可能的状态序列集合为 s 删，s l 洲 ，并分别记概 率如下： p = ( s m m i q ，入) = p 。+ p b 。+ p d + p 。地+ p h = p b c + p 。f g ， p a m m = ( s r m m q ，入) = p 。+ p b + p c d + p 。f + p g l i = p o d + p 。f + p g h ， 在词典中可以分别检索到各个词汇的词频信息，为组成词的单个字的词频记为 零，则可以分别计算出p m m 和p r i m 的值，若p m m p r i m ，则q 幸= p 删；否则，q = p r i m 。q * 1 0 为p 为最大概率时的最佳状态序和最终的分词结果。 2 2 2n - b e s t 最优路径模型 n b e s t 最有路径模型的基本思想【2 9 1 是根据词典，找出字串中所有可能的词，构 造词语切分有向无环图。每个词对应图中的一条有向边，并赋给相应的边长( 权值) 。 然后针对该切分图，在起点到终点的所有路径中，求出长度值按严格升序排列( 任何 两个不同位置上的值一定不等，下同) 依次为第1 ，第2 ，第i ，第n 的路径 集合作为相应的粗分结果集。如果两条或两条以上路径长度相等，那么他们的长度并 1 2 列第i ，都要列入粗分结果集，而且不影响其他路径的排列序号，最后的粗分结果集 合大小大于或等于n 。 设待分字串s = c l ，c 2 ，c 1 1 ，其中c i ( i = l ，, - - - , n ) 为单个的字，n 为串的长度，n o 。 建立一个节点数为n + l 的切分有向无环图g ，各节点编号依次为v o ，v i ，v 2 ， v n ，通过以下两种方法建立g 所有可能的词边：相邻节点v k - l ，v k 之间建立有向边 ，边的长度值为l k ，边对应的词默认为c k ( k = l ，2 ，n ) ；若w = c i ，c i + 1 ，c j 是一个词，则节点v i 1 ，v i 之间建立有向边， ，边的长度值为l w ，边对应的 词为w ( 0 l 勺 n ) ；这样，待分字串s 中包含的所有词与切分有向无环图g 中的边一 一对应。 2 3本文采用的算法模型 通过研究与分析得知，有词典正向最大匹配与逆向最大匹配虽然分词正确里有待 提高，但是其分词速率比较理想；而v i t e r b i 算法选取最优路径模型如果直接用于分 词系统中，则需要对待分词语句做全分词处理之后选取最优路径，即在目标分词语句 的全分词结果集中依次搜索每一条组合路径，之后按照概率最大的原则选取最优路 径，这种方式虽然可以提高分词正确率，但综合考虑分词速率的影响，则仍需对分词 速率做进一步的改进，因此，本文采取的是一种综合了双向最大匹配与v i t e r b i 选取 最优路径相结合的算法模型，即利用有词典支持的快速筛选粗分结果集，利用v i t e r b i 算法依据词典中的相关词频信息，对粗分结果集进一步筛选出总词频最大的分词结果 作为最优路径，得出最终的分词结构，本算法的优点是利用正向最大匹配与逆向最大 匹配速度快的优点，缩小了v i t e r b i 算法遍历路径的范围，从而既利用了v i t e r b i 算法 在词频信息提取上的优势，消除歧义，又加快了v i t e r b 算法的计算速度，分词效果比 较理想，本文第4 章做了详细的测试。 例如，对目标语句“南京市长主持人代会 进行分词，依据词典进行全分词处理 的时，需要对集合 南京、南京市、市长、主持、主持人、人代会、南、京、市、长、 主、持、人、代、会 这些单个词或字按照顺序以任意组合的方式进行排列，根据排 列组合公式可知其全分词排列的组合方式将有很多种，例如，可以有以下几种排列方 式：“南京i 市长i 主持1 人代会 ，“南京市i 长f 主持人i 代l 会 ，“南京 1 3 l 市长i 主持人l 代l 会”，“南京l 市l 长l 主持1 人代会”等。前两种分别 为逆向最大匹配与正向最大匹配的排列组合，可以看出，正确结果即为第一种组合方 式，而后两种排列方式与正确结果相差甚远，依据已有中文分词理论可以得知，其中 多数组合方式对消除歧义没有实质作用，一般情况下，在正向最大匹配与逆向最大匹 配分词结果中已包含正确的分词结果，可以根据v i t e r b i 算法，仅对双向扫描的结果 进行概率筛选，找到最优路径即可得到分词结果，如图2 1 所示： 南京市长主持人代会 图2 1v i t e r b i 路径图 长i 主持人i 代i 会 首 图2 1 中，横坐标和纵坐标分别表示词首与词尾，s t a r t 与e n d 分别为分词路径 的起点位置与终点位置，a _ b - c - d 为逆向最大匹配结果曲线，a 卜刊为正 向最大匹配结果曲线，横线即为组成词的位置，从图中可以看出，a b c d 分别 组成词“南京 、“市长 、“主持 、“人代会”，依据词典可以得出词频分别 为1 4 6 8 、1 4 4 2 、1 4 6 1 、1 3 5 7 ，总词频为5 7 2 8 ，而a 卜刊仅组成了两个词， 分别为“南京市 、“主持人 ，其词频分别为1 4 5 8 、1 4 7 7 ，因此其总词频为2 9 3 5 ， 根据v i t e r b i 算法选取频率最大路径的思想，选取a 川- - - c d 为最优路径，即逆向 1 4 最大匹配为最终的分词结果，可以看出，此结果正确的。 2 4本章小结 本章论述了中文分词中常用的算法以及语言模型，在充分学习与研究上述算法与 语言模型的基础上，提出了本文中文分词系统所采取的算法模型，即综合利用双向匹 配的、基于统计与v i t e r b i 最短路径的分词模型。 1 5 3 1系统设计 3 1 1 设计思想 第3 章系统设计与实现 本文系统的主要设计思路是首先根据标记对中文语料进行预处理，按照标点符号 等标记将语料进行粗分处理；其次，依据g r i d 词典网格，对语料粗分结果进行双向 扫描最大匹配分词处理，获取歧义字段区间并记录其相应的词频信息；最后，对歧义 字段进行语言模型的匹配，利用v i t e r b i 算法与n b e s t 最优路径消除歧义，得到最终 分词结果。 3 1 2 开发平台 本系统是基于e c l i p s e 开发平台，使用j a v a 语言进行开发，因此具有j a v f l 跨平台 的优点，同时使用了j f l v as w i n g 技术，图形化显示效果也很理想。 3 1 3 系统总流程图 本文所设计的中文分词系统是基于词典支持、正向与逆向匹配相结合、并使用 v i t e r b i 算法过滤歧义词汇的最大匹配模式，具体流程图如图3 1 所示： 1 6 图3 1 系统总流程图 图3 1 中，首先将待切分文档按照一定标准进行分词的前端处理，例如根据标 点符号对文本进行标记、删除多余的空格以及标点等，其次将前端处理的输出结果根 据标记进行分组，即形成了待分词文本的数组结构，等待分词；另一方面，为了提高 每次遍历词典的速度，首先将原始词典根据一定模式进行初始化，形成多个根节点的 词典树，作为分词处理的词典支持；分词处理是歧义识别与地名识别的综合处理，歧 义识别使用正向最大匹配与逆向最大匹配同时进行，并使用v i t e r b i 算法对歧义词汇 进行再处理；另外，如果歧义识别遇到地名时，将启用地名识别模块，之后将地名处 理结果与歧义识别结果进行综合，加入最终分词处理结果中，完成一次分词处理；如 此循环处理直到文本末尾，则分词结束，完成对整个文本的分词处理。 对于词典结构、歧义识别和地名识别，将在本文3 2 3 4 小节中作详细介绍。 1 7 3 2词典结构 3 2 1词典概述 分词词典是汉语信息处理系统的一个重要基础部分，