资讯专栏INFORMATION COLUMN

结巴分词原理

zzbo / 2724人阅读

摘要:我来到北京清华大学对应的状态应该为其实和的区别就是对未成功切分的部分,没有使用进行分词。

介绍

结巴分词是一个受大家喜爱的分词库,源码地址为github,今天我们就跟进源码,看一下结巴分词的原理

原理

</>复制代码

  1. def cut(self, sentence, cut_all=False, HMM=True):
  2. """
  3. The main function that segments an entire sentence that contains
  4. Chinese characters into separated words.
  5. Parameter:
  6. - sentence: The str(unicode) to be segmented.
  7. - cut_all: Model type. True for full pattern, False for accurate pattern.
  8. - HMM: Whether to use the Hidden Markov Model.
  9. """

使用结巴分词的时候,有三种模式,这三种模式的进入条件分别为:

</>复制代码

  1. if cut_all:
  2. cut_block = self.__cut_all
  3. elif HMM:
  4. cut_block = self.__cut_DAG
  5. else:
  6. cut_block = self.__cut_DAG_NO_HMM

首先我们看一下这三种模式

__cut_all:

原句:我来到北京清华大学 结果:我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学

原句:他来到了网易杭研大厦 结果:他/ 来到/ 了/ 网易/ 杭/ 研/ 大厦

__cut_DAG:

原句:我来到北京清华大学 结果:我/ 来到/ 北京/ 清华大学

原句:他来到了网易杭研大厦 结果:他/ 来到/ 了/ 网易/ 杭研/ 大厦

__cut_DAG_NO_HMM:

原句:我来到北京清华大学 结果:我/ 来到/ 北京/ 清华大学

原句:他来到了网易杭研大厦 结果:他/ 来到/ 了/ 网易/ 杭/ 研/ 大厦

下面我们就来分析一下这三种模式:
这三种模式有一个共同点,第一步都是先构造DAG,也就是构造有向无环图。
源码如下:

</>复制代码

  1. def get_DAG(self, sentence):
  2. self.check_initialized()
  3. DAG = {}
  4. N = len(sentence)
  5. for k in xrange(N):
  6. tmplist = []
  7. i = k
  8. frag = sentence[k]
  9. while i < N and frag in self.FREQ:
  10. if self.FREQ[frag]:
  11. tmplist.append(i)
  12. i += 1
  13. frag = sentence[k:i + 1]
  14. if not tmplist:
  15. tmplist.append(k)
  16. DAG[k] = tmplist
  17. return DAG

如果sentence是"我来到北京清华大学‘,那么DAG为

</>复制代码

  1. {0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}

直观上来看,DAG[5]=[5,6,8]的意思就是,以’清‘开头的话,分别以5、6、8结束时,可以是一个词语,即’清‘、’清华‘、’清华大学‘
get_DAG方法中,最重要的也就是self.FREQ了,它是怎么来的呢?


其实就是通过jieba目录下,dict.txt文件来产生的self.FREQ,方法如下:
dict.txt共有349046行,每一行格式为:

</>复制代码

  1. 一 217830 m
  2. 一一 1670 m
  3. 一一二 11 m
  4. 一一例 3 m
  5. 一一分 8 m
  6. 一一列举 34 i

第一部分为词语,第二部分为该词出现的频率,第三部分为该词的词性。
以读取’一一列举‘为例子,首先执行self.FREQ["一一列举"]=34,然后会检查’一‘、’一一‘、’一一列‘、’一一列举‘之前是否在self.FREQ中存储过,如果之前存储过,则跳过,否则执行self.FREQ["一"]=0,self.FREQ["一一"]=0,self.FREQ["一一列"]=0
所以self.FREQ中不止存储了正常的词语和它出现的次数,同时也存储了所有词语的前缀,并将前缀出现的次数设置为0,以和正常词语区别开。

好了,现在DAG这部分我们介绍完了,然后我们分开来介绍一下这三种模式:

__cut_all

源码如下:

</>复制代码

  1. def __cut_all(self, sentence):
  2. dag = self.get_DAG(sentence)
  3. old_j = -1
  4. for k, L in iteritems(dag):
  5. if len(L) == 1 and k > old_j:
  6. yield sentence[k:L[0] + 1]
  7. old_j = L[0]
  8. else:
  9. for j in L:
  10. if j > k:
  11. yield sentence[k:j + 1]
  12. old_j = j

这个具体的遍历方式我们就不细说了,大家自行看源码吧

__cut_DAG

</>复制代码

  1. def __cut_DAG(self, sentence):
  2. DAG = self.get_DAG(sentence)
  3. route = {}
  4. self.calc(sentence, DAG, route)
  5. ......

首先我们先看一下self.calc方法

</>复制代码

  1. def calc(self, sentence, DAG, route):
  2. N = len(sentence)
  3. route[N] = (0, 0)
  4. logtotal = log(self.total)
  5. for idx in xrange(N - 1, -1, -1):
  6. route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
  7. logtotal + route[x + 1][0], x) for x in DAG[idx])

这里使用了一个技巧,也就是log(a) + log(b) = log(ab),从而巧妙的避过了乘法,也就避免了溢出的风险。
其实calc函数就是实现了vertibi算法,不了解vertibi算法的同学自行百度吧。

然后再贴上整个__cut_DAG的源码:

</>复制代码

  1. def __cut_DAG(self, sentence):
  2. DAG = self.get_DAG(sentence)
  3. route = {}
  4. self.calc(sentence, DAG, route)
  5. x = 0
  6. buf = ""
  7. N = len(sentence)
  8. while x < N:
  9. y = route[x][1] + 1
  10. l_word = sentence[x:y]
  11. if y - x == 1:
  12. buf += l_word
  13. else:
  14. if buf:
  15. if len(buf) == 1:
  16. yield buf
  17. buf = ""
  18. else:
  19. if not self.FREQ.get(buf):
  20. recognized = finalseg.cut(buf)
  21. for t in recognized:
  22. yield t
  23. else:
  24. for elem in buf:
  25. yield elem
  26. buf = ""
  27. yield l_word
  28. x = y
  29. if buf:
  30. if len(buf) == 1:
  31. yield buf
  32. elif not self.FREQ.get(buf):
  33. recognized = finalseg.cut(buf)
  34. for t in recognized:
  35. yield t
  36. else:
  37. for elem in buf:
  38. yield elem

其中,重点关注这一部分

</>复制代码

  1. if not self.FREQ.get(buf):
  2. recognized = finalseg.cut(buf)
  3. for t in recognized:
  4. yield t

什么时候会进入finalseg.cut(buf)呢?实际上,就是当遇到一些dict.txt中没出现的词的时候,才会进入这个函数:
在这个函数中,就是使用HMM的方法,对这些未识别成功的词进行标注,然后我们来介绍一下项目中相关的内容:


其中,prob_start.py存储的是HMM的起始状态相关的信息,文件中的数字都经过log处理过:

</>复制代码

  1. P={"B": -0.26268660809250016,
  2. "E": -3.14e+100,
  3. "M": -3.14e+100,
  4. "S": -1.4652633398537678}

B代表begin,E代表end,M代表middle,S代表single。所以在开始时,HMM的状态只可能是S或者B,而E和M为负无穷
prob_trans.py存储的是状态转移矩阵:

</>复制代码

  1. P={"B": {"E": -0.510825623765990, "M": -0.916290731874155},
  2. "E": {"B": -0.5897149736854513, "S": -0.8085250474669937},
  3. "M": {"E": -0.33344856811948514, "M": -1.2603623820268226},
  4. "S": {"B": -0.7211965654669841, "S": -0.6658631448798212}}

prob_emit.py中存储的是在该状态下出现该汉字的概率,例如p("刘"|S)=-0.916

</>复制代码

  1. P={"B": {"u4e00": -3.6544978750449433,
  2. "u4e01": -8.125041941842026,
  3. "u4e03": -7.817392401429855,
  4. "u4e07": -6.3096425804013165,
  5. "u4e08": -8.866689067453933,
  6. "u4e09": -5.932085850549891,
  7. "u4e0a": -5.739552583325728,
  8. "u4e0b": -5.997089097239644,
  9. "u4e0d": -4.274262055936421,
  10. "u4e0e": -8.355569307500769,
  11. ......

通过这种方式,也就可以进行分词了。
‘我/ 来到/ 北京/ 清华大学’对应的状态应该为"SBEBEBMME"

__cut_DAG_NO_HMM

其实__cut_DAG_NO_HMM和__cut_DAG的区别就是:对vertibi未成功切分的部分,__cut_DAG_NO_HMM没有使用HMM进行分词。源码如下:

</>复制代码

  1. def __cut_DAG_NO_HMM(self, sentence):
  2. DAG = self.get_DAG(sentence)
  3. route = {}
  4. self.calc(sentence, DAG, route)
  5. x = 0
  6. N = len(sentence)
  7. buf = ""
  8. while x < N:
  9. y = route[x][1] + 1
  10. l_word = sentence[x:y]
  11. if re_eng.match(l_word) and len(l_word) == 1:
  12. buf += l_word
  13. x = y
  14. else:
  15. if buf:
  16. yield buf
  17. buf = ""
  18. yield l_word
  19. x = y
  20. if buf:
  21. yield buf
  22. buf = ""

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/44926.html

相关文章

  • 使用cjieba(结巴分词库)实现php扩展中文分词-支持php5, php7

    摘要:作者地址编译安装配置指向库目录使用小明硕士毕业于中国科学院计算所,后在日本京都大学深造小明硕士毕业于中国科学院计算所,后在日本京都大学深造效果小明硕士毕业于中国科学学院科学院中国科学院计算计算所,后在日本京都大学日本京都大学深造计算所 作者git地址:https://github.com/jonnywang/... 编译安装 git clone https://github.com/j...

    fevin 评论0 收藏0
  • 使用cjieba(结巴分词库)实现php扩展中文分词

    摘要:编译安装配置指向库目录使用小明硕士毕业于中国科学院计算所,后在日本京都大学深造小明硕士毕业于中国科学院计算所,后在日本京都大学深造效果小明硕士毕业于中国科学学院科学院中国科学院计算计算所,后在日本京都大学日本京都大学深造计算所小明京都 编译安装 git clone https://github.com/jonnywang/jz.git cd jz/cjieba make cd .. p...

    ethernet 评论0 收藏0
  • 结巴中文分词之PHP扩展

    摘要:指向库目录小明硕士毕业于中国科学院计算所,后在日本京都大学深造小明硕士毕业于中国科学学院科学院中国科学院计算计算所,后在日本京都大学京都大学深造小明硕士毕业于中国科学院计算所,后在日本京都大学深造计算所小明京都大学深造硕士中国科学院他心理健 https://github.com/jonnywang/... functions array jieba(string $text, bool...

    _Zhao 评论0 收藏0
  • B 站直播间数据爬虫

    摘要:站的弹幕服务器也有类似的机制,随便打开一个未开播的直播间,抓包将看到每隔左右会给服务端发送一个心跳包,协议头第四部分的值从修改为即可。 原文:B 站直播间数据爬虫, 欢迎转载项目地址:bilibili-live-crawler 前言 起因 去年在 B 站发现一个后期超强的 UP 主:修仙不倒大小眼,专出 PDD 这样知名主播的吃鸡精彩集锦,涨粉超快。于是想怎么做这样的 UP,遇到的第一...

    xuweijian 评论0 收藏0

发表评论

0条评论

zzbo

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<