转载请注明出处：http://www.codelast.com/
 
现在有很多开源的中文分词器库，如果你的项目要选择其一来实现中文分词功能，必然要先评测它们的分词效果。如何评测？下面详细叙述。

 【1】黄金标准/Golden standard
 
所谓的黄金标准是指：评价一个分词器分词结果的好坏，必然要有一份“公认正确”的分词结果数据来作为参照。
 
通常，我们使用一份人工标注的数据作为黄金标准。但是，就算是人工标注的数据，每个人对同一句话的分词结果恐怕也持有不同的意见，例如，有一句话“科学技术是第一生产力”，有人说应该这样分词：“科学技术 是 第一 生产力”，又有人说应该这样分词：“科学 技术 是 第一 生产力”。那么，到底哪种才是对的呢？
 因此，要找有权威的分词数据来做为黄金标准。
 大家可以使用SIGHAN（国际计算语言学会（ACL）中文语言处理小组）举办的国际中文语言处理竞赛Second International Chinese Word Segmentation Bakeoff（http://sighan.cs.uchicago.edu/bakeoff2005/）所提供的公开数据来评测，它包含了多个测试集以及对应的黄金标准分词结果。
 文章来源：http://www.codelast.com/
 【2】评价指标
 精度（Precision）、召回率（Recall）、F值（F-mesure）是用于评价一个信息检索系统的质量的3个主要指标，以下分别简记为P，R和F。同时，还可以把错误率（Error Rate）作为分词效果的评价标准之一（以下简记为ER）。
 直观地说，精度表明了分词器分词的准确程度；召回率也可认为是“查全率”，表明了分词器切分正确的词有多么全；F值综合反映整体的指标；错误率表明了分词器分词的错误程度。
 P、R、F越大越好，ER越小越好。一个完美的分词器的P、R、F值均为1，ER值为0。
 通常，召回率和精度这两个指标会相互制约。
 
 
 
例如，还是拿上面那句话作为例子：“科学技术是第一生产力”（黄金标准为“科学技术 是 第一 生产力”），假设有一个分词器很极端，把几乎所有前后相连的词的组合都作为分词结果，就像这个样子：“科学 技术 科学技术 是 是第一 第一生产力 生产力”，那么毫无疑问，它切分正确的词已经覆盖了黄金标准中的所有词，即它的召回率（Recall）很高。但是由于它分错了很多词，因此，它的精度（Precision）很低。
 
因此，召回率和精度这二者有一个平衡点，我们希望它们都是越大越好，但通常不容易做到都大。
 文章来源：http://www.codelast.com/
 为了陈述上述指标的计算方法，先定义如下数据：
  ：黄金标准分割的单词数
  ：分词器错误标注的单词数
  ：分词器正确标注的单词数
 
则以上各指标的计算公式如下：
 
 
文章来源：http://www.codelast.com/
 【3】正确及错误标注的计数算法
 
 
 
如上所述，我们要先计算出e和c，才能计算出各指标值。  和  是按如下算法来统计的：
 
在“黄金标准”和“待评测的结果”中，理论上，除了分词后添加的空格之外，它们所有的文字都是相同的；唯一的不同就在于那些有差异的分词结果的位置上。例如，“计算机 是个 好东西”（黄金标准）与“计算机 是 个 好东西”（待评测的结果）的差异就在于“是个”与“是 个”的差异，其余分词结果都是相同的。因此，只需要找到这种差异的个数，就可以统计出分词器正确标注了多少个词、错误标注了多少个词。
  
 
以下面的分词结果为例：
 
“计算机 总是 有问题”——黄金标准
 
“计算机 总 是 有问题”——待评测的结果
  
 
给分出来的每个词都做位置的标记（位置从1开始）：
 
(1,4)，(4,6)，(6,9) ——黄金标准
 
(1,4)，(4,5)，(5,6)，(6,9) ——待评测的结果
 文章来源：http://www.codelast.com/
 
那么我们会发现，(1,4)和(6,9)这两个词是相同的（即“计算机”和“有问题”），而差异在于(4,6)和(4,5)，(5,6)（即“总是”和“总 是”），因此，我们只需要比较这两个标注结果中的差异数，就可以知道分词器正确、错误地标注了多少个单词。在此例中，正确的标注的单词数为2，错误标注的单词数为2。
  
 
需要说明的是：在此例中，也可以认为错误标注的单词数为1（即“总是”与“总 是”的差异），按照最大错误数来算会使错误率升高（在分词精度很差的情况下，可能会导致ER>100%），不过，在所有分词器都使用同一标准来评测的情况下，也就会很公平，并不会影响到最终的结论。
 
 
 
有了上面的算法，就很容易写出一个评测程序了。这里就不把程序放上来了。
 文章来源：http://www.codelast.com/
 【4】参考文献
 ① Word Segmentation: Quick but not Dirty.
 
Timothy Gambell 1814 Clover Lane Fort Worth, TX 76107, timothy.gambell@aya.yale.edu
 
Charles Yang* Department of Linguistics, Yale University New Haven, CT 06511, charles.yang@yale.edu
 
② Chinese Segmentation and New Word Detection using Conditional Random Fields
 Fuchun Peng, Fangfang Feng, Andrew McCallum, Computer Science Department, University of Massachusetts Amherst, 140 Governors Drive, Amherst, MA, U.S.A. 01003, {fuchun, feng, mccallum}@cs.umass.edu
 ③ A Compression-based Algorithm for Chinese Word Segmentation
 
W. J. Teahan, The Robert Gordon University
 
Rodger McNab, University of Waikato
 
Yingying Wen, University of Waikato
 
Ian H. Witten, University of Waikato

NLP(1) | 词向量one hot编码词向量编码思想
 

分词的概念
 
        简单来说就是把词进行分开，分词的难点： 1.如何避免歧义，如：“白开水不如果汁甜”。如何让机器避免将“如果”分到一起。 2.如何识别未登录词，并判断词性（人物，地点） 解决歧义的方法有很多，使用n_gram模型或者概率统计在解决歧义的作用下很好实现，如下面要介绍的HMM和CRF.
 
 
 
分词方法分类
 
基于词典的分词算法 基于词典的分词算法又称为机械分词算法，它是按照一定的策略将待分析的汉字串与一个“充分大的机器词典”中的词条进行匹配 , 若在词典中找到某个字符串, 则匹配成功,认为这个字串是词并将之切分出来。基于词典的分词算法有三个要素,分词词典、扫描方向（正向、逆向）和匹配原则（最大匹配，最小匹配等）[2]。 正向最大匹配算法。假设词典里词条的最大长度是Maxlen,则每次从文本最左边截取一个字符串，其长度为Maxlen，把该字串在词典中进行匹配，如果匹配成功，则将这个词从句子中切分出来；若匹配不成功，则将这个字串的最后一个字去掉，再将新得到的字串在词典中匹配。循环这个过程，直到切分出所有的词。
基于统计的分词算法和基于理解的分词算法 基于统计的分词算法主要思想是，词是稳定的字的组合，两个字在文本中连续出现的次数越多，就越有可能组合成一个词。因此这类算法通过对大量文本的统计,根据字串在文本中出现的统计频率来决定其是否构成一个词。其主要的统计模型有：互信息、N元文法模型、神经网络模型和隐马尔科夫模型（HMM）等。
下面就介绍一下最大随机场和隐马可夫模型在中文分词中的应用
 
CRF
 
原理 用一句话来解释就是“有序列的分类”。 就是在原来分类的基础上考虑到了时序，开始（B），中间（B），结尾（E），以及单字构成的词（S） CRF分词的过程就是对词位标注后，将B和E之间的字，以及S单字构成分词 CRF学习的过程： 就是描述一些特征配置：当前词语是xx，上个词xx，满足这种配置的，特征函数输出就是1，不然是0。每个词都有同样多的特征函数判断，所以是全局优化值。预测的过程就是利用每种特征配置给标签打分，然后打分结果加权求和，打分最高的标签，就是预测结果。 训练方法： 线性链的条件随机场跟线性链的隐马尔科夫模型一样，一般推断用的都是维特比算法。这个算法是一个最简单的动态规划。首先我们推断的目标是给定一个X，找到使P(Y|X)最大的那个Y嘛。然后这个Z(X)，一个X就对应一个Z，所以X固定的话这个项是常量，优化跟他没关系（Y的取值不影响Z）。然后 exp也是单调递增的，也不带他，直接优化exp里面。所以最后优化目标就变成了里面那个线性和的形式，就是对每个位置的每个特征加权求和。比如说两个状态的话，它对应的概率就是从开始转移到第一个状态的概率加上从第一个转移到第二个状态的概率，这里概率是只exp里面的加权和。那么这种关系下就可以用维特比了。
维特比原理 首先你算出第一个状态取每个标签的概率，然后你再计算到第二个状态取每个标签得概率的最大值，这个最大值是指从状态一哪个标签转移到这个标签的概率最大，值是多 少，并且记住这个转移（也就是上一个标签是啥）。然后你再计算第三个取哪个标签概率最大，取最大的话上一个标签应该是哪个。以此类推。整条链计算完之后， 你就知道最后一个词去哪个标签最可能，以及去这个标签的话上一个状态的标签是什么、取上一个标签的话上上个状态的标签是什么，酱。这里我说的概率都是 exp里面的加权和，因为两个概率相乘其实就对应着两个加权和相加，其他部分都没有变。
与HMM区别 1）HMM是假定满足HMM独立假设。CRF没有，所以CRF能容纳更多上下文信息。 2）CRF计算的是全局最优解，不是局部最优值。 3）CRF是给定观察序列的条件下，计算整个标记序列的联合概率。而HMM是给定当前状态，计算下一个状态。 4）CRF比较依赖特征的选择和特征函数的格式，并且训练计算量大
示例 这里用的是genius包 Genius是一个开源的python中文分词组件，采用 CRF(Conditional Random Field)条件随机场算法。
#encoding=utf-8
import genius
text = u"""昨天,我和施瓦布先生一起与部分企业家进行了交流,大家对中国经济当前、未来发展的态势、走势都十分关心。"""
seg_list = genius.seg_text(
    text,
    use_combine=True,
    use_pinyin_segment=True,
    use_tagging=True,
    use_break=True
)
print('\n'.join(['%s\t%s' % (word.text, word.tagging) for word in seg_list]))
 
['昨天', ',', '我', '和', '施瓦布', '先生', '一起', '与', '部分', '企业家', '进行', '了', '交流', ',', '大家', '对', '中国', '经济', '当前', '、', '未来', '发展', '的', '态势', '、', '走势', '都', '十分关心']
 
HMM分词
 
HMM是关于时序的概率模型，描述一个含有未知参数的马尔可夫链所生成的不 可观测的状态随机序列，再由各个状态生成观测随机序列的过程。HMM是一个 双重随机过程---具有一定状态的隐马尔可夫链和随机的观测序列. HMM由隐含状态S、可观测状态O、初始状态概率矩阵π、隐含状态转移概率矩 阵A、可观测值转移矩阵B(又称为混淆矩阵，Confusion Matrix)； π和A决定了状态序列，B决定观测序列，因此HMM可以使用三元符号表示，称 为HMM的三元素：
 
 
具体的原理部分会专门用一章来介绍。 具体代码可以见：https://github.com/tostq/Easy_HMM
 
 
 

参考
 
https://cloud.tencent.com/developer/article/1163101
 
 

 
目录
 
中文分词评测方法
步骤
参考资料
 

 
中文分词评测方法
 
对于分词，目前有很多开源的程序，包括hanlp、jieba、哈工大分词等。为了确定哪种分词结果比较好，通常有两种方式，一种是调用接口，对特定的句子分词，通过感觉对分词结果进行对比，但这种分词结果却带有了很大的主观色彩。在网上也是博客在介绍。另一种则通过测试集对分词结果与标准的分词进行分析，得出准确率、召回率等。
 
步骤
 
 
开放的测试集选取
 一般测试集产生的来源主要源于竞赛，但是，我在搜索过程中，只找到了一个，Second International Chinese Word Segmentation Bakeoff ，虽然竞赛是2005年公开的，但是却没找到别的，大家如果有其他更好的，麻烦留言交流。
 接下来我们就以这个测试集对分词结果进行分析。
 
 
下载数据集
 icwb2-data.zip [50 MB, md5]，大家尽量跳转到官网进行下载。
 
 
目录结构
 
doc  nshort_seg.out  testing  training  gold  README   scripts
 
其中：
 
  
gold: 包含测试数据和训练数据单词列表。
scripts： 对比分析效果的脚本。
testing: 里面包含了未分词的文本，其标准分词在gold的目录的对应文件中。
training: 包含了训练数据集。
doc： 包含了竞赛的说明文档。
 
 
评分方法
 script文件夹中，包含了score脚本，脚本执行的时候需要三个参数，训练集、标准分词、自己分词。
 执行脚本如下，可根据自己的需求更换对应的参数
 
perl scripts/score gold/pku_training_words.utf8 gold/pku_test_gold.utf8 gold/pku_test.out
 
 
结果展示
 结果中包含了单个文本片段，以及最后总的评分结果，这里我们仅展示总的评分结果。
 
=== TOTAL INSERTIONS:   993
=== TOTAL DELETIONS:    7143
=== TOTAL SUBSTITUTIONS:        7617
=== TOTAL NCHANGE:      15753
=== TOTAL TRUE WORD COUNT:      104372
=== TOTAL TEST WORD COUNT:      98222
=== TOTAL TRUE WORDS RECALL:    0.859
=== TOTAL TEST WORDS PRECISION: 0.912
=== F MEASURE:  0.885
=== OOV Rate:   0.058
=== OOV Recall Rate:    0.708
=== IV Recall Rate:     0.868

 
在结果中，RECALL、PRECISION、F MEASURE:分别为召回率、精度和F值，值越高越好。
 
 
部分代码片段
 为了方便开发测试，以hanlp为例，贴出部分生成segment文件的代码
 
  
通用的类
 
public class Util {

    /**
     * 将wordlist转化为string
     * @param sentence segment生成的List<Term>
     * @param posflag 是否输出标签，在测试时输入为false
     * @return
     */
    public static String wordlist2String(List<Term> sentence, boolean posflag){
        StringBuffer result = new StringBuffer();
        if(sentence.size()>=1){
            for(Term w:sentence){
                if(w.getWord()!=null && !" ".equals(w.getWord())){//去掉begin和end
                    result.append(w.getWord());
                    if(true==posflag){
                        result.append("/"+w.getNature().toString());
                    }
                    if (w.getWord().equals("\r\n")){
                        continue;
                    }
                    result.append("  ");
                }
            }
        }
        return result.toString();
    }
    
    /**
     * 读取根路径下的文件
     *
     * @param filePath 文件路径
     *            
     * @return byte[]
     *
     */
    public static String readSystemFileToByte(String filePath) {
        InputStream inStream = null;
        byte data[] = null;
        try {
            inStream = new FileInputStream(filePath);;
            ByteArrayOutputStream swapStream = new ByteArrayOutputStream();
            byte[] buff = new byte[100];
            int rc = 0;
            while ((rc = inStream.read(buff, 0, 100)) > 0) {
                swapStream.write(buff, 0, rc);
            }
            data = swapStream.toByteArray();
            inStream.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        String dataString  = null;
        try {
            dataString = new String(data, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }
        return dataString;
    }

    /**
     * 将分词结果输出到文件内容
     * @param content 分析结果
     * @param path 保存的路径
     */
    public static void write(String content, String path){
        try{
            BufferedWriter bw = new BufferedWriter(new FileWriter(path));
            bw.write(content);
            bw.newLine();
            bw.close();
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
        System.out.println("保存成功");
    }
}
 
 
测试方法
public void test(){
String inputPath = "";
String outPath="";
//读取文件内容
String content = Transform.readSystemFileToByte(inputPath);

//分词并保存结果
String outContent = Transform.wordlist2String(HanLP.segment(content),false);
    Transform.write(outContent,outPath);
}
 
 
参考资料
 
中文分词器分词效果的评测方法
Second International Chinese Word Segmentation Bakeoff

 
中文分词方法汇总笔记
 
分词难点
分词方法
传统基于字典（规则分词）
基于机器学习的分词方法
统计分词
语言模型
隐马尔可夫 HMM 模型
其他
   
  
  
分词工具和云服务
其他

 
感谢知乎 @华天清 的总结
 
 
分词难点
 
分词算法： 不同的分词算法得到的分词结果不同，对下层的文本处理有较大的影响
未登录词的OOV的识别： 难以识别未登录词
歧义：
 组合型歧义：在汉字字段AB中, A是词, B是词, AB仍是词, 则AB为组合型歧义字段。
 例：我是/清华大学/的；我是/清华/大学/的
 交集型歧义：在字段 ABC 中 AB是词 BC也是词， 则 ABC为交集型歧义
 例：球拍/卖 球/拍卖
 真歧义：在一句话中, 由人去判断也不知道哪个应该是词, 哪个应该不是词
 例：球拍卖了 可以是 球/拍卖了 也可以是 球拍/卖了
 
分词方法
 
传统基于字典（规则分词）
 
一、 正向最大匹配法 FMM:
 
从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，重复以上过程，直到切分出所有词为止。
 
 
二、逆向最大匹配法 RMM：
 对文本从右至左切出最长的词，该算法是正向最大匹配的逆向思维，匹配不成功，将匹配字段的最前一个字去掉，实验表明，逆向最大匹配算法要优于正向最大匹配算法
 汉语中偏正结构较多，若使用逆向匹配，可以适当的提高精度
 三、双向匹配分词法 BMM：
 将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。
 
正逆向分词次数不同，选分词树较少的
词数相同，且结果相同 返回任意一个
词数相同，结果不同，返回单字最少的
 
# -*- coding:utf-8 -*-
# @Time    : 2019/10/21 11:12
# @Author  : Ray.X
# 初始化
word_dict = ['研究', '研究生', '生命', '起源', '南京市', '南京市长', '长江', '大桥', '长江大桥']
test_str = '在南京市长江大桥研究生命的起源'
# 遍历分词词典，获得最大分词长度
MaxLen = 0
for key in word_dict:
    if len(key) > MaxLen:
        MaxLen = len(key)


def forward_mm():
    """
    正向最大匹配 FMM
    :return:
    """
    foward_out = []
    n = 0
    while n < len(test_str):
        matched = 0
        # range(start, stop, step)，根据start与stop指定的范围以及step设定的步长 step=-1表示去掉最后一位
        for i in range(MaxLen, 0, -1):  # i等于max_chars到1 3-2-1
            w = test_str[n: n + i]  # 截取文本字符串n到n+1位
            # 判断所截取字符串是否在分词词典内
            if w in word_dict:
                foward_out.append(w)
                matched = 1
                n = n + i
                break
        if not matched:  # 等于 if matched == 0
            foward_out.append(test_str[n])
            n = n + 1
    print('正向最大匹配 FMM:\n', foward_out)
    return foward_out


def reverse_mm():
    """
    逆向最大匹配 RMM
    :return:
    """
    reverse_out = []
    n = len(test_str)
    while 0 < n:
        matched = 0
        # range([start,] stop[, step])，根据start与stop指定的范围以及step设定的步长 step=-1表示去掉最后一位
        for i in range(MaxLen, 0, -1):  # i等于max_chars到1
            w = test_str[n - i: n]  # 截取文本字符串n-i到n位
            # 判断所截取字符串是否在分词词典内
            if w in word_dict:
                reverse_out.append(w)
                matched = 1
                n = n - i
                break
        if matched == 0:
            reverse_out.append(test_str[n - 1])
            n = n - 1
    print('逆向最大匹配 RMM:\n', list(reversed(reverse_out)))  # 因为是逆向所以最终结果需要反向
    return list(reversed(reverse_out))


def bi_mm():
    """
    双向最大匹配 BMM
    :return:
    """
    fmm = forward_mm()
    rmm = reverse_mm()
    # 单字词个数
    f_single_word = 0
    r_single_word = 0
    # 总词数
    tot_fmm = len(fmm)
    tot_rmm = len(rmm)
    # 未登录词
    oov_fmm = 0
    oov_rmm = 0
    # 罚分，罚分值越低越好
    score_fmm = 0
    score_rmm = 0
    # 如果正向和反向结果一样，返回任意一个
    if fmm == rmm:
        bmm = rmm
    else:  # 分词结果不同，返回单字数、非字典词、总词数少的那一个
        for w in fmm:
            if len(w) == 1:
                f_single_word += 1
            if w not in word_dict:
                oov_fmm += 1
        for w in rmm:
            if len(w) == 1:
                r_single_word += 1
            if w not in word_dict:
                oov_rmm += 1

        # 可以根据实际情况调整惩罚分值
        # 这里都罚分都为1分
        # 非字典词越少越好
        if oov_fmm > oov_rmm:
            score_fmm += 1
        elif oov_fmm < oov_rmm:
            score_rmm += 1
        # 总词数越少越好
        if tot_fmm > tot_rmm:
            score_fmm += 1
        elif tot_fmm < tot_rmm:
            score_rmm += 1
        # 单字词越少越好
        if f_single_word > r_single_word:
            score_fmm += 1
        elif f_single_word < r_single_word:
            score_rmm += 1

        # 返回罚分少的那个
        if score_fmm < score_rmm:
            bmm = fmm
        else:
            bmm = rmm
    print('双向最大匹配 BMM:\n', bmm)

    
if __name__ == "__main__":
    bi_mm()

 

 从结果看 逆向优于正向
 
四、N-最短路径法
 每个句子将生成一个有向无环图, 每个字作为图的一个定点, 边代表可能的分词
 
 
在上图中, 边的起点为词的第一个字, 边的终点为词尾的下一个字. 边1表示"我"字单字成词, 边2表示"只是"可以作为一个单词.
 每个边拥有一个权值, 表示该词出现的概率. 最简单的做法是采用词频作为权值, 也可以采用TF-IDF值作为权值提高对低频词的分词准确度.
 N最短路径分词即在上述有向无环图中寻找N条权值和最大的路径, 路径上的边标志了最可能的分词结果.通常我们只寻找权值和最大的那一条路径.
 
 根据上图的权值最大路径得到的分词结果为: “我/只是/做/了/一些/微小/的/工作”
 参考 https://www.cnblogs.com/Finley/p/6619187.html
 
五、设立切分标志法
 收集切分标志，在自动分词前处理切分标志，再用FMM、RMM进行细加工。
 
六、最佳匹配（OM，分正向和逆向）
 对分词词典按词频大小顺序排列，并注明长度，降低时间复杂度。
 优点：易于实现
 缺点：匹配速度慢。对于未登录词的补充较难实现。缺乏自学习
 基于词典的分词方法属于粗分模型，普遍对歧义和未登录词的处理较差
 
基于机器学习的分词方法
 
统计分词
 
主要思想为把每个词看做是由词的最小单位的各个字组成，如果相连的字在不同的文本中出现的次数最多，就证明这个相连的字很可能就是一个词。因此可以利用字与字相邻出现的频率来反映成词的可靠度，当组合频率高于某一个阈值时，就认为这个相邻字构成的是一个词。
 **基本操作：**1. 建立语言模型 2. 对句子单词划分，然后对划分结果进行概率计算，获得概率最大的分词方式。
 主要使用 隐马尔可夫模型 HMM、条件随机场模型 CRF、 最大熵模型 ME等统计学算法
 
语言模型
 
语言模型在信息检索、机器翻译、语音识别中承担着重要的任务。
 用概率论来说就是：为长度为m的字符串确定其概率分布$P({\omega }_1,{\omega }_2,...,{\omega }_m)$，其中${\omega }_1$ 到${\omega }_m)$依次为文本中的各个词语
 $$P({\omega }_1,{\omega }_2,...,{\omega }_m)=P({\omega }_1)P({\omega }_2|{\omega }_1)P({\omega }_3|{\omega }_2,{\omega }_1)...P({\omega }_i|{\omega }_{i-1},...,{\omega }_2,{\omega }_1)...P({\omega }_m|{\omega }_{m-1},...,{\omega }_2,{\omega }_1)$$
 从上述公式可见采用链式法则进行计算，在文本较长时计算难度较大，因此提出了 N元文法模型 N-gram
 N-gram 就是在估算条件概率时，忽略距离大于等于n的上文词的影响，而后可将计算简化为：
 $$P({\omega }_i,|{\omega }_1,{\omega }_2,...,{\omega }_{i-1})\approx P({\omega }_i|{\omega }_{i-(n-i)},...,{\omega }_{i-2},{\omega }_{i-1})$$
 
n越大，保留的词序信息越丰富，但计算成本也呈指数级增长
 一般使用频率技术的比例来计算n元条件概率
 $$P({\omega }_i,|{\omega }_1,{\omega }_2,...,{\omega }_{i-1})=\frac{count({\omega }_{i-(n-i)},...,{\omega }_{i-2},{\omega }_{i-1},{\omega }_i)}{count({\omega }_{i-(n-i)},...,{\omega }_{i-2},{\omega }_{i-1})}$$
 $count({\omega }_{i-(n-i)},...,{\omega }_{i-2},{\omega }_{i-1},{\omega }_i)$ 表示词语$({\omega }_{i-(n-i)},...,{\omega }_{i-2},{\omega }_{i-1},{\omega }_i$在语料库中出现的总次数
 需要配合相应的平滑算法解决 分子分母为0的情况。
 例如 拉普拉斯平滑算法：
 假设在文本分类中，有3个类，C1、C2、C3，在指定的1000个训练样本中，
 某个词语K1，在 K 个类中观测计数分别为0，990，10，
 K1的概率为0，0.99，0.01，
 对这三个量使用拉普拉斯平滑的计算方法如下：　1/1003 = 0.001，991/1003=0.988，11/1003=0.011 （分子加1 ，分母加 K ）
 在实际的使用中也经常使用加 lambda（1≥lambda≥0）来代替简单加1。如果对N个计数都加上lambda，这时分母也要记得加上N*lambda。
 
隐马尔可夫 HMM 模型
 
HMM 是将分词作为字在字串中的序列标注任务来实现的。
 基本思路：每个字在构造一个特定的词语时都占据着一个确定的构词位置（即词位），现规定每个字最多只有四个构词位置：即B（词首）、M（词中）、E（词尾）和S（单字）例：
 南京长江大桥上——>南/B 京/E 长/B 江/M 大/M 桥/E 上/S
 数学表达式如下：$\lambda ={\lambda }_1{\lambda }_2...{\lambda }_n$ 代表输入的句子 $o_1{o}_2...o_n$ 代表输出的标签，n为句子的长度
 $$max=maxP(o_1{o}_2...o_n|{\lambda }_1{\lambda }_2...{\lambda }_n)$$
 在分词任务上$o$即为B、M、E、S四种标记，$\lambda$为句子中的每个字(包括标点等非中文字)
 因$P(o|\lambda )$无法精确计算，因此引入观测独立性假设，但该方法没有考虑上下文，易出现BBB\BBM的错误
 通过贝叶斯公式可得$$P(o|\lambda )=\frac{P(o,\lambda )}{P(\lambda )}=\frac{P(\lambda |o)P(o)}{P(\lambda )}$$
 $P(\lambda )$因$\lambda$作为常数可以忽略，所以$P(o|\lambda )\approx P(\lambda |o)P(o)$
 对$P(\lambda |o)P(o)$作马尔可夫假设，则 $P(\lambda |o)=P({\lambda }_1|o_1)P({\lambda }_2|o_2)...P({\lambda }_n|o_n)$
 对$P(o)$作齐次马尔可夫假设， 则$P(o)=P(o_1)P(o_2|o_1)...P(o_n|o_{n-1})$
 于是$P(\lambda |o)P(o)\approx P({\lambda }_1|o_1)P(o_2|o_1)P({\lambda }_2|o_2)P(o_3|o_2)...P({\lambda }_n|o_n)P(o_n|o_{n-1})$
 在HMM中 $P({\lambda }_n|o_n)$ 称为发射概率 $P(o_n|o_{n-1})$称为转移概率，通过设置某些转移概率为0，可以排除BBM\BBB的不合理情况
 
求解$maxP(\lambda |o)P(o)$ 的常用方法是Veterbi算法，它是一种动态规划方法，核心思想是：如果最终的最优路径经过某个$o_i$，那么从初节点到$o_{i-1}$点的路径必然也是最优路径——因为每个节点$o_i$只会影响前后两个$P(o_{i-1}|o_i)$和$P(o_i|o_{i+1})$
 
以下是 jieba 分词实现HMM的代码：
 
    def __cut(self, sentence):
    # 调用viterbi，通过viterbi算法求出隐藏状态序列
        prob, pos_list = viterbi(
            sentence, char_state_tab_P, start_P, trans_P, emit_P)
        begin, nexti = 0, 0
 	# 基于隐藏状态序列进行分词
        for i, char in enumerate(sentence):
            pos = pos_list[i][0]
            # 字所处的位置是开始位置
            if pos == 'B':
                begin = i
            # 字所处的位置是结束位置
            elif pos == 'E':
            # 这个子序列就是一个分词
                yield pair(sentence[begin:i + 1], pos_list[i][1])
                nexti = i + 1
            # 单字
            elif pos == 'S':
                yield pair(char, pos_list[i][1])
                nexti = i + 1
        # 剩余的直接作为一个分词，返回
        if nexti < len(sentence):
            yield pair(sentence[nexti:], pos_list[nexti][1])
 
jieba 的 viterbi算法
 
import sys
import operator
MIN_FLOAT = -3.14e100
MIN_INF = float("-inf")

if sys.version_info[0] > 2:
    xrange = range
def get_top_states(t_state_v, K=4):
    return sorted(t_state_v, key=t_state_v.__getitem__, reverse=True)[:K]

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]  # tabular
    mem_path = [{}]
    all_states = trans_p.keys()
    # 初始状态
    for y in states.get(obs[0], all_states):  # init
        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
        mem_path[0][y] = ''
    # 时刻t = 1,...,len(obs) - 1
    for t in xrange(1, len(obs)):
        V.append({})
        mem_path.append({})
        #prev_states = get_top_states(V[t-1])
        # 当前时刻所处的各种可能的状态
        prev_states = [
            x for x in mem_path[t - 1].keys() if len(trans_p[x]) > 0]

        prev_states_expect_next = set(
            (y for x in prev_states for y in trans_p[x].keys()))
        obs_states = set(
            states.get(obs[t], all_states)) & prev_states_expect_next

        if not obs_states:
            obs_states = prev_states_expect_next if prev_states_expect_next else all_states

        for y in obs_states:
            prob, state = max((V[t - 1][y0] + trans_p[y0].get(y, MIN_INF) +
                               emit_p[y].get(obs[t], MIN_FLOAT), y0) for y0 in prev_states)
            V[t][y] = prob
            mem_path[t][y] = state

    last = [(V[-1][y], y) for y in mem_path[-1].keys()]
    # if len(last)==0:
    #     print obs
    # 最后一个时刻
    prob, state = max(last)

    route = [None] * len(obs)
    i = len(obs) - 1
    while i >= 0:
        route[i] = state
        state = mem_path[i][state]
        i -= 1
    return (prob, route)
     # 返回最大概率对数和最优路径
 
import jieba
"""
jieba提供3种分词模式
    精确模式，试图将句子最精确地切开，适合文本分析；
    全模式，把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义；
    搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。
    
"""
default = jieba.cut('在南京市长江大桥研究生命的起源', cut_all=False)  # 精确模式 也是默认模式
full = jieba.cut('在南京市长江大桥研究生命的起源', cut_all=True)  # 全模式
search = jieba.cut_for_search('在南京市长江大桥研究生命的起源')  # 搜索引擎模式
print('default', "/ ".join(default))
print('full', "/ ".join(full))
print('search', ", ".join(search))

 
 
其他
 
支持向量机 SVM
 深度学习的分词方法
 基于神经网络的分词器
 textCNN
 序列到序列模型 seq2seq
 注意力机制 Attention Mechanism
 BERT模型
 
## 整理后稍后加入
 
分词工具和云服务
 
Hanlp 分词
 最短路径分词，有中文分词、词性标注、新词识别、命名实体识别、自动摘要、文本聚类、情感分析、词向量word2vec等功能，支持自定义词典；
 采用HMM、CRF、TextRank、word2vec、聚类、神经网络等算法；
 支持Java，C++，Python语言； 在线链接http://hanlp.com/
 JAVA:https://github.com/hankcs/HanLP
 
<dependency>
    <groupId>com.hankcs</groupId>
    <artifactId>hanlp</artifactId>
    <version>portable-1.6.1</version>
</dependency>
 
Python:https://github.com/hankcs/pyhanlp
 
pip install pyhanlp
 
data 链接http://114.115.185.60/file/data-for-1.7.5.zip
 因 Hanlp主要由java编写所以在使用时需要安装JDK
 jieba分词
 找出基于词频的最大切分组合，有中文分词、关键词提取、词性标注功能，支持自定义词典；
 采用HMM模型、 Viterbi算法；
 支持Java，C++，Python， node.js， Golang， ios
 大概是使用最多的分词工具
 https://github.com/fxsjy/jieba
 全自动安装：easy_install jieba 或者 pip install jieba / pip3 install jieba
 通过 import jieba 来引用
 哈工大的LTP
 https://github.com/HIT-SCIR/ltp
 有中文分词、词性标注、句法分析等功能；
 商用需付费；调用接口，每秒请求的次数有限制；
 编写语言有C++、Python、Java版；
 清华大学THULAC
 https://github.com/lancopku/PKUSeg-python
 支持按领域分词、有词性标注功能、支持用户自训练模型；
 基于CRF模型、自研的ADF训练方法；
 有python版本；
 斯坦福分词器
 https://nlp.stanford.edu/software/segmenter.shtml
 支持多语言分词包括中英文，提供训练模型接口，也可用已有模型，但速度较慢；
 Java实现的CRF算法；支持python
 食用方法参见：
 NLTK结合stanfordnlp工具包使用方法总结https://blog.csdn.net/lizzy05/article/details/88148097
 Stanfordnlp 安装及使用https://blog.csdn.net/lizzy05/article/details/87483539
 KCWS分词器
 https://github.com/koth/kcws
 有中文分词、词性标注功能，支持自定义词典；
 采用word2vec、Bi-LSTM、CRF算法；
 ZPar
 https://github.com/frcchang/zpar/releases
 有中文、英文、西班牙语分词、词性标注，由C++语言编写；
 IKAnalyzer
 https://github.com/wks/ik-analyzer
 有中文分词功能，支持自定义词典；
 Jcseg
 https://gitee.com/lionsoul/jcseg
 有中文分词、关键词提取、自动摘要、词性标注、实体识别等功能，支持自定义词典；
 基于mmseg、textRank、BM25等算法；
 FudanNLP
 https://github.com/FudanNLP/fnlp
 中文分词 词性标注 实体名识别 关键词抽取等；
 SnowNLP
 https://github.com/isnowfy/snownlp
 有中文分词、词性标注、情感分析、文本分类、提取关键词等功能；
 基于HMM、Naive Bayes、TextRank、tf-idf等算法；
 Python类库；
 ansj分词器
 https://github.com/NLPchina/ansj_seg
 有中文分词、人名识别、词性标注、用户自定义词典等功能；
 基于n-Gram+CRF+HMM算法；
 NLTK
 https://github.com/nltk/nltk
 擅长英文分词，也支持中文分词处理，但建议先用其他分词工具对中文语料分词，再用它的处理功能；
 庖丁解牛
 https://code.google.com/archive/p/paoding/
 支持Lucene 3.0
 
中科院NLPIR
 具有分词、词性标注、新词识别、命名实体识别、情感分析、关键词提取等功能，支持自定义词典；
 https://github.com/NLPIR-team/NLPIR/tree/master/NLPIR-Parser
 有在线以及独立客户端 有12大功能
 
新词发现：
 从文件集合中挖掘出内涵的新词语列表，可以用于用户专业词典的编撰；还可以进一步编辑标注，导入分词词典中，从而提高分词系统的准确度，并适应新的语言变化。 
  
批量分词标注：
 对原始语料进行分词、自动识别人名地名机构名等未登录词、新词标注以及词性标注。并可在分析过程中，导入用户定义的词典。
统计分析与术语翻译
 针对切分标注结果，系统可以自动地进行一元词频统计、二元词语转移概率统计（统计两个词左右连接的频次即概率）。针对常用的术语，会自动给出相应的英文解释。
文本聚类及热点分析
 能够从大规模数据中自动分析出热点事件，并提供事件话题的关键特征描述。同时适用于长文本和短信、微博等短文本的热点分析。
大数据文本分类过滤
 针对事先指定的规则或示例样本，系统自动从海量文档中筛选出符合需求的样本。
摘要提取
 能够对单篇或多篇文章，自动提炼出内容的摘要，抽取人名、地名、机构名、时间及主题关键词；方便用户快速浏览文本内容。能够对单篇文章或文章集合，提取出若干个代表文章中心思想的词汇或短语，可用于精化阅读、语义查询和快速匹配等。
敏感信息扫描分析
 根据配置的敏感关键，快速扫描各种关键词及变种。
情感分析
 针对事先指定的分析对象和示例样本，系统自动从海量文档中筛选出正负面的得分和句子样例。
文档去重
 能够快速准确地判断文件集合或数据库中是否存在相同或相似内容的记录，同时找出所有的重复记录。
HTML正文提取
 自动剔除导航性质的网页，剔除网页中的HTML标签和导航、广告等干扰性文字，返回有价值的正文内容。适用于大规模互联网信息的预处理和分析。
全文精准检索
 支持文本、数字、日期、字符串等各种数据类型，多字段的高效搜索，支持AND/OR/NOT以及NEAR邻近等查询语法，支持维语、藏语、蒙语、阿拉伯、韩语等多种少数民族语言的检索。可以无缝地与现有文本处理系统与数据库系统融合。
编码自动识别与转换
 自动识别内容的编码，并把编码统一转换为GBK编码。
 
 
其他
 
（1）腾讯文智
 （2）BosonNLP
 （3）百度NLP
 （4）阿里云NLP
 （5）新浪云
 （6）盘古分词 具有中英文分词功能，支持自定义词典；