非主流自然语言处理——遗忘算法系列(三):分词

Deep Learning Specialization on Coursera

一、前言

  前面介绍了词库的自动生成的方法,本文介绍如何利用前文所生成的词库进行分词。

二、分词的原理

  分词的原理,可以参看吴军老师《数学之美》中的相关章节,这里摘取Google黑板报版本中的部分:
  分词原理
  从上文中,可以知道分词的任务目标:给出一个句子S,找到一种分词方案,使下面公式中的P(S)最大:
  分词原理
  不过,联合概率求起来很困难,这种情况我们通常作马尔可夫假设,以简化问题,即:任意一个词wi的出现概率只同它前面的词 wi-1 有关。
  关于这个问题,吴军老师讲的深入浅出,整段摘录如下:
  分词原理
  另外,如果我们假设一个词与其他词都不相关,即相互独立时,此时公式最简,如下:
  分词原理
  这个假设分词无关的公式,也是本文所介绍的分词算法所使用的。

三、算法分析

  问:假设分词结果中各词相互无关是否可行?
  答:可行,前提是使用遗忘算法系列(二)中所述方法生成的词库,理由如下:
  分析ICTCLAS广受好评的分词系统的免费版源码,可以发现,在这套由张华平、刘群两位博士所开发分词系统的算法中假设了:分词结果中词只与其前面的一个词有关。
  回忆我们词库生成的过程可以知道,如果相邻的两个词紧密相关,那么这两个词会连为一个粗粒度的词被加入词库中,如:除“清华”、“大学”会是单独的词外,“清华大学”也会是一个词,分词过程中具体选用那种,则由它们的概率来决定。
  也就是说,我们在生成词库的同时,已经隐含的完成了相关性训练。
  关于ICTCLAS源码分析的文章,可以参看吕震宇博文:《天书般的ICTCLAS分词系统代码》。
  问:如何实现分词?
  答:基于前文生成的词库,我们可以假设分词结果相互无关,分词过程就比较简单,使用下面的步骤可以O(N)级时间,单遍扫描完成分词:
  逐字扫描句子,从词库中查出限定字长内,以该字结尾的所有词,分别计算其中的词与该词之前各词的概率乘积,取结果值最大的词,分别缓存下当前字所在位置的最大概率积,以及对应的分词结果。
  重复上面的步骤,直到句子扫描完毕,最后一字位置所得到即为整句分词结果。
  3、算法特点
    3.1、无监督学习;
    3.2、O(N)级时间复杂度;
    3.3、词库自维护,程序可无需人工参与的情况下,自行发现并添加新词、调整词频、清理错词、移除生僻词,保持词典大小适当;
    3.4、领域自适应:领域变化时,词条、词频自适应的随之调整;
    3.5、支持多语种混合分词。

四、演示程序下载

  演示程序与词库生成的相同:

五、联系方式:

  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com
Deep Learning Specialization on Coursera

非主流自然语言处理——遗忘算法系列(三):分词》上有18条评论

  1. jsp

    您好,真的很厉害!我想向您具体请教一下制作这个程序的过程,可以吗?本人也对这方面很感兴趣,刚刚入门。

    [回复]

    老憨 回复:

    当然可以,文中有源码(C#)和Demo的下载地址,还有我的联系方式,可以通过邮件讨论,谢谢关注。

    [回复]

  2. TM

    有和主流方案的效果进行比较么

    [回复]

    老憨 回复:

    原始算法不优化的情况下,分词效果依赖于词库生成的所用文本的数量和质量,通常来说不如主流的分词效果。

    [回复]

    bzy 回复:

    请问你有没有做过评测?如果做过是什么语料,规模怎样?未登录词识别效果怎样?歧义识别效果怎样?

    [回复]

    老憨 回复:

    没有正式评测,可以下载Demo,使用内置的数据或自行提供数据体验下,词库生成时训练文本尽量大于200M。

    ff 回复:

    效果不好就不用再发表了吧。。。

    [回复]

    老憨 回复:

    抛砖引玉。。

  3. bzy

    请问有没有评测的结果。未登录词的识别怎么样?歧义识别效果怎样?

    [回复]

    老憨 回复:

    词库是自动生成,动态维护的,对程序来说所有词都是“未登录词”。

    [回复]

  4. bzy

    请问你有没有做过评测?如果做过是什么语料,规模怎样?未登录词识别效果怎样?歧义识别效果怎样?

    [回复]

    老憨 回复:

    没做过评测,目测90%以上的准确率,在公司项目中使用,满足工程需求。

    [回复]

    ideaquery 回复:

    欢迎继续发表,每一个思路都可能是创新的火花

    [回复]

    老憨 回复:

    谢谢鼓励,欢迎交流讨论,碰撞更多火花。

  5. 老憨 文章作者

    补充说明一下:

    词库生成时训练语料250M以上较好,使用这个词库分词,准确率应在90%以上,本文以讨论算法为主,原始分词代码没有做任何针对性的优化(包括标点、数字、英文的特别处理),Demo中分词代码不足50行,并非提供一个商用分词程序。

    [回复]

  6. misswen

    逐字扫描句子,从词库中查出限定字长内,以该字结尾的所有词,分别计算其中的词与该词之前各词的概率乘积,取结果值最大的词,分别缓存下当前字所在位置的最大概率积,以及对应的分词结果。

    这个描述不是很懂啊,可不可以细致描述下

    [回复]

    老憨 回复:

    举个例子:“苹果是什么颜色的?”
    并假设最大词长为4。
    步骤如下:

    1、逐字扫描各字,限定字长(假如设置为4)内,以该字结尾的所有字串:
    【苹】苹
    【果】果,苹果
    【是】是,果是,苹果是
    【什】什,是什,果是什,苹果是什
    【么】么,什么,是什么,果是什么

    2、这样得到的串并非都是词,通过检查词库来确定是否存在,得到:
    【苹】苹
    【果】果,苹果
    【是】是,苹果是
    【什】什
    【么】么,什么,是什么

    3、计算各词与该词之前各词的概率乘积,取概率连积最大的那种,作为截止到当前字的分词方案。PS:某个词的概率等于该词词频除于词库总词频。

    【苹】
    苹:p(苹)

    {保存当前字位置的最大分词方案及概率积:《0,p(苹)》}

    【果】
    果:p(苹)*p(果) //“果”前一个位置的最大概率连积为《0,p(苹)》
    苹果:p(苹果)//“苹果”前一个位置已到句首

    //比较所有词对应的概率,取最大的进行保存
    {保存当前字位置的最大分词方案及概率积:《1,p(苹果)》}

    【是】
    是:p(苹果)*p(是) //“是”前一个位置的最大概率连积为《1,p(苹果)》
    苹果是:p(苹果是)

    {保存当前字位置的最大分词方案及概率积:《2,p(苹果)*p(是)》}

    【什】
    什:p(苹果)*p(是)*p(什)
    {保存当前字位置的最大分词方案及概率积:《3,p(苹果)*p(是)*p(什)》}

    【么】
    么:p(苹果)*p(是)*p(什)*p(么)
    什么:p(苹果)*p(是)*p(什么)
    是什么:p(苹果)*p(是什么)

    //以上都是用各词前一个位置的概率连积乘以本词概率

    {保存当前字位置的最大分词方案及概率积:《4,p(苹果)*p(是)*p(什么)》}

    4、如此,直到句子结尾,所得尾字最大的分词方案,即为整句的结果。

    备注:如果某个字不存在任何词,则保留该字,并以词频1,参与概率计算。

    [回复]

  7. zhoucc

    感谢分享,比较完整的一个分词方案。准备用python实现一遍,测试下效果

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注