中文分词及结巴分词原理概述

zkbhj 发表了文章 • 0 个评论 • 139 次浏览 • 2020-08-01 17:08 • 来自相关话题

中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 

基于词典的分词方法;
基于统计的分词方法。


基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:

基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法。


下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
  查看全部
中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 


基于词典的分词方法;
基于统计的分词方法。



基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:


基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法



下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
 

美团点评《O2O搜索场景下的查询理解系统》总结

zkbhj 发表了文章 • 0 个评论 • 164 次浏览 • 2020-07-28 20:57 • 来自相关话题

查询理解简介
 
QU(Query Understanding),对用户输入的Query进行一系列的分析(分词、归一化、纠错、实体识别、实体链接、异地识别、意图识别等),进而产生一系列的基础信号(POI、城市词、品牌词、类别词、经纬度、异地等)。
 
然后用这些基础信号去做更精准的召回,以及对最后排序可能会产生影响。
 
从QU到DQU,是美团NLP的平台化方向和过程。
 
NLP核心模块介绍
 
实体识别
 
对比通用搜索(百度等),电商/O2O搜索是结构化召回NER是指导召回关键信号
 

命名实体识别(Named Entity Recognition,简称NER),又称作“专名识别”,是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等。NER是信息提取、问答系统、句法分析、机器翻译、面向Semantic Web的元数据标注等应用领域的重要基础工具,在自然语言处理技术走向实用化的过程中占有重要的地位。在美团搜索场景下,NER是深度查询理解(Deep Query Understanding,简称 DQU)的底层基础信号,主要应用于搜索召回、用户意图识别、实体链接等环节,NER信号的质量,直接影响到用户的搜索体验。


实体识别模型迭代引入BERT模型
 
查询改写
 
基于知识库(精度高,召回少)->基于用户行为(整串匹配,召回一般) -> 基于翻译模型(召回高,容易语义漂移) -> 基于语义(召回高,解决语义漂移)
 翻译改写主模型:SMT
 
意图识别
 
识别用户需求,决定多业务&多形态召回
 
更多扩展阅读:
BERT在美团搜索核心排序的探索和实践
https://tech.meituan.com/2020/07/09/bert-in-meituan-search.html
美团搜索中NER技术的探索与实践
https://tech.meituan.com/2020/07/23/ner-in-meituan-nlp.html
视频地址:
https://appukvkryx45804.h5.xiaoeknow.com/v1/course/column/p_5f0eeb5ae4b04349896c0dd5?type=3&share_user_id=u_5f190d7aa0047_eBn4XWgyvu&share_type=5&scene=%E9%82%80%E8%AF%B7%E9%93%BE%E6%8E%A5&entry=2&entry_type=2001&is_redirect=1
 
  查看全部
查询理解简介
 
QU(Query Understanding),对用户输入的Query进行一系列的分析(分词、归一化、纠错、实体识别、实体链接、异地识别、意图识别等),进而产生一系列的基础信号(POI、城市词、品牌词、类别词、经纬度、异地等)。
 
然后用这些基础信号去做更精准的召回,以及对最后排序可能会产生影响。
 
从QU到DQU,是美团NLP的平台化方向和过程。
 
NLP核心模块介绍
 
实体识别
 
  • 对比通用搜索(百度等),电商/O2O搜索是结构化召回
  • NER是指导召回关键信号

 


命名实体识别(Named Entity Recognition,简称NER),又称作“专名识别”,是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等。NER是信息提取、问答系统、句法分析、机器翻译、面向Semantic Web的元数据标注等应用领域的重要基础工具,在自然语言处理技术走向实用化的过程中占有重要的地位。在美团搜索场景下,NER是深度查询理解(Deep Query Understanding,简称 DQU)的底层基础信号,主要应用于搜索召回、用户意图识别、实体链接等环节,NER信号的质量,直接影响到用户的搜索体验。



实体识别模型迭代引入BERT模型
 
查询改写
 
基于知识库(精度高,召回少)->基于用户行为(整串匹配,召回一般) -> 基于翻译模型(召回高,容易语义漂移) -> 基于语义(召回高,解决语义漂移)
 翻译改写主模型:SMT
 
意图识别
 
识别用户需求,决定多业务&多形态召回
 
更多扩展阅读:
BERT在美团搜索核心排序的探索和实践
https://tech.meituan.com/2020/07/09/bert-in-meituan-search.html
美团搜索中NER技术的探索与实践
https://tech.meituan.com/2020/07/23/ner-in-meituan-nlp.html
视频地址:
https://appukvkryx45804.h5.xiaoeknow.com/v1/course/column/p_5f0eeb5ae4b04349896c0dd5?type=3&share_user_id=u_5f190d7aa0047_eBn4XWgyvu&share_type=5&scene=%E9%82%80%E8%AF%B7%E9%93%BE%E6%8E%A5&entry=2&entry_type=2001&is_redirect=1
 
 

如何评估搜索的好坏?学习企查查搜索系统演进

zkbhj 发表了文章 • 0 个评论 • 130 次浏览 • 2020-07-27 11:43 • 来自相关话题

无论搜索怎么扩充信息,最终我们评估搜索的标准依然是回归到搜索的本身,即是否返回用户最想要的信息。怎么度量这个,如何评估搜索的好坏?如何确认搜索人员做到的精准,是否就是用户想要的?企查查对于搜索的评估主要基于如下4个指标Top3SuggestNullHitRate。我们持续关注上述这个指标的变化,并持续予以优化。

1. TOP3

我们的结果集常态的输入可能有数十条数百条,精准的搜索可能只有1条记录,最大的则能达到1万条。对于不同量级的结果集,我们关注前三条用户的点击比例,并把这个指标作为衡量整个搜索是否精度的最主要指标。

2. Suggest

用户每多输入一个字数,结果集都是在变化,他什么时候点击相当重要,如果持续不点击suggest意味着用户需要输入更多的字数,这时会判断推荐词是否是他想要的,如果该指标比例提高会有效减少用户的输入时间。这也是评估搜索是否精准的一个重要指标。

3. Null

无结果是搜索比较糟糕的体验,为了规避无结果的占比,我们除了分析用户的输入以推动纠错,兼容形近、音近等情况,还补全了诸如二次搜索等机制。

4. HitRate

整体的点击搜索比,宏观面的数据,既可以辅助分析用户的搜索行为,也可以反推当前的数据质量走势。

通过对上述指标的持续跟进,我们可以较为直观的知道整个搜索团队的工作是否在往更好的方向发展,同时也能分析到给用户的搜索习惯走势。
 
当然,关于搜索,我们除了上述各种预设的机制外,对于热门的搜索,我们也特别增加了人工干预,以规避新词更新不及时,热点事件排序不合理问题。
 
原文阅读:
https://developer.aliyun.com/article/720572
  查看全部
无论搜索怎么扩充信息,最终我们评估搜索的标准依然是回归到搜索的本身,即是否返回用户最想要的信息。怎么度量这个,如何评估搜索的好坏?如何确认搜索人员做到的精准,是否就是用户想要的?企查查对于搜索的评估主要基于如下4个指标Top3SuggestNullHitRate。我们持续关注上述这个指标的变化,并持续予以优化。

1. TOP3

我们的结果集常态的输入可能有数十条数百条,精准的搜索可能只有1条记录,最大的则能达到1万条。对于不同量级的结果集,我们关注前三条用户的点击比例,并把这个指标作为衡量整个搜索是否精度的最主要指标。

2. Suggest

用户每多输入一个字数,结果集都是在变化,他什么时候点击相当重要,如果持续不点击suggest意味着用户需要输入更多的字数,这时会判断推荐词是否是他想要的,如果该指标比例提高会有效减少用户的输入时间。这也是评估搜索是否精准的一个重要指标。

3. Null

无结果是搜索比较糟糕的体验,为了规避无结果的占比,我们除了分析用户的输入以推动纠错,兼容形近、音近等情况,还补全了诸如二次搜索等机制。

4. HitRate

整体的点击搜索比,宏观面的数据,既可以辅助分析用户的搜索行为,也可以反推当前的数据质量走势。

通过对上述指标的持续跟进,我们可以较为直观的知道整个搜索团队的工作是否在往更好的方向发展,同时也能分析到给用户的搜索习惯走势。
 
当然,关于搜索,我们除了上述各种预设的机制外,对于热门的搜索,我们也特别增加了人工干预,以规避新词更新不及时,热点事件排序不合理问题。
 
原文阅读:
https://developer.aliyun.com/article/720572