分词算法
摘要：中文分词是中文信息处理的重要基础，本文详细阐述了目前主要的几种中文分词算法的技术原理 、中文分词目前的瓶颈和评价准则，以及中文分词的具体应用。
中文分词指将一个汉字序列切分成一个个单独的词。现有的中文分词算法有五大类：基于词典的方法，基于统计的方法，基于规则的方法，基于字标注的方法，基于人工智能技术（基于理解）的方法。中文分词目前主要有四个瓶颈，分别是分词歧义、未登录词识别、分词粒度问题、错别字和谐音字规范化。中文分词有五大评价准则：分词正确率，切分速度，功能完备性，易扩充性和可维护性，可移植性。中文信息处理包括三个层次：词法分析，句法分析，语义分析，其中中文分词是词法分析的第一步，非常重要。中文分词是大部分下游应用的基础，这些下游应用小到POS词性标注、NER命名实体识别，大到自动分类、自动摘要、自动校对、语言模型、机器翻译、搜索引擎、语音合成等等。
一、 中文分词是什么
中文分词是中文信息处理的基本技术，指将一个汉字序列切分成一个个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。
词是最小的能够独立活动的有意义的语言成分，英文单词之间是以空格作为自然分界符的，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记。
二、中文分词的技术原理
2.1 中文分词算法
现有的中文分词算法有五大类：基于词典的分词方法，基于统计的分词方法，基于规则的分词方法，基于字标注的分词方法，基于人工智能技术（基于理解）的分词方法。
图1：中文分词算法总结
2.1.1 基于词典的方法
基于词典的方法：字符串匹配，机械分词方法
原理：按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。
按照扫描方向的不同：正向匹配 & 逆向匹配
按照长度的不同：最大匹配 & 最小匹配
按照是否与词性标注过程相结合：单纯分词方法 & 分词与标注相结合
1.正向最大匹配算法（MM）
步骤
从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数
查找大机器词典并进行匹配，若匹配成功，则将这个匹配字段作为一个词切分出来；若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为信我的匹配字段，进行再次匹配，重复以上过程直到切分出所有词为止
2.邻近匹配算法
邻近匹配算法
对正向最大匹配算法的改进，因为正向正向最大匹配算法对每个不存在的长字符串都要进行一次二分搜索，算法复杂度太高，可以利用同一个首字符下的词条按升序排列这一条件，在找到某个字符串后，在其后增加一个字得到一个新字串，如果新字串在词典中出现，那么新词一定在原字串的后面，且相隔位置不会太远
优点：可以加快匹配进程
3.逆向最大匹配算法（RMM）
逆向最大匹配算法
是正向最大匹配的逆向思维（最大匹配的顺序不是从首字母开始，而是从末尾开始，由右向左），匹配不成功，将匹配字段的最前一个字去掉
优点：逆向最大匹配算法要优于正向最大匹配算法（实践证明）
4.双向最大匹配法(Bi-directction Matching method,BM)
双向最大匹配法：将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。
中文中90.0％左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0％的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0％的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败）。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。
5.最短路径匹配算法（Shortest path match）
最短路径匹配算法
根据词典，找出字串中所有可能的词（也称全分词），然后构造词语切分有向无环图
每一个词对应图中的一条有向边。若赋给相应的边长一个权值（该权值可以是常数，也可以是构成的词的属性值），然后针对该切分图，在起点到终点的所有路径中，求出最短路径，该最短路径上包含的词就是该句子的切分结果
最短路径匹配算法的规则是使切分处理的词数最少，符合汉语自身的语言规律
缺点：在实际应用中，同样不能正确切分出许多不完全符合规则的句子。如果有多条最短路径，往往只能保留其中一个结果，这样对其他同样符合要求的结果不公平，也缺乏理论依据。
6.基于字符串匹配的分词方法的优缺点
优点：简单，易于实现
缺点
匹配速度慢
存在交集型和组合型歧义切分问题
词本身没有一个标准的定义，没有统一标准的词集
不同词典产生的歧义也不同
缺乏自学习的智能性
2.1.2 基于统计的分词（无字典分词）
主要思想
上下文中，相邻的字同时出现的次数越多，就越可能构成一个词。因此字与字相邻出现的概率或频率能较好的反映词的可信度。
可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可以认为此字组可能构成了一个词。该方法又称为无字典分词。
主要统计模型有：N 元文法模型、隐Markov 模型和最大熵模型等。
在实际应用中一般是将其与基于词典的分词方法结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。
1.N-gram模型思想
N-gram模型思想：第n个词的出现只与前面N-1个词相关，而与其它任何词都不相关，整句的概率就是各个词出现概率的乘积 。
2.隐马尔科夫模型（HMM，hiddenMarkov Model）
原理：根据观测值序列找到真正的隐藏状态值序列。
2.1.3 基于规则的分词（基于语义）
原理：通过模拟人对句子的理解，达到识别词的效果，基本思想是语义分析，句法分析，利用句法信息和语义信息对文本进行分词。
优点：自动推理，并完成对未登录词的补充。
语义分词法引入了语义分析，对自然语言自身的语言信息进行更多的处理，如扩充转移网络法、知识分词语义分析法、邻接约束法、综合匹配法、后缀分词法、特征词库法、矩阵约束法、语法分析法等。
扩充转移网络法：以有限状态机概念为基础。有限状态机只能识别正则语言，对有限状态机作的第一次扩充使其具有递归能力，形成递归转移网络 （RTN）。在RTN 中，弧线上的标志不仅可以是终极符（语言中的单词）或非终极符（词类），还可以调用另外的子网络名字分非终极符（如字或字串的成词条件）。这样，计算机在运行某个子网络时，就可以调用另外的子网络，还可以递归调用。词法扩充转移网络的使用， 使分词处理和语言理解的句法处理阶段交互成为可能，并且有效地解决了汉语分词的歧义。
矩阵约束法：其基本思想是先建立一个语法约束矩阵和一个语义约束矩阵， 其中元素分别表明具有某词性的词和具有另一词性的词相邻是否符合语法规则， 属于某语义类的词和属于另一词义类的词相邻是否符合逻辑，机器在切分时以之约束分词结果。
2.1.4 基于字标注的中文分词方法
基于字标注的中文分词方法
实质上是构词方法，即把分词过程视作字在字符串中的标注问题；分词的过程就成为字重组的简单过程
基于规则/统计的分词方法的弊端：一般都依赖于一个事先编制好的词典，而自动分词的过程就是通过词表和相关信息来做出词语切分的决策
本分词法的优点：能够平衡地看待词表词和未登录词的识别问题。因为文本中的词表词和未登录词都是用统一的字标注过程来实现，在学习架构上，既可以不必专门强调词表词信息，也不用专门设计特定的未登录词(如人名、地名、机构名)识别模块。这使得分词系统的设计大大简化。在字标注过程中，所有的字根据预定义的特征进行词位特性的学习，获得一个概率模型。然后，在待分字串上，根据字与字之间的结合紧密程度，得到一个词位的标注结果。最后，根据词位定义直接获得最终的分词结果。
2.1.5 基于人工智能技术的中文分词方法（基于理解）
基于人工智能技术的中文分词方法
原理：在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象
通常包括三个部分： 分词子系统、句法语义子系统和总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程
条件：需要使用大量的语言知识和信息
目前基于理解的分词方法主要有：专家系统分词法，神经网络分词法，神经网络专家系统集成式分词法等
1.神经网络分词算法
神经网络分词算法
原理：以模拟人脑运行，分布处理和简历数值计算模型工作，将分词知识的隐式方法存入神经网内部，通过自学习和训练内部权值，以达到正确的分词结果
算法的分词过程是一个生成分词动态网的过程，该过程是分步进行的：首先以确定待处理语句的权字串为基础，来确定网络处理单元；然后根据链接权重表激活输入/输出单元之间的链接，该过程可以采用某种激活方式，取一个汉字作为关键字，确定其链接表，不断匹配
优点：神经网络分词法具有自学习、自组织功能，可以进行并行、非线性处理，并且反应迅速、对外界变换敏感
缺点：目前的基于神经网络的分词算法存在着网络模型表达复杂，学习算法收敛速度较慢，训练时间长，并且对已有的知识维护更新困难等不足。
2.专家系统分词算法
专家系统分词算法
原理：从模拟人脑功能出发，构造推理网络，将分词过程看做是知识推理过程
该方法将分词所需要的语法、语意以及句法知识从系统的结构和功能上分离处理，将知识的表示、知识库的逻辑结构与维护作为首要考虑的问题。知识库按常识性知识与启发性知识分别进行组织。知识库是专家系统具有“智能”的关键行部件
优点：专家系统分词算法是一种统一的分词算法，不仅使整个分词处理过程简明，也使整个系统的运行效率提高
3.神经网络专家系统集成式分词法
神经网络专家系统集成式分词法
原理：首先启动神经网络进行分词，当神经网络对新出现的词不能给出准确切分时，激活专家系统进行分析判断，依据知识库进行推理，得出初步分析，并启动学习机制对神经网络进行训练
优点：可以较充分发挥神经网络与专家系统二者优势，进一步提高分词效率
2.2 中文分词瓶颈
1.分词歧义
分词歧义：指在一个句子中，一个字串可以有多种不同的切分方法，一个句子经常对应几个合法词序列，因此，汉语分词中的一个重要问题就是在所有这些可能的序列中选出一个正确的结果。
分词歧义是中文分词的主要困难
交集性歧义：可用动态规划来解决
组合型歧义：指同一个子串既可合又可分；可用统计语言模型来解决
eg.“学生会宣传部”中的“学生会”是一个词，“学生会主动完成作业”里的“学生 会”就必须拆开
统计语言模型：对于任意两个词语 w1、 w2 ，统计在语料库中词语 w1 后面恰好是 w2 的概率 P(w1, w2) 。这样便会生成一个很大的二维表。再定义一个句子的划分方案的得分为 P(∅, w1) · P(w1, w2) · … · P(wn-1, wn) ，其中 w1, w2, …, wn 依次表示分出的词。我们同样可以利用动态规划求出得分最高的分词方案。
2.未登录词识别
未登录词识别
未登录词包括：中外人名、中国地名、机构组织名、事件名、货币名、缩略语、派生词、各种专业术语以及在不断发展和约定俗成的一些新词语，是种类繁多，形态组合各异，规模宏大的一个领域。对这些词语的自动辨识，是一件非常困难的事。
中文没有首字母大写，计算机很难分辨人名地名等专有名词
人名刚好与上下文组合成词：比如“高通向人大常委会提交报告”
人名刚好是常用词：比如“汪洋”
品牌名、机构名、地名等专有名词的识别
缩略词的识别
网络新词更难识别：甚至没有固定的生产机制
3.错别字、谐音字规范化
当处理不规范文本（如网络文本和语音转录文本）时，输入的句子中不可避免会存在一些错别字或刻意的谐音字（如香菇—>想哭），这些词对分词系统造成很大干扰。
4.分词粒度问题
对“词语的最小单位”的定义存在主观性，导致多人标注的语料存在大量不一致现象，即表达相同意思的同一字串，在语料中存在不同的切分方式。
2.3 中文分词的评价准则
中文分词主要有五项评价准则：分词正确率，切分速度，功能完备性，易扩充性和可维护性，可移植性。
1.分词正确率
中文分词是中文信息处理的重要基础，因此分词准确性对整体的信息处理任务来说十分重要。
为了获得分词系统切分正确率，应该进行整体测试，歧义测试和专业词测试。自动分词系统的切分正确率的基本公式为：
其中，S1，S2，S3。分别为总体测试、歧义测试和专业词测试的正确率；Bi(i=1，2，3)为三种测试加的权值。
2.切分速度
切分速度对中文信息处理任务也非常重要。比如对于搜索引擎来说，如果分词速度太慢，即使准确性再高，也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。
切分速度
指单位时间内所处理的汉字个数
在分词正确率基本满足要求的情况下，切分速度是另一个很重要的指标，特别对于算法不单一，使用辅助手段， 诸如联想，基于规则，神经网络，专家系统等方法更应注意这一点
通常中文信息处理的文本数量是相当大的，因此必须考虑方法是否能使系统总开销合理。在人机交互方式下处理歧义问题的策略和人机接口的设计，有时会严重影响切分速度，这也是应考虑的因素
3.功能完备性
自动分词方法除了完成分词功能外，还应具备词库增删、修改、查询和批处理等功能。
4.易扩充性和可维护性
易扩充性和可维护性是提供数据存储和计算功能扩充要求的软件属性，包括词库的存储结构，输入/输出形式的变化等方面的扩展和完善。这项指标与系统清晰性、模块性、简 单性、结构性、完备性以及自描述性等软件质量准则有直接的联系，对于研究实验性质的软件是非常重要的，因为这类软件需要不断提高与改进，使之适应中文信息 处理的各种应用。
5.可移植性
可移植性：指方法能从一个计算机系统或环境转移到另一个系统或环境的容易程度。一个好的分词方法不应该只能在一个环境下运行，而应该稍作修改便可在另一种环境下运行，使它更便于推广。
三、中文分词技术的应用
3.1 中文分词是中文信息处理的基础
中文分词是中文信息处理的基础，是自然语言处理的基础模块，中文信息处理包括三个层次：词法分析，句法分析，语义分析。中文分词是词法分析的第一步。
图2：自然语言句子级分析技术
Level1：词法分析 （Lexical Analysis）
词性标注（part-of-speech tag）：为每个词赋予一个类别，如名词、动词、形容词 etc.；一般属于相同词性的词，在句子中承担类似的角色
Level2：句法分析（synactic parsing）：对输入的文本句子进行分析以得到句子的句法结构的处理过程；句法分析的输出结果常作为语义分析的输入
短语结构句法分析（phrase-structure syntactic parsing）：识别出句子中的酸雨结果以及短语间的层次句法关系
依存句法分析（dependency syntactic parsing）：识别句子中词汇与词汇之间的相互依存关系，属于浅层句法分析
深层文法句法分析：利用深层文法，如词汇化树邻接文法、词汇功能文法、组合范畴文法等，对句子进行深层的句法和语义分析
Level3：语义分析（semantic parsing）：理解句子表达的真实语义
语义角色标注（semantic role labeling）：属于浅层语义分析技术
三个层级的联合方式
级联：分词、词性标注、句法分析、语义分析分别训练模型；实际使用时，逐一使用各模块进行分析，最终得到所有结果
联合模型：多任务联合学习和解码，如分词词性联合、词性句法联合、分析词性句法联合、句法语义联合等，联合模型通常可显著提高分析质量（但复杂度高，速度慢）
3.2 具体应用（以搜索引擎为例）
中文分词是大部分下游应用的基础，这些下游应用小到POS词性标注、NER命名实体识别，大到自动分类、自动摘要、自动校对、语言模型、机器翻译、搜索引擎、语音合成等等。
下面以搜索引擎为例，具体阐述中文分词在搜索引擎中的应用。
搜索引擎针对用户提交查询的关键词串进行的查询处理后，根据用户的关键词串用各种匹配方法进行分词。
搜索引擎的查询处理
1.首先到数据库里索引相关信息
若用户提交的字符串不超过3个汉字，则直接去数据库索引
分词：若超过4个字符串，则用分隔符（如空格、标点）把用户提交的字符串分割成N个子查询串
2.再检测用户提供的字符串里有无重复词汇
若有，则丢弃，默认为一个词汇
检查用户提交的字符串有无字母和数字，若有则把字母和数字当做一个词
REFERENCE
中文分词算法基本介绍
中文分词技术介绍-月光博客
中文信息处理发展报告
btw：欢迎关注 ~
Github： HTTPs://github.com/ScarlettYellow
个人博客：https://scarletthuang.cn/
相关阅读
概述在人工智能中，自然语言处理是一门极其深奥的领域，自然语言处理在广义上分为两部分，第一部分自然语言理解，是指让电脑“听懂”人类
百度，作为全球zui大的中文搜索引擎，掌握着一套熟练的中文分词技术，当搜索引擎蜘蛛将网站内容索引后,就会通过中文分词技术将网站信息
随着信息的飞速增长，使搜索引擎成为人们查找信息的首选工具，Google、百度、yahoo、最近新出的网易的有道 等大型搜索引擎一直是人们
搜索引擎在我们的日常生活中已经成为了不可分割的一部分了，相信很多朋友都曾在网上看到类似于“没有了百度我们将面临什么？&rd