分词技术研究报告

技术报告 报告人：杨超一、 研究内容

目前，国内的每个行业、领域都在飞速发展，这中间产生了大量的中文信息资源，为了能够及时准确的获取最新的信息，中文搜索引擎是必然的产物。中文搜索引擎与西文搜索引擎在实现的机制和原理上大致雷同，但由于汉语本身的特点，必须引入对于中文语言的处理技术，而汉语自动分词技术就是其中很关键的部分。汉语自动分词到底对搜索引擎有多大影响？对于搜索引擎来说，最重要的并不是找到所有结果，最重要的是把最相关的结果排在最前面，这也称为相关度排序。中文分词的准确与否，常常直接影响到对搜索结果的相关度排序。分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求。

研究汉语自动分词算法，对中文搜索引擎的发展具有至关重要的意义。快速准确的汉语自动分词是高效中文搜索引擎的必要前提。本课题研究中文搜索引擎中汉语自动分词系统的设计与实现，从目前中文搜索引擎的发展现状出发，引出中文搜索引擎的关键技术------汉语自动分词系统的设计。首先研究和比较了几种典型的汉语自动分词词典机制，指出各词典机制的优缺点，然后分析和比较了几种主要的汉语自动分词方法，阐述了各种分词方法的技术特点。针对课题的具体应用领域，提出改进词典的数据结构，根据汉语中二字词较多的特点，通过快速判断二字词来优化速度；分析中文搜索引擎下歧义处理和未登陆词处理的技术，提出了适合本课题的自动分词算法，并给出该系统的具体实现。最后对系统从分词速度和分词准确性方面进行了性能评价。本课题的研究将促进中文搜索引擎和汉语自动分词新的发展。

二、汉语自动分词系统的研究现状

1、几个早期的自动分词系统

自80年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系统逐步得以开发，其中几个比较有代表性的自动分词系统在当时产生了较大的影响。

CDWS分词系统是我国第一个实用的自动分词系统，由北京航空航天大学计算机系于１９８３年设计实现，它采用的自动分词方法为最大匹配法，辅助以词尾字构词纠错技术。其分词速度为5-10字/秒，切分精度约为1/625。

ABWS是山西大学计算机系研制的自动分词系统，系统使用 “两次扫描联想-回溯”方法，运用了较多的词法、句法等知识。其切分正确率为98.6%(不包括非常用、未登录的专用名词)，运行速度为48词/分钟。

CASS是北京航空航天大学于1９８８年实现的分词系统。它使用正向增字最大匹配，运用知识库来处理歧义字段。其机械分词速度为200字/秒以上，知识库分词速度150字/秒（没有完全实现）。

书面汉语自动分词专家系统是由北京师范大学现代教育研究所于1991前后研制实现的，它首次将专家系统方法完整地引入到分词技术中。

2、清华大学SEG分词系统

此系统提供了带回溯的正向、反向、双向最大匹配法和全切分-评价切分算法，由用户来选择合适的切分算法。其特点则是带修剪的全切分-评价算法。经过封闭试验，在多遍切分之后，全切分-评价算法的精度可以达到99%左右。

3、清华大学SEGTAG系统

此系统着眼于将各种各类的信息进行综合，以便最大限度地利用这些信息提高切分精度。系统使用有向图来集成各种各样的信息。通过实验，该系统的切分精度基本上可达到99%左右，能够处理未登录词比较密集的文本,切分速度约为30字/秒。

4、国家语委文字所应用句法分析技术的汉语自动分词

此分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分歧义。切词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分可能中选择出合理的切分结果。

5、复旦分词系统

此系统由四个模块构成。一、预处理模块，利用特殊的标记将输入的文本分割成较短的汉字串，这些标记包括标点符号、数字、字母等非汉字符，还包括文本中常见的一些字体、字号等排版信息。二、歧义识别模块，使用正向最小匹配和逆向最大匹配对文本进行双向扫描，如果两种扫描结果相同，则认为切分正确，否则就判别其为歧义字段，需要进行歧义处理；三、歧义字段处理模块，此模块使用构词规则和词频统计信息来进行排歧。最后，此系统还包括一个未登录词识别模块，实验过程中，对中文姓氏的自动辨别达到了70%的准确率。系统对文本中的地名和领域专有词汇也进行了一定的识别。

6、哈工大统计分词系统

此系统能够利用上下文识别大部分生词，解决一部分切分歧义。经测试，此系统的分词错误率为1.5%，速度为236字/秒。

7、杭州大学改进的MM分词系统
系统的词典采用一级首字索引结构，词条中包括了“非连续词”（形如C1…* Cn）。系统精度的实验结果为95%，低于理论值99.73%，但高于通常的MM、RMM、DMM方法。

8、Microsoft Research 汉语句法分析器中的自动分词

微软研究院的自然语言研究所在从90年代初开始开发了一个通用型的多国语言处理平台NLPWin，据报道，NLPWin的语法分析部分使用的是一种双向的Chart Parsing，使用了语法规则并以概率模型作导向，并且将语法和分析器独立开。 实验结果表明，系统可以正确处理85%的歧义切分字段，在Pentium 200 PC上的速度约600-900字/秒。

9、北大计算语言所分词系统

本系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结合的分词系统。系统的分词连同标注的速度在Pentium 133Hz/16MB内存机器上的达到了每秒3千词以上，而在Pentium II/64MB内存机器上速度高达每秒5千词。

三、主要的自动分词算法

现有的分词算法主要可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。

1、 基于字符串匹配的分词方法

这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下；

1正向最大匹配

2逆向最大匹配

3最少切分（使每一句中切出的词数最小）

还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。由于分词是一个智能决策过程，机械分词方法无法解决分词阶段的两大基本问题：歧义切分问题和未登录词识别问题。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。

一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。

另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。

对于机械分词方法，可以建立一个一般的模型，形式地表示为ASM(d,a,m)，即Automatic Segmentation Model。其中，

d：匹配方向，+1表示正向，-1表示逆向；

a：每次匹配失败后增加/减少字串长度（字符数），+1为增字，-1为减字；

m：最大/最小匹配标志，+1为最大匹配，-1为最小匹配。

例如，ASM(+, -, +)就是正向减字最大匹配法（即MM方法），ASM(-, -, +)就是逆向减字最大匹配法(即RMM方法)，等等。对于现代汉语来说，只有m=+1是实用的方法。用这种模型可以对各种方法的复杂度进行比较，假设在词典的匹配过程都使用顺序查找和相同的计首字索引查找方法，则在不记首字索引查找次数（最小为log<汉字总数> » 12~14）和词典读入内存时间的情况下，对于典型的词频分布，减字匹配ASM(d,-,m)的复杂度约为12.3次，增字匹配ASM(d,+,m)的复杂度约为10.6。

2、基于理解的分词方法

通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。

3、基于统计的分词方法

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息为： ，其中 是汉字X、Y的相邻共现概率， 、 分别是X、Y在语料中出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。

在本课题中，采用 基于字符串匹配的分词方法来实现中文搜索引擎下的汉语自动分词系统。

四、 技术方案

1）研究方法：

1、 研究词典的存储方式和数据结构

2、 采用正向/反向最大匹配分词法实现自动分词

3、 对2中两种匹配分词算法的结果不一致的词进行提取，标记为歧义字段

4、 对歧义字段进行消歧处理

5、 对未登陆词进行处理

6、 从分词的准确性和分词速度方面对系统进行评价

7、 设计词典管理模块，完成对词典的更新和维护

8、 针对具体的中文搜索引擎应用背景，对自动分词算法进行改进

2）技术路线：

本项目的研究主要分为四个阶段来实施：

第一阶段：定义词典的数据结构

第二阶段：实现正向/反向最大匹配分词法

第三阶段：实现歧义处理

第四阶段：实现未登陆词处理

3）实验平台：

Windows + VC6.0

4）实验方案：

实验一：建立词典机制，实现词典管理模块

实验二：实现正向/反向最大匹配自动分词算法

实验三：检测并提取歧义字段，实现歧义处理模块

实验四：实现未登陆词处理模块

五、 已完成的工作

目前，已对整个系统的模块设计进行了规划，完成实验一和实验二，实现了词典管

理模块和正向/反向最大匹配自动分词算法。本课题选用1998年1月份人民日报语料进行统计和分析，得到词的统计信息如表1所示。

表1 1998年1月份人民日报语料库中词的统计信息

根据表2对1998年1月份人民日报语料库中词的统计数据，我们得到该语料库中出现的词条数的分布信息如图2(a)所示，词频数的分布信息如图2(b)所示：

以上统计数据表明，在汉语中，二字词占有绝大多数。因此快速判断二字词，对提高自

动分词效率起着至关重要的作用。在实现分词程序时，主要采用快速判断二字词和匹配分词交叉使用技术提高自动分词速度。

对词典的优化主要表现在以下几个方面：分词词典中以同一个词头开始的词是按内码顺序从小到大连续存放在一起的，且不包括首字，这样可以节省存储空间。同时采用内存映射文件技术，词典文件一打开就被映射到内存的某个地址，只有根据词头映射表具体访问某个词头偏移地址的时候，才会读取字典中对应词块的数据，检索时根据词头映射表指针，直接映射到该词头数据存储的文件偏移，再根据词条数目以二分法逐次匹配查找词，这样能提高词典的访问速度。

六、下一步工作展望

将正向/反向最大匹配自动分词算法得到的结果中不一致的地方标记为歧义字段，研究歧义处理算法，同时研究未登陆词处理，最后完成整个分词系统。