海量新闻信息处理中的中文分词算法研究

点击进入人民网奖学金专题

●2012年度“人民网优秀论文奖”获奖名单揭晓

2012年度“人民网优秀论文奖”获奖名单10月30日揭晓，北京邮电大学计算机学院刘健、于淼同学的作品《海量新闻信息处理中的中文分词算法研究》获得人民网优秀技术课题二等奖，以下是论文全文：

一、研究题目现实意义

人民网作为国际互联网上最大的综合性网络媒体之一，对信息的时效性把控也越来越高。随着WEB 3.0时代的到来，门户网站新闻媒体已经不再是互联网内容的主要来源，SNS平台，微博，博客，论坛，点评网等每天会产生海量内容（UGC），而每日的热点，舆情也蕴含于其中。面对日益增加的海量数据，如何从海量数据中挖掘出热点问题，从而迅速把握热点动态，网络舆情，也成为人民网非常关心以及亟待解决的问题。

为应对互联网的海量数据处理，云计算应运而生。基于现有的云框架，人民网可用现有的网络数据爬取技术将海量互联网数据收集到集群当中，运用云计算技术进行数据的抽取与挖掘。可以说云计算已经基本可以满足海量数据给人民网带来的数据存储以及运算方面的挑战。但是我们知道，分析中文的信息，除了要有良好的数据处理能力，还有一个非常重要的方面就是中文的自然语言处理能力。

我们知道，基于网络舆情监控风险评估系统的算法是基于WEB文本挖掘一些基本的模型与算法：如TF-IDF模型，关联规则的Apriori算法，监督学习中SVM算法等等。然而这些算法能用于中文文本挖掘的先决条件就是有一个良好中文的分词模块，所以中文分词作为风险评估，网络舆情的基础工具，角色十分重要。

众所周知，中文与英文书写方面的最大不同在于，英文以词为单位，而且每个词之间有空格隔开，所以英文分词非常简单。但是中文是以字为单位，词与词之间无空格，所以中文分词要有自己独立的一套方法。

二、社会化新闻中的中文分词算法

当前计算机技术大气候下,技术条件非常成熟。一方面各大门户网站面临激烈的市场竞争，社会和用户对信息获取的准确度和热度的要求日渐严格和苛刻，另外一方面，由于客户业务增长和历史积累所导致的海量业务数据，网络用语、机构简称等新名词不断增加，对分词技术提出了新的挑战。

社会化新闻一直是人民网关注的重点问题，分词技术也成为人民网风险评估系统中的重要组成部分。结合人民网的实际情况，在对新闻等内容的分词当中主要存在以下几点难题：分词歧义问题，未登录词的处理，以及专业分词词典的构建，比如在社会化新闻中经常会出现一些人民或机构名词，如：“王瑜珲任长沙市委组织部副部长”，“湄公河联合执法动态”等，其中“王瑜珲”，“湄公河”这些词可能在我们现有的词库中不存在，很难被切分出来。我们根据以往的研究积累，针对人民网对于社会化海量新闻的分析需求，有针对性的在文中提出了几种分词算法。不仅在原理上做了正确论述，由理论应用到分词算法上也有详细描述。通过研究，我们认为基于隐马尔科夫模型（HMM）的改进模型多重隐马尔科夫模型（CHMM）在分词算法上更为出色，更适合为风险评估系统提供服务。

与此同时，结合人民网风险评估系统，我们认为具有预警意义的词应该是名词动词或者形容词。对于一些代词如：“我们”，助词“的”等可以进行过滤。所以我们的分词模块可以通过词性过滤，来进行关键词提取，使依据词的评估更精确。

不仅如此，风险评估系统中的词多数为新词，我们提供新词添加功能，以便使分词效果更加准确。具体方案将在第六部分论述。

在理论研究的同时，我们对本文提出的多重隐马尔科夫模型算法进行实现，并结合了词性过滤与添加新词的功能，使分词取得了较好的效果，从而使理论结合了实际，为人民网的分词技术的优化提供了可靠的方案。

三、技术难点解析

分析人民网的媒体类型特点和海量社会化新闻的特点以及风险评估系统的需求，我们初步总结出了以下三点亟待解决的分词难题：

3.1交集型歧义：

对字串汉字串AJB，如果满足AJ、JB同时为词(A、J、B分别为汉字串)，那么字串AJB被称作交集型切分歧义。例如：“结婚的与尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，也可以分成“结婚／的／和尚／未／结婚／的”。

3.2组合型歧义：

如果汉字串AB满足A、B、AB同时为词,那么AB被称作组合型切分歧义。例如：“这扇门的把手”中的“把手”就是一个词，“把手抬起来”的“把手”就必须拆开；

3.3未登录词识别：

未登录词往往与其前后的字词交叉组合,不仅增加了自身切分的难度,而且严重地干扰了相邻词的正确切分,从而大大地降低了词法分析乃至整个句子分析的正确率。

在海量社会新闻的文本当中，未登录词问题尤为重要。未登录词主要考虑以下几个方面：中国人名，地名，机构名，缩略语，新词。

所以，我们提出的方案，必须要能较好解决以上问题，并兼顾人民网对于海量社会化新闻的处理以及风险舆情的监测。我们认为基于HMM改进模型算法可以较好的为人民网解决分词技术难题，并为风险评估系统提供优质服务。

四、中文分词算法设计：

中文分词方法可粗略分为两大类:第1类是基于语言学知识的规则方法,如:各种形态的最大匹配、最少切分方法、以及综合了最大匹配和最少切分的N-最短路径方法。第2类是基于大规模语料库的机器学习方法,这是目前应用比较广泛、效果较好的解决方案。用到的统计模型有N元语言模型、信道-噪声模型、最大期望、隐马尔科夫模型等。由于人民网海量新闻种类繁多，而且每日新名词产生量巨大，所以我们认为机械分词配合统计模型方法进行设计，并在其中加入人工干预，用人工与智能相结合的方法，可以达到比较好的效果。

4.1基于字符串匹配的算法

基于字符串匹配的分词方法又称为机械分词方法。它的分词策略简单的说就是将带切分字串与分词词典中的词进行匹配，如果能够在分词词典中找到该字串，则进行切分，否则不予切分。基于字符串匹配的分词方法主要有正向最大匹配算法(Forward MM, FMM)、逆向最大匹配算法(Backward MM, BMM)、双向最大匹配算法（Bi-directional MM）、最小匹配算法（Minimum Matching）。

下面把正向最大匹配法（FMM）作为机械分词法的代表，对其过程详细介绍，流程图如图3-1所示。

1.初始化待切分字串S1,及输出字串S2，S2为空；

2.找出分词词典中最长的词条，并设该词条所含汉字个数为I；

3.取被处理文本当前字符串S1中的I个字作为匹配字段，查找分词词典。若词典中有这样的一个I字词，则匹配成功，将匹配成功的词W赋给S2并在该匹配字段后加一个切分标志，然后继续处理接下来的句子；

4.如果分词词典中查找不到这样的一个I字词，则匹配失败；

5.上步中的匹配字段去掉最后一个汉字，I--；

6.重复步骤3-5，直到能够在词典中进行匹配，并将匹配的字串成功切分；

7.分子切分结束，输出S2。

图4-1

正向最大匹配法的优点就是易于实现而且分词速度也比较快，但是对交叉歧义和组合歧义没有特别好的解决办法，因为它只是根据词典进行机械的切分。经统计，在词典完备，没有任何其他知识的条件下，错误切分率1/169，但是有个完备的词典是不可能实现的，该方法往往不单独使用，而是与其它方法配合使用。

我们可以建立一个特殊规则表来改进机械分词的性能，例如：“会诊”后面接“断”、“疗”、“脉”、“治”时要把“会”要单独切出，这样可以对分词歧义有一定意义上的修正。还可以维护一张不单独成词的字表：如民，伟，尘等。但是维护特殊规则的表的方法会花费大量的人力资源，而起需要不断更新规则，更可能会出现规则的冲突。

4.2基于大规模语料库的统计模型算法研究：

在分词算法的研究中，基于统计的分词方法和机械分词法几乎是交替处于领导地位。时至今日，基于统计的分词方法越来越受到学者的青睐。基于统计的分词发放有两个基本的理论模式。

一、利用汉字之间结合关系的紧密程度来判定那些字符串应该结合成词。这种统计的方法可以在分词过程中脱离对词典的依靠。词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。这种方法的优势是不需词典，对词典已收录的词和未收录的有相似的解法。但也无法有效实现对长于二字的词的延伸处理。

二、模式二的原理是通过计算语料中字符串的分布的强度，包括其重复出现的概率和环境，以此作为该字符串是否应被分成词的一句。简而言之，这种模式在寻找语料中最可能成词的字符串。模式二的优势在于对词典已收录和未收录的词均使用。并且对于同一字符串，在不同的语料中，有着不同的分布强度，自然可以得到不同的分析结果。这样对于歧义字符串完全可以达到理想的有两个或以上分析结果。

我们以二元的Bi-Gram的基本原理为例做说明：对于任意两个词语,，统计在语料库中词语后面恰好是的率P(,)。于是产生一个巨大的二维表。再定义一个句子的划分方案的得分为P(?,)·P(, )·…·P(, )，其中, , …, 依次表示分出的词。利用动态规划求出得分最高的分词方案。

4.2.1隐马尔科夫模型（HMM）

4.2.1.1基本原理论述：

隐马尔可夫模型是在马尔可夫模型的基础上发展而来的，它是为了解决我们观察的事件往往并不是与状态一一对应而只是通过一定的概率分布相联系的问题而提出的。HMM是一个双重随机过程，一个是具有一定状态数的马尔可夫链，这是基本的随机过程，它描述状态的转移；另一个随机过程描述状态和观察值之间的统计对应关系。其中模型的状态转换过程是不可观察的，因而称之为“隐”马尔可夫模型。一个HMM可能用一个五元组来表示，其中：

（1） S代表一组状态的集合，S={}，其中的状态数为N，并用来表示t时刻的状态。

（2） V表示一组可观察符号的集合，V={}，M是从每一个状态可能输出的不同观察值的数目。

（3） A代表状态转移概率矩阵，A={}，其中，，这是个N行N列的矩阵，表示从状态转移到状态的概率。

（4） B表示可观察符号的概率分布，}，表示在状态输出观察符号的概率。

（5） 表示初始状态的概率分布，，其中，它表示在时刻1选择某个状态的概率。

一个确定的隐马尔可夫模型，其状态数和每个状态可能输出的观察值的数目都是可以确定的，因此可以用（A，B，）来表示模型的参数。其中，由，A描述马尔可夫链，产生的输出为状态序列，记为Q，表示第t次转移的源状态；B则描述随机过程，产生的输出为观察值序列，记为O，表示第t次转移的输出。

4.2.1.2基于HMM模型的分词策略：

中文分词的N元统计模型中,将信号源抽象为隐马信号源,也就是采用了二元统计模型。而这时的Markov模型中的状态是我们观察不到的。而对应正确的切分词的序列就是此隐马模型的真实序列,而被分词的文本则是此隐马尔柯夫链的观测值。则在二元统计模型中,中文分词的过程就转化已知隐马模型观测值(文本)求解其真实序列的值(分词结果)。记录Markov信源产生的词的序列C的某个可能分词结果为W=(,…,)，W对应的词的隐状态序列C=(,…,)。我们选择最优的隐状态序列作为我们的分词结果W*:

则W#                               4-1-1

利用贝叶斯公式进行展开，得到

W#

将词类看做状态，词语作为观测值，利用一阶HMM展开，得

W#                   4-1-2

（其中，为句子的开始标记BEG，下同）

为计算方便，常用负对数来计算，则

W#          4-1-3

对W*求解的问题则转化为求此问题的最小值。对于已收入核心词典的词,p(|)=1分词过程中只考虑未录登词的p(|)值。

4.2.2条件随机场模型(CRF)

4.2.2.1  CRF基本原理论述

条件随机场模型（Conditiional Random Fields,CRFs）是一种建立切分和标注序列数据概率模型的框架，它用特征函数的方式综合使用各种互相影响的语言特征，集合了最大熵模型和HMM模型的特点，回避了传统HMM方法处理长距离关联的不足和MEMM等模型中的标注偏置问题。

CRF是一种无向图模型，对于指定的节点输入值，能够计算指定的节点输出值上的条件概率。其训练目标是使得条件概率最大化。线性链是CRF中常见的特定图结构之一，它是由指定的输出节点顺序链接而成。定义,…..,}定义为给定的输入观测序列，即无向图模型中t个输入节点上的值（如一个中文词序列）；定义为一个长度与x相等的状态序列，即无向图中t个输出节点上的值。参数的线性链CRF把给定输入序列x得到的状态序列y的条件概率定义为：

              4-2-1

Z(x)是一个范化因子，使得在给定输入上的所有可能的状态序列的概率之和为1；表示一个特征函数，通常取布尔值，是训练中得到的，与每个特征相关的权重参数，它的取值反映了特征函数所代表的事件发生的可能性。

4.2.2.2.CRF分词策略

一、标记问题解决分词：就是将词语开始和结束的字标记出来，就能对一个句子完成分词，假设使用两个标记B (开始)，E(结束)对句子进行处理，如：“民主是普世价值”，民B主E是B普B世E价B值E, 这样标记明确，分词结果就明确了。

二、如何找到最好的标记结果：知道如何用标记的方式解决分词，那么怎么为一个句子找到一个最好的标记序列呢，CRF为这样的问题提供了一个解决方案，对于输入序列()(对于分词，就是那个句子)，求这个输入序列条件下 某个标记序列()的概率极值。

三、解码过程：

CRF的公式：

                    4-2-2

设使用4标记，B-开始，O-单独成词，M-词语中间的字，E-结束，特征：一元特征，当前字的前一个字，当前字，当前字的后一个字二元特征，各标记间的转移特征。

例如：

民 主 是 普 世 价 值

B BBBBBB

O OOOOOO

M MMMMMM

E EEEEEE

运用Viterbe解码算法，即在以上由标记组成的数组中搜索一条最优的路径。对于每一列的每一个标记，我们都要计算到达该标记的分数，这个分数由三部分组成，它本身的一元特征权重W，它前面一个字标记的路径分数PreScore，前面一个字标记到当前标记转移特征权重TransW。

1. 计算第一列的分数(score),对于，‘民’来说，我们要算 B,O,M,E的Score，因为是第一列，所以PreSocre和TransW都是0，就不用计算，只需要计算自己的一元特征的权重：对于标记，B，我们计算它的Score，记为S1B=B=w(nul民,B)+w(民,B)+w(民,B,主)。

这些特征的意思是：(null，民，B)，当前字为‘民’标记为B，前面一个字为空，(民,B):当前字为‘民’，标记为B，(民,B,主)：当前字为'民'，标记为B，当前字的后一个字为‘主’。特征的权重都是在训练时得到的。对于标记，O，M，E，一样要计算W1O，W1M，W1E,从而得到分数S1O，S1M，S1E。

2.对于第二列，首先要计算是每个标记的一元权重W2BW2O,W2M,W2E对于B，到达该标记的最大分数为：S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E))+W2B其中v(BB)等为B到B的转移特征的权重。这个也是由训练得到的。同样对于第二列的O,M,E也要计算S2O，S2M，S2E。

3.一直计算到最后一列，‘值’字的所有标记，得到S7B，S7O，S7M，S7E.比较这四个值中的最大值，即为最优路径的分数，然后以该值的标记点为始点 回溯得到最优路径。

4.2.3 基于HMM模型的分词算法改进策略：

本文经过调研找到了一种基于多重隐马尔科夫模型（CHMM）的方法,旨在将汉语分词、切分排歧、未登录词识别、词性标注等词法分析任务融合到一个相对统一的理论模型中。

CHMM实际上是若干个层次的简单HMM的组合,各层HMM之间共享一个切分词图作为公共数据结构;每一层隐马尔可夫模型都采用N-Best策略,将产生的最好的若干个结果送到词图中供更高层次的模型使用。

图4-2

首先,在预处理的阶段,采取N-最短路径粗分方法,快速地得到能覆盖歧义的最佳N个粗切分结果；随后,在粗分结果集上,采用低层隐马模型识别出普通无嵌套的人名、地名,并依次采取高层隐马模型识别出嵌套了人名、地名的复杂地名和机构名；然后将识别出的未登录词以科学计算出来的概率加入到基于类的切分隐马模型中,未登录词与歧义均不作为特例,与普通词一起参与各种候选结果的竞争。最后在全局最优的分词结果上进行词性的隐马标注。

原子切分是词法分析的预处理过程,主要任务是将原始字符串切分为分词原子序列·分词原子指的是分词的最小处理单元,在分词过程中,可以组合成词,但内部不能做进一步拆分·分词原子包括单个汉字,标点以及由单字节、字符、数字等组成的非汉字串。如“2012.9人民网蓬勃发展”应切分为:2012.9\人\民\网\蓬\勃\发\展。

在分词歧义问题上我们采取的是N-最短路径的切分排歧策略。其基本思想是在初始阶段保留切分概率P( W)最大的N个结果,作为分词结果的候选集合。在未登录词识别、词性标注等词法分析之后,再通过最终的评价函数,计算出真正最优结果。实际上,N-最短路径方法是最少切分方法和全切分的泛化和综合。

图4-3

在未登录词识别问题上，我们对初始切分得到的各个词按照其在未登录词识别中的作用进行分类,并将词所起的不同作用称为角色。

图4-4

对于一个给定的初始切分结果W=(,),在一个角色集合的范畴内，假定R=()为C的某个角色序列。我们取概率最大的角色序列R#作为最终的角色标注结果。和第3节隐马分词的推导过程类似,我们最终可以得到

R#

R#可以通过Viterbi算法[26]选优得到；

复杂地名和机构名往往嵌套了普通无嵌套的人名、地名等未登录词,如“张自忠路”、“周恩来和邓颖超纪念馆”。对于这种嵌套的未登录词,我们的做法是：在低层的HMM识别过程中,先识别出普通不嵌套的未登录词,然后在此基础上,通过相同的方法采取高层隐马模型,通过角色标注计算出最优的角色序列,在此基础上,进一步识别出嵌套的未登录词。

基于类的隐马分词算法：本算法处于CHMM的第2层，也就是在所有的未登录词识别完成后进行。首先，我们可以把所有的词分类：

其中，核心词典中已有的每个词对应的类就是该词本身。这样假定核心词典中收入的词数为|Dict|，则我们定义的词类总数有：|Dict|+6。给定一个分词原子序列S，S的某个可能分词结果记为,…,，W对应的类别序列记为，同时，我们取概率最大的分词结果W#作为最终的分词结果。则

W#

利用贝叶斯公式进行展开，得到

W#

将词类看做状态，词语作为观测值，利用一阶HMM展开，得

W#

（其中，为句子的开始标记BEG，下同）

为计算方便，常用负对数来计算，则

W#

根据类的定义，如果在核心词典收录，可以得到=，因此，=1。在分词过程中，我们只需考虑未登录词的。在图2中，我们给出了“毛泽东1893年诞生”的二元切分词图。最终所求的分词结果就是从初始节点S到结束节点E的最短路径，这是典型的最短路径问题，可以采取贪心算法，如Dijkstra算法快速求解。

五、方案流程与评估方法

5.1 算法实现流程与改进策略

如5-1图所示，将待处理文档通过多重隐马尔科夫分词模块儿经过，原子切分，未登录词识别及词性标注得到初步的分词结果。再根据分词结果，结合人工审核的方式将应该分到一起的词加入词典，以便优化分词效果。得到初次的分词结果再根据词性过滤模块儿将名词、动词、形容词过滤出来，得到关键词，从而较好滤除噪声。

图5-1

5.2 分词效果评估方案：

我们可以才用人工标注的方法进行样本文本的分词，再用分词器进行切分，然后比对二者差别，从而评估分词器效果。可以借鉴检索系统的评价，具体主要从以下精确度与召回率两个方面来进行评价。

对应于分词系统，主要用到精确度与召回率。其对应含义为：

Tp  分词正确的数量； Fp  分词错误的数量； Fn 未正确分词的句子数量

注：一句话可有多个分词结果。

六、结语

综上所述，在中文分词算法方面基于大规模语料库的统计算法在是现有方法当中表现比较出色的一个。由于中文词法的复杂性，完全依靠计算机智能分词很难实现，所以在智能分词环节引入人工干预，由人来添加新的词汇往往会收到比较好的效果。在人民网的风险评估系统中，分词模块儿作为基础工具意义重大，希望我们能共同探索，发现更好的分词方法。

我们实验室的项目，立足于市场和应用的基础研究，为北京市某政府单位提供了垂直搜索引擎服务，厦门移动的数据挖掘系统也是我们合作的一个方向，其中分词基础都是处于一个基础研究方向。我们期待进一步的合作。