文档章节

jieba 源码解析

正_午
 正_午
发布于 2016/09/27 23:16
字数 1985
阅读 148
收藏 0

阅读动机

jieba分词是Python 里面几个比较流行的中文分词工具之一。为了理解分词工具的工作原理,以及实现细节对jieba进行了详细的阅读。

读代码之前,我有几个问题是这样的:

  • 分词工具的实现都有哪几个步骤?
  • 结巴分词的文档说是使用了HMM模型,但是HMM 模型是如何运用在分词工具中的?,以及模型是如何产生的?
  • 几乎所有的分词工具都支持用户添加词库,但是用户词库到底在分词过程中扮演什么角色?

简介

jieba 分词支持三种分词模式,官方文档给出了如下的Example

import jieba

seg_list = jieba.cut("我来到北京清华大学", cut_all=True)
print("Full Mode: " + "/ ".join(seg_list))  # 全模式

seg_list = jieba.cut("我来到北京清华大学", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list))  # 精确模式

seg_list = jieba.cut("他来到了网易杭研大厦")  # 默认是精确模式
print(", ".join(seg_list))

seg_list = jieba.cut_for_search("小明硕士毕业于中国科学院计算所,后在日本京都大学深造")  # 搜索引擎模式
print(", ".join(seg_list))

考虑到文章篇幅的限制,我会详细解读默认模式也就是jieba.cut方法的所有实现。 阅读过程中会涉及一些算法原理,本文不做详细解释。

宏观逻辑

上面面的流程图很粗糙,但是很好的说明了大概的步骤。 首先使用概率无向图,获得最大概率路径.概率无向图的构建完全依赖于字典,最大概率路径求解也是依赖字典中的词频。 最后使用HMM模型来解决未登录词(Out Of Vocabulary) ,所以在整个过程如果没有模型也是可以的,只要你有一个很好的词典。最大概率路径的求解还有很多方法,记得HanLP的求解就有实现最短路径。

粗分

首先会使用正则将文本切分,正则什么样?就跟现则的是默认模式还是全模式。正则如下:

re_han_default = re.compile("([\u4E00-\u9FD5a-zA-Z0-9+#&\._]+)", re.U)
re_han_cut_all = re.compile("([\u4E00-\u9FD5]+)", re.U)

到底有什么区别: 我写了个测试:

test_str = u'我在重庆abc,他也在重庆? 1234你在重庆吗'
print (re_han_default.split(test_str))
print (re_han_cut_all.split(test_str))

输出:

['', '我在重庆abc', ',', '他也在重庆', '? ', '1234你在重庆吗', '']
['', '我在重庆', 'abc,', '他也在重庆', '? 1234', '你在重庆吗', '']

上面输出的list 里面每一个被成为block。

细分

对粗分产生的blok ‘abc’这样的不能被re.han匹配的会直接作为结果反回。对于和中文连在一起的会进入下一个阶段细分。

DAG构建

细分的第一步是构建 DAG 即有向无环图。构建的核心代码如下:

def get_DAG(self, sentence):
        self.check_initialized() # 初始化,加载词典
        DAG = {}
        N = len(sentence)
        for k in xrange(N):
            tmplist = []
            i = k
            frag = sentence[k]
            while i < N and frag in self.FREQ:
                if self.FREQ[frag]:
                    tmplist.append(i)
                i += 1
                frag = sentence[k:i + 1]
            if not tmplist:
                tmplist.append(k)
            DAG[k] = tmplist
        return DAG

怎么个意思呢: 举个例子 我来到北京清华大学 产生的DAG 结果如下:

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

使用dict 来存储图数据结构。字典中的key 是没个字对应句子的index,后面的value 是一个list就是可达的路径。比如{1:[1,2]}意思就是“来”和“来到”这两个词在词典中存在。其他的类推。

图的产生依赖于self.FREQ这个变量,这是存储字典的,其结构是词做key ,词出现次数做value 的dict. 所以词典的好坏对分词结果会有很大的影响。如果根本不存在的路径给连上了,应该连上的没有连上。后面的HMM模型也是没办法解决的后者,当然最大概率路径会解决部分第一个问题,但是都是有限的。所以词典是相当关键的。

最大概率路径求解

有了上面的DAG 下面求是求解最大概率路径。这个问题有很多中方法,jieba 使用的是动态规划。先不解释动态规划是什么,直接看代码,

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

真个过程就上面几行。关键就在max 那一句。这个问题不在这里展开。但是有个小的技巧说下:在对很小的数据进行操作的时候,Python 也是可能向下溢出的,什么意思看下面的例子:

b = 0.0000001
print b**100

结果会打印0.0 所有有个方法就是取log 。这个方法在很多地方都是有用的。 上面还用到了连个tuple比较这一技巧。

求解的结果如果分词时候参数设置的不适用HMM模型,到这里就结束了。求解结果部分如下:key 同样是对应的index.第二个就代表的是来到这个词。

{0: (-32.587853155857076, 0), 1: (-27.379629658355885, 2),}

未登录词

上面的最大概率在一定程度上解决了歧义问题,但是在分词里面还有另外一个问题未登录词问题也叫OOV(Out Of Vocabulary). jieba 使用HMM来识别未登录词。 比如: “我来到誉存科技” 这句话,产生的最大概率路径是

{0: (-42.29693140266269, 0), 1: (-37.0887079051615, 2), 2: (-33.93639839927486, 2), 3: (-28.257272562332492, 3), 4: (-17.872975353951055, 4), 5: (-8.250710549196151, 6), 6: (-10.881580216048834, 6), 7: (0, 0)}

看到3,和4 都是独立的词,如果不使用HMM 这个词就会被分成两个字。其逻辑就是把多个连续的单字组合成新的blok 使用HMM来切分。HMM到底怎么切分呢?

HMM

HMM 隐马模型的定义自己可以去查,就算查完你也不一定能说清楚到底在分词的时候怎么使用的,但是不查绝对不知道。 在分词之前语料会被标注,标注的方式有很多中。其中比较多的是BMES对应的是B(begin)词的开头,M(Middle)词的中间,E(End)词的结束,S(Single)单个的词 HMM有几个概念,和分词这个具体问题的对应关系如下:

  • 状态序列(state sequence):BMES 这些状态
  • 观测序列(observation sequence):就是看到的需要分词的句子,所有的字组成一个序列。

现在的问题就是一直观测序列求状态序列。但是第一部我们需要建立HMM模型。 HMM 有三个基本组成: 初始概率状态概率分布A 状态转移矩阵pi 观测概率分布B

如果有了上面三个元素一个HMM模型就是定好了。当然还有HMM模型有很多假设,此处省略。 jieba 是如何得到这三个变量的了。这就是HMM的学习问题 了。在标注好的语料之上。可以使用极大似然估计来估计这三个参数。这里也看到,语料是关键因素,语料的质量决定这三个参数。其实估计的过程不管其中的原理就是一些统计计算。jieba 把这三个元素分别存贮在三个py文件中:

prob_start.py: 初始状态概率 prob_trans.py: 状态转移 prob_emit.py: 观测概率分布

看看 prob_start:

P={'B': -0.26268660809250016,
 'E': -3.14e+100,
 'M': -3.14e+100,
 'S': -1.4652633398537678}

-3.14e+100表示的是无穷小。意思就是第一个字不可能是E,或者M.只可能是B,S具体是多少,使用语料中的频率做估计。

另外两个元素用类似的方法在语料之上很容易得到。

有了上面的饮马模型,但是如何通过观测序列求最有可能的状态序列?这时候就到Viterbi algorithm出场了。具体也不展开,反正很简单。

可访问正午的博客查看更多内容

© 著作权归作者所有

共有 人打赏支持
正_午
粉丝 7
博文 4
码字总数 8815
作品 2
恩施
私信 提问
【NLP】【二】jieba源码分析之分词

【一】词典加载 利用jieba进行分词时,jieba会自动加载词典,这里jieba使用python中的字典数据结构进行字典数据的存储,其中key为word,value为frequency即词频。 1. jieba中的词典如下: ji...

muqiusangyang
11/02
0
0
使用了jieba分词提取权重最大的关键词的示例代码,却始终不出效果。

本人新手刚接触python不久,由于近期用到分词也才接触到jieba,关于返回权重最大关键词我参照了给出的源码 https://github.com/fxsjy/jieba/blob/master/test/extracttags.py 现在不出效果,...

metalhammer
2014/01/09
681
1
jieba中文分词源码分析(一)

一、缘由 接触自然语言处理(NLP)有段时间,理论知识有些了解,挺想动手写些东西,想想开源界关于NLP的东西肯定不少,其中分词是NLP的基础,遂在网上找了些资源,其中结巴分词是国内程序员用p...

gfsfg8545
2015/09/03
0
0
【NLP】【三】jieba源码分析之关键字提取(TF-IDF/TextRank)

【一】综述 利用jieba进行关键字提取时,有两种接口。一个基于TF-IDF算法,一个基于TextRank算法。TF-IDF算法,完全基于词频统计来计算词的权重,然后排序,在返回TopK个词作为关键字。TextR...

muqiusangyang
11/05
0
0
【NLP】【一】中文分词之jieba

声明:本文参考jieba官方文档而成,官方链接:https://github.com/fxsjy/jieba 【一】jieba安装 pip install jieba 【二】jieba简介 简介可见jieba官方说明:https://pypi.org/project/jieb...

muqiusangyang
10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

强化学习在美团“猜你喜欢”的实践

1 概述 “猜你喜欢”是美团流量最大的推荐展位,位于首页最下方,产品形态为信息流,承担了帮助用户完成意图转化、发现兴趣、并向美团点评各个业务方导流的责任。经过多年迭代,目前“猜你喜...

美团技术团队
15分钟前
0
0
docker - 常用命令

1. docker服务的启动、停止、重启 [root@localhost ~]# service docker restartRedirecting to /bin/systemctl restart docker.service[root@localhost ~]# service docker stopRedir......

细肉云吞
18分钟前
1
0
安装CentOS 6.5 系统

一、安装CentOS 6.5 系统 1、选择第一个 "Install or upgrade an existing system" 2、选择跳过 “Skip” 3、直接下一步 4、建议初学者选择中文的,工作中选择 “English” 5、键盘选择 “美...

寰宇01
31分钟前
0
0
AR+ 实时音视频通话,虚拟与现实无缝结合

今年中旬 Google 在万众期待下推出了 ARCore,能将现实与数码完美无缝地融合在一起,丰富我们的现实世界。通过它开发者可以更加快速方便地在 Android 平台开发 AR 应用,凭借 AR 技术大量产品...

七牛云
31分钟前
0
0
手把手教你实现一个 Vue 进度条组件!

最近在个人的项目中,想对页面之间跳转的过程进行优化,想到了很多文档或 npm 等都用到的页面跳转进度条,于是便想自己去实现一个,特此记录。 来看下 npm 搜索组件时候的效果: so 下面咱们...

我的卡
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部