分词算法,分词算法有哪些

自然语言处理（NLP）的基础难点：分词算法

自然语言处理（NLP，Natural Language Processing）是人工智能领域中的一个重要方向，主要研究人与计算机之间用自然语言进行有效通信的各种理论和方法。自然语言处理的底层任务由易到难大致可以分为词法分析、句法分析和语义分析。分词是词法分析（还包括词性标注和命名实体识别）中最基本的任务，也是众多NLP算法中必不可少的第一步，其切分准确与否往往与整体结果息息相关。

金融领域分词的难点

分词既简单又复杂。简单是因为分词的算法研究已经很成熟了，大部分的算法（如HMM分词、CRF分词）准确率都可以达到95%以上；复杂则是因为剩下的5%很难有突破，主要可以归结于三点：

▲粒度，即切分时的最小单位，不同应用对粒度的要求不一样，比如“融资融券”可以是一个词也可以是两个词

▲歧义，比如“恒生”一词，既可指恒生公司，又可指恒生指数

▲未登录词，即未出现在算法使用的词典中的词，比如不常见的专业金融术语，以及各种上市公司的名称

在金融领域中，分词也具有上述三个难点，并且在未登录词方面的难点更为突出，这是因为金融类词汇本来就多，再加上一些专有名词不仅有全称还有简称，这就进一步增大了难度。

在实际应用中，以上难点时常会造成分词效果欠佳，进而影响之后的任务。尤其是在一些金融业务中，有许多需要与用户交互的场景，某些用户会用口语化的词汇描述业务，如果分词错误会影响用户意图的解析，这对分词的准确性提出了更高的要求。因此在进行NLP上层应用开发时，需要对分词算法有一定的了解，从而在效果优化时有能力对分词器进行调整。接下来，我们介绍几种常用的分词算法及其应用在金融中的优劣。

几种常见的分词算法

分词算法根据其核心思想主要分为两种：

第一种是基于字典的分词，先把句子按照字典切分成词，再寻找词的最佳组合方式，包括最大匹配分词算法、最短路径分词算法、基于N-Gram model的分词算法等；

第二种是基于字的分词，即由字构词，先把句子分成一个个字，再将字组合成词，寻找最优的切分策略，同时也可以转化成序列标注问题，包括生成式模型分词算法、判别式模型分词算法、神经网络分词算法等。

最大匹配分词寻找最优组合的方式是将匹配到的最长词组合在一起，主要的思路是先将词典构造成一棵Trie树（也称为字典树），Trie树由词的公共前缀构成节点，降低了存储空间的同时可以提升查找效率。

最大匹配分词将句子与Trie树进行匹配，在匹配到根结点时由下一个字重新开始进行查找。比如正向（从左至右）匹配“他说的确实在理”，得出的结果为“他／说／的确／实在／理”。如果进行反向最大匹配，则为“他／说／的／确实／在理”。

这种方式虽然可以在O(n)时间对句子进行分词，但是只单向匹配太过绝对，尤其是金融这种词汇较丰富的场景，会出现例如“交易费/用”、“报价单/位”等情况，所以除非某些词的优先级很高，否则要尽量避免使用此算法。

最短路径分词算法首先将一句话中的所有词匹配出来，构成词图（有向无环图DAG），之后寻找从起始点到终点的最短路径作为最佳组合方式，例：

我们认为图中每个词的权重都是相等的，因此每条边的权重都为1。

在求解DAG图的最短路径问题时，总是要利用到一种性质：即两点之间的最短路径也包含了路径上其他顶点间的最短路径。比如S-A-B-E为S到E到最短路径，那S-A-B一定是S到B到最短路径，否则会存在一点C使得d(S-C-B)d(S-A-B)，那S到E的最短路径也会变为S-C-B-E，这就与假设矛盾了。利用上述的最优子结构性质，可以利用贪心算法或动态规划两种求解算法：

（1）基于Dijkstra算法求解最短路径，该算法适用于所有带权有向图，求解源节点到其他所有节点的最短路径，并可以求得全局最优解；

（2）N-最短路径分词算法，该方法是对Dijkstra算法的扩展，在每一步保存最短的N条路径，并记录这些路径上当前节点的前驱，在最后求得最优解时回溯得到最短路径。这种方法的准确率优于Dijkstra算法，但在时间和空间复杂度上都更大。

相较于最大匹配分词算法，最短路径分词算法更加灵活，可以更好地把词典中的词组合起来，能更好地解决有歧义的场景。比如上述“他说的确实在理”这句话，用最短路径算法的计算结果为“他／说／的／确实／在理”，避免了正向最大匹配的错误。但是对于词典中未存在的词基本没有识别能力，无法解决金融领域分词中的“未登录词”难点。

N-Gram（又称N元语法模型）是基于一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关。在此种假设下，可以简化词的条件概率，进而求解整个句子出现的概率。

现实中，常用词的出现频率或者概率肯定比罕见词要大。因此，可以将求解词图最短路径的问题转化为求解最大概率路径的问题，即分词结果为“最有可能的词的组合“。

计算词出现的概率，仅有词典是不够的，还需要充足的语料，所以分词任务已经从单纯的“算法”上升到了“建模”，即利用统计学方法结合大数据挖掘，对“语言”（句子出现的概率）进行建模。

我们将基于N-gram模型所统计出的概率分布应用到词图中，可以得到词的概率图。对该词图用最短路径分词算法求解最大概率的路径，即可得到分词结果。

相较于前两种分词算法，基于N-Gram model的分词算法对词频进行了统计建模，在切分有歧义的时候力求得到全局最优值，比如在切分方案“证券/自营/业务”和“证券/自/营业/务”中，统计出“证券/自营/业务”出现的概率更大，因此结果有更高的准确率。但也依然无法解决金融场景中未登录词的问题。

生成式模型主要有隐马尔可夫模型（HMM，Hidden Markov Model）、朴素贝叶斯分类等。HMM是常用的分词模型，基于Python的jieba分词器和基于Java的HanLP分词器都使用了HMM。

HMM模型认为在解决序列标注问题时存在两种序列，一种是观测序列，即人们显性观察到的句子，另一种是隐状态序列，即观测序列的标签。假设观测序列为X，隐状态序列是Y，则因果关系为Y-X。因此要得到标注结果Y，必须对X的概率、Y的概率、P(X|Y)进行计算，即建立P(X,Y)的概率分布模型。

HMM算法可以在一定程度上解决未登录词的问题，但生成式模型的准确率往往没有接下来要谈到的判别式模型高。

判别式模型主要有感知机、支持向量机（SVM，Support Vector Machine）、条件随机场（CRF，Conditional Random Field）、最大熵模型等，其中感知机模型和CRF模型是常用的分词模型。

（1）平均感知机分词算法

感知机是一种简单的二分类线性模型，通过构造超平面，将特征空间（输入空间）中的样本分为正负两类。通过组合，感知机也可以处理多分类问题。但由于每次迭代都会更新模型的所有权重，被误分类的样本会造成很大影响，因此采用平均的方法，在处理完一部分样本后对更新的权重进行平均。

（2）CRF分词算法

CRF可以看作一个无向图模型，假设给定的标注序列为Y，观测序列为X，CRF对条件概率P(Y|X)进行定义，而不是对联合概率建模。

平均感知机算法虽然速度快，但仍不够准确。适合一些对速度要求高、对准确性要求相对不那么高的场景。CRF分词算法可以说是目前最常用的分词、词性标注和实体识别算法，它对未登陆词也有很好的识别能力，是目前在速度、准确率以及未登录词识别上综合表现最突出的算法，也是我们目前所采用的解决方案，但速度会比感知机慢一些。

在NLP中，最常用的神经网络为循环神经网络（RNN，Recurrent Neural Network），它在处理变长输入和序列输入问题中有着巨大的优势。LSTM（Long Short-Term Memory，长短期记忆网络）为RNN变种的一种，在一定程度上解决了RNN在训练过程中梯度消失和梯度爆炸的问题。

目前对于序列标注任务，业内公认效果最好的模型是BiLSTM+CRF。相比于上述其它模型，双向循环神经网络BiLSTM，可以更好地编码当前字等上下文信息，并在最终增加CRF层，核心是用Viterbi算法进行解码，以得到全局最优解，避免B,S,E这种不可能的标记结果的出现，提高准确率。

神经网络分词虽然能在准确率、未登录词识别上有更好的表现，但RNN无法并行计算，在速度上没有优势，所以该算法通常在算法研究、句子精确解析等对速度要求不高的场景下使用。

分词作为NLP底层任务之一，既简单又重要，很多时候上层算法的错误都是由分词结果导致的。因此，对于底层实现的算法工程师，不仅需要深入理解分词算法，更需要懂得如何高效地实现和调试。

而对于上层应用的算法工程师，在实际分词时，需要根据业务场景有选择地应用上述算法，比如在搜索引擎对大规模网页进行内容解析时，对分词对速度要求大于精度，而在智能问答中由于句子较短，对分词的精度要求大于速度。

分词算法HMM隐马尔可夫模型

在网上看了很多关于马尔可夫模型的资料，有很多文章写得不错，在此记录自己学习过程中的笔记

隐马尔可夫模型(Hidden Markov Model, HMM)是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为 状态序列 ；每个状态生成一个观测，而由此产生的观测的随机序列，称为 观测序列 。序列的每一个位置又可以看作是一个时刻。

隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。

一个简单的例子

假设我们有3颗不同的骰子。第一个是6面体、第二个是4面体、第三个是8面体，对应每一面数值分别为（1,2,3,4,5,6）、（1,2,3,4）、（1,2,3,4,5,6,7,8），出现概率分别为

我们开始掷骰子，我们从这三个骰子里挑选一个骰子的概率为 。我们掷骰子的数值在1~8之间。当不停的掷骰子我们会得到一串数字序列。例如（掷骰10次）:1、6、3、5、2、7、3、5、 2、4。

上图可以看出马尔可夫模型为节点为隐含状态，边为转移概率的有向图模型，接下来我们通过这个例子介绍几个概念。

可见状态链（观测序列） ：掷骰子得到的这串数字对应概念中我们可观察的参数。

隐含状态链（状态序列） ：在这个掷骰子的例子中隐含状态链为我们掷的骰子的序列(有多种可能)。隐含状态（骰子）之间存在转换概率，D4的下一个状态D4、D6、D8的概率都是 。

转换概率（状态转移概率）： 隐含状态转换（骰子改变）的概率

输出概率（发射状态）： 尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率。就我们的例子来说，六面体掷出1的概率为 ，四面体掷出1的概率为 ，八面体掷出1的概率为 。

当然转换概率和输出概率我们都是随意更改的，比如输出概率方面我们对骰子做点手脚可以让例如六面体掷出1的概率为 ，其它数字的概率为 。转换概率方面我们可以放入比如在2颗D6、4颗D4、4颗D8中选择筛子，然后有放回的选择筛子，转换概率D6为0.2， D4为0.4，D8为0.4。

使用维特比算法（Viterbi algorithm）进行分词根据观测序列推断出状态序列

观察值序列：小明硕士毕业于中国科学院计算所

隐含状态集：隐含状态指的是每个字的状态。 有词语的开头、词语的中间字、词尾、单个字，这里的隐含状态集有4个状态对应的英文字母{B,M,E,S}

输入：小明硕士毕业于中国科学院计算所

输出：BEBEBMEBEBMEBES（BE/BE/BME/BE/BME/BE/S =小明/硕士/毕业于/中国/科学院/计算/所）

1、定义V[id][字的状态] = 概率，注意这里的概率，前几个的字的状态都确定下来了（概率最大），这里的概率就是一个累乘的概率了。

2、因为第一个字为‘小’，所以第一个字的概率V[1][B]= 初始概率[B] *发射概率[B][‘小’]，同理可得V[1][M]、V[1][E]、V[1][S]选择其中概率最大的一个加入到结果序列。

3、从第二个字开始，对于字的状态Y，都有前一个字的状态是X的概率* X转移到Y的概率 * Y状态下输出字为‘明’的概率。因为前一个字的状态Y有四种可能，所以Y的概率有四个，选取其中较大一个作为V[2][字的状态]的概率，同时加入到结果序列中。

4、比较V[15][B]、V[15][M]、V[15][E]、V[15][S]，找出较大的哪一个对应的序列，就是最终结果。

自然语言处理——7.5 自动分词基本算法

?? 有词典切分/ 无词典切分

?? 基于规则的方法/ 基于统计的方法

－有词典切分，机械切分

假设句子： ，某一词： 为词典中最长词的字数。

设待切分字串 ，其中 为单个的字， 为串的长度， 。建立一个节点数为 的切分有向无环图 ，各节点编号依次为 。

求最短路径：贪心法或简单扩展法。

把输入字串(句子) 作为 的输入；切分后的单词串 为状态的输出，即观察序列 。词性序列 为状态序列，每个词性标记 对应 中的一个状态 ， 。

将分词过程看作是字的分类问题。该方法认为，每个字在构造一个特定的词语时都占据着一个确定的构词位置(即词位)。假定每个字只有4个词位：词首(B)、词中(M)、词尾(E)和单独成词(S)，那么，每个字归属一特定的词位。

该方法的重要优势在于，它能够平衡地看待词表词和未登录词的识别问题，文本中的词表词和未登录词 都是用统一的字标注过程来实现的。在学习构架上， 既可以不必专门强调词表词信息，也不用专门设计特 定的未登录词识别模块，因此，大大地简化了分词系统的设计

使用3-gram:

而基于字的分词方法采用区分式模型(Discriminative model)

假设 是观察值， 是模型。如果对 进行建模, 就是生成式模型。其基本思想是：首先建立样本的概 率密度模型，再利用模型进行推理预测。要求已知样 本无穷多或者尽可能地多。该方法一般建立在统计学 和 Bayes 理论的基础之上。

? 主要特点 ：从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。

? 主要优点 ：实际上所带的信息要比判别式模型丰富，研究单类问题比判别式模型灵活性强，模型可以通 过增量学习得到，且能用于数据不完整(missing data) 情况。

? 主要缺点 ：学习和计算过程比较复杂。

6.2.2 判别(区分)式模型(Discriminative Model)

如果对条件概率(后验概率) 进行建模，就是判别式模型。基本思想是：有限样本条件下建立判别函数，不 考虑样本的产生模型，直接研究预测模型。表性理论为统计学习理论。

? 主要特点 ：寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。

? 主要优点 ：判别式模型比生成式模型较容易学习。

? 主要缺点 ：黑盒操作，变量间的关系不清楚，不可视。

基于字的区分模型有利于处理集外词，而基于词的生成模型更多地考虑了词汇之间以及词汇内部字与字之间的依存关系。因此，可以将两者的优势结合起来。

6.2.3 结合方法1

结合方法1：将待切分字串的每个汉字用 替代， 以 作为基元，利用语言模型选取全局最优(生成式模型)。

6.2.4 结合方法2:插值法把两种方法结合起来

有哪些比较好的中文分词方案？

中文分词是中文文本处理的一个基础步骤，也是中文人机自然语言交互的基础模块。不同于英文的是，中文句子中没有词的界限，因此在进行中文自然语言处理时，通常需要先进行分词，分词效果将直接影响词性、句法树等模块的效果。当然分词只是一个工具，场景不同，要求也不同。在人机自然语言交互中，成熟的中文分词算法能够达到更好的自然语言处理效果，帮助计算机理解复杂的中文语言。竹间智能在构建中文自然语言对话系统时，结合语言学不断优化，训练出了一套具有较好分词效果的算法模型，为机器更好地理解中文自然语言奠定了基础。在此，对于中文分词方案、当前分词器存在的问题，以及中文分词需要考虑的因素及相关资源，竹间智能自然语言与深度学习小组做了些整理和总结。中文分词根据实现原理和特点，主要分为以下2个类别：

1、基于词典分词算法也称字符串匹配分词算法。该算法是按照一定的策略将待匹配的字符串和一个已建立好的“充分大的”词典中的词进行匹配，若找到某个词条，则说明匹配成功，识别了该词。常见的基于词典的分词算法分为以下几种：正向最大匹配法、逆向最大匹配法和双向匹配分词法等。基于词典的分词算法是应用最广泛、分词速度最快的。很长一段时间内研究者都在对基于字符串匹配方法进行优化，比如最大长度设定、字符串存储和查找方式以及对于词表的组织结构，比如采用TRIE索引树、哈希索引等。

2、基于统计的机器学习算法这类目前常用的是算法是HMM、CRF、SVM、深度学习等算法，比如stanford、Hanlp分词工具是基于CRF算法。以CRF为例，基本思路是对汉字进行标注训练，不仅考虑了词语出现的频率，还考虑上下文，具备较好的学习能力，因此其对歧义词和未登录词的识别都具有良好的效果。NianwenXue在其论文《Combining Classifiers for Chinese Word Segmentation》中首次提出对每个字符进行标注，通过机器学习算法训练分类器进行分词，在论文《Chinese word segmentation as character tagging》中较为详细地阐述了基于字标注的分词法。常见的分词器都是使用机器学习算法和词典相结合，一方面能够提高分词准确率，另一方面能够改善领域适应性。

如何理解分词术的歧义

何为分词?中文分词与其他的分词又有什么不同呢?分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在上面的例子中我们就可以看出，在英文的行文中，单词之间是以空格作为自然分界符的，而中文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，但是在词这一层上，上面的例子中我们也可以看出，中文比之英文要复杂的多、困难的多。 目前主流的中文分词算法有以下3种： 1、 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹 配成功(识别出一个词)。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况，可以分为最大(最长)匹配和最小(最短)匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 1)正向最大匹配法(由左到右的方向)； 2)逆向最大匹配法(由右到左的方向)； 3)最少切分(使每一句中切出的词数最小)。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为 1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还 需通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分 为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反 过来对分词结果进行检验、调整，从而极大地提高切分的准确率。 2、 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织 成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 3、 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统 计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这 一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典(常用词词典)进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 分词几点要注意: 1.分词算法的时间性能要比较高。尤其是现在的web搜索，实时性要求很高。所以作为中文信息处理基础的分词首先必须占用尽可能少的时间。 2.分词正确率的提高并不一定带来检索性能的提高。分词到达一定精度之后，对中文信息检索的影响不再会很明显，虽然仍然还是有一些影响，但是这已经不是CIR的性能瓶颈。所以片面的一味追求高准确率的分词算法并不是很适合大规模中文信息检索。在时间和精度之间存在矛盾无法兼顾的情况下，我们需要在二者之间找到一个合适的平衡点。 3.切分的颗粒度仍然可以依照长词优先准则，但是需要在查询扩展层面进行相关后续处理。在信息检索中，分词算法只需要集中精力考虑如何消除交叉歧义。对于覆盖歧义，我们可以利用词典的二次索引和查询扩展来解决。 4.未登录词识别的准确率要比召回率更加重要。要尽量保证未登录词识别时不进行错误结合，避免因此切分出错误的未登录词。如果将单字错误的结合成未登录词了，则有可能导致无法正确检索到相应的文档。 百度的分词 首先根据分割符号将查询分开。“信息检索 理论 工具” 分词后 。 然后看看是否有重复的字符串，如果有，就抛弃多余的，只保留一个。“理论 工具理论”分词后，GOOGLE不考虑这个并归计算。 接着判断是否有英文或者数字，如果有的话，把英文或者数字当作一个整体保留并把前后的中文切开。查询”电影BT下载”分词后。 如果字符串只包含小于等于3个中文字符的话，那就保留不动，当字符串长度大于4个中文字符的时候，百度的分词程序才出马大干快上，把这个字符串肢解掉。 分词算法类型正向最大匹配，反向最大匹配，双向最大匹配，语言模型方法，最短路径算法判断一个分词系统好不好，关键看两点，一个是消除歧义能力；一个是词典未登录词的识别比如人名，地名，机构名等。 百度分词采取了至少两个词典，一个是普通词典，一个是专用词典(人名、地名、新词等)。而且是专用词典先切分，然后将剩余的片断交由普通词典来切分。 百度用分词算法类型采用的是双向最大匹配算法。

有哪些比较好的中文分词方案

中文分词算法大概分为两大类

a.第一类是基于字符串匹配，即扫描字符串，如果发现字符串的子串和词相同，就算匹配。

这类分词通常会加入一些启发式规则，比如“正向/反向最大匹配”, “长词优先” 等策略。

这类算法优点是速度块，都是O(n)时间复杂度，实现简单，效果尚可。

也有缺点，就是对歧义和未登录词处理不好。

b.第二类是基于统计以及机器学习的分词方式

这类分词基于人工标注的词性和统计特征，对中文进行建模，即根据观测到的数据（标注好的语料）对模型参数进行估计，即训练。 在分词阶段再通过模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。常见的序列标注模型有HMM和CRF。

这类分词算法能很好处理歧义和未登录词问题，效果比前一类效果好，但是需要大量的人工标注数据，以及较慢的分词速度。