几种分词算法对比

• 句法语义分析：对于给定的句子，进行分词、词性标记、命名实体识别和链接、句法分析、语义角色识别和多义词消歧
• 信息抽取：从给定文本中抽取重要的信息。比如时间、地点、人物、事件、原因、结果、数字、日期、货币、专有名词等。涉及到实体识别、时间抽取、因果关系抽取等关键技术
• 文本挖掘：包括文本聚类、分类、信息抽取、摘要、情感分析，以及对挖掘的信息和知识的可视化、交互化表达界面。目前主流的技术都是基于统计机器学习的
• 问答系统(我目前研究的方向)： 对一个自然语言表达的问题，由问答系统给出一个精准的答案。需要对自然语言查询语句进行某种程度的语义分析，包括实体链接、关系识别，形成逻辑表达式，然后到知识库中查找可能的候选答案并通过一个排序机制找出最佳的答案——目前基于知识图谱的问答系统还是挺好用的

分词是中文NLP的基础。

基于词表的分词算法

基于词典的分词过度依赖词典和规则库，因此对于歧义词和未登录词的识别能力较低；其优点是速度快，效率高

正向最大匹配法

正向最大匹配法，对于输入的一段文本从左至右、以贪心的方式切分出当前位置上长度最大的词。正向最大匹配法是基于词典的分词方法，其分词原理是：单词的颗粒度越大，所能表示的含义越确切。

def cut_words(raw_sentence, word_dic):
    max_length = max(len(word) for word in words_dic)  # 统计词典中最长的词
    sentence = raw_sentence.strip()
    words_length = len(sentence)
    cut_word_list = []  # 存储切分好的词
    while words_length > 0:
       max_cut_length = min(max_length,words_length)
       subsentence = sentence[0:max_cut_length]
       while max_cut_length > 0:
           if subsentence in words_dic:
               cut_word_list.append(subsentence)
               break
           elif max_cut_length == 1:
                cut_word_list.append(subsentence)
                break
           else:
                max_cut_length -= 1
                subsentence = subsentence[0:max_cut_length]
       sentence = sentence[max_cut_length:]
       words_length -= max_cut_length
    words = "/".join(cut_word_list)
    return words

逆向最大匹配法

从右至左。

只需改变切分方式 subsentence = sentence[-max_cut_length:] sentence = sentence[0:-max_cut_length]

并将切分好的序列逆序 cut_word_list.reverse() , 再join即可

结果分析

请输入您要分词的序列
我毕业于中南财经政法大学金融系，现在在中国科技大学学软件工程。
分词结果
我/毕业/于/中南财经政法大学/金融系/，/现在/在/中国/科技/大/学学/软件工程/。

可以看出：从后向前的分词方法有很大的缺陷

FMM和BMM难以解决歧义问题——解决：双向最大匹配法

双向最大匹配算法

双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。

启发式规则：

1. 如果正反向分词结果词数不同，则取分词数量较少的那个——单词的颗粒度越大，所能表示的含义越确切
2. 如果分词结果词数相同
   • 分词结果相同，就说明没有歧义，可返回任意一个
   • 分词结果不同，返回其中单字较少的那个

实现：将FMM和BMM的返回值改为切分好的序列，经比较之后返回更为准确的分词结果

import FMM2
import BMM2

def bimm_cut_words(raw_sentence, words_dic):
    fmm_word_list = FMM2.cut_words(raw_sentence, words_dic)
    bmm_word_list = BMM2.cut_words(raw_sentence, words_dic)
    fmm_word_list_len = len(fmm_word_list)
    bmm_word_list_len = len(bmm_word_list)
    if bmm_word_list_len != fmm_word_list_len:
        if bmm_word_list_len < fmm_word_list_len:
            return bmm_word_list
        else:
            return fmm_word_list
    else:
        fsingle = 0
        bsingle = 0
        issame = True
        for i in range(len(fmm_word_list)):
            if fmm_word_list[i] != bmm_word_list[i]:
                issame = False
            if len(fmm_word_list[i]) == 1:
                fsingle += 1
            if len(bmm_word_list[i]) == 1:
                bsingle += 1
        if issame:
            return fmm_word_list
        elif fsingle > bsingle:
            return bmm_word_list
        else:
            return fmm_word_list

基于词典的问题：即使只是去切分一个句子，仍然需要2~3秒的处理时间，这在处理大文本的时候，很显然将成为性能的瓶颈。

分析算法可知，基于词典的遍历，在匹配时也是用的蛮力搜索，可以说是相当的暴力，基本上没有任何优化，只实现了基本的功能。

基于统计模型的分词算法

基于N-gram语言模型的分词方法

利用统计信息找出一条概率最大的路径。

当样本量很大的时候，基于大数定律，一个短语或者词语出现的概率可以用其频率来表示。——用统计方法的前提是有大量的样本。同时基于1阶马尔科夫假设：一个词wi出现的概率只与它前面的wi-1有关

$P(w_i | w_{i-1}) = count (w_i,w_{i-1})/count(w_{i-1})$

基于序列标注的分词算法

基于HMM的分词方法(生成式)

把分词问题转为字的分类问题(序列标注问题)——由字构词，不依赖事先编制好的词表，但仍然需要分好词的训练语料

单字S，开始B-中间M-结尾E ， 已知观察序列求对应的形式化序列

基于CRF的分词方法(判别式)

同HMM一样，也是基于序列标注，但它是一个判别式模型。不仅考虑了文字词语出现的频率信息，同时考虑上下文语境，具备较好的学习能力，因此其对歧义词和未登录词的识别都具有良好的效果；其不足之处是训练周期较长，计算量较大

分词所使用的是Linear-CRF，它由一组特征函数组成，包括权重λ和特征函数f，特征函数f的输入是整个句子s、当前posi、前一个词位li-1，当前词位li

HMM VS 最大熵 VS CRF

• CRF， HMM都常用来做序列标注的建模，像分词、词性标注，以及命名实体标注
• 隐马模型一个最大的缺点就是由于其输出独立性假设，导致其不能考虑上下文的特征，限制了特征的选择
• 最大熵隐马模型则解决了隐马的问题，可以任意选择特征，但由于其在每一节点都要进行归一化，所以只能找到局部的最优值，同时也带来了标记偏见的问题，即凡是训练语料中未出现的情况全都忽略掉
• 条件随机场则很好的解决了这一问题，他并不在每一个节点进行归一化，而是所有特征进行全局归一化，因此可以求得全局的最优值。

基于深度学习的端到端的分词方法

需要大量的语料

输入层是一个embedding层，经过双向LSTM网络编码，输出层是一个CRF层。经过双向LSTM网络输出的实际上是当前位置对于各词性的得分， CRF层的意义是对词性得分加上前一位置的词性概率转移的约束，其好处是引入一些语法规则的先验信息

学习来源：网页云课堂《动手学中文分词》