大家好，又见面了，我是你们的朋友全栈君。
目前常用的分词工具很多，包括盘古分词、Yaha分词、Jieba分词、清华THULAC等，现在项目使用的分词方法是结巴分词，本次来介绍一下。
安装就不说了可以直接pip install jieba或者pycharm的setting中添加即可。通过 import jieba 来引用
如下为jieba代码结构及子目录与相应功能的对应；
.
├── analyse # 短语抽取模块
│ ├── analyzer.py
│ ├── idf.txt
│ ├── __init__.py
│ ├── textrank.py # TextRank方法
│ └── tfidf.py # TFIDF方法
├── _compat.py
├── dict.txt
├── finalseg # 基于HMM的切分方法
│ ├── __init__.py
│ ├── prob_emit.p
│ ├── prob_emit.py
│ ├── prob_start.p
│ ├── prob_start.py
│ ├── prob_trans.p
│ └── prob_trans.py
├── __init__.py # 基于DAG的切分方法
├── __main__.py
└── posseg # 词性标注模块
├── char_state_tab.p
├── char_state_tab.py
├── __init__.py
├── prob_emit.p
├── prob_emit.py
├── prob_start.p
├── prob_start.py
├── prob_trans.p
├── prob_trans.py
└── viterbi.py详细文档可以参考GitHub https://github.com/fxsjy/jieba
目前特点
-
支持三种分词模式：
- 精确模式，试图将句子最精确地切开，适合文本分析；
- 全模式，把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义；
- 搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。
-
支持繁体分词
-
支持自定义词典
-
MIT 授权协议
实现算法
- 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
- 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
- 对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法
1，主要功能分词模式
jieba.cut方法接受三个输入参数: 需要分词的字符串；cut_all 参数用来控制是否采用全模式；HMM 参数用来控制是否使用 HMM 模型jieba.cut_for_search方法接受两个参数：需要分词的字符串；是否使用 HMM 模型。该方法适合用于搜索引擎构建倒排索引的分词，粒度比较细- 待分词的字符串可以是 unicode 或 UTF-8 字符串、GBK 字符串。注意：不建议直接输入 GBK 字符串，可能无法预料地错误解码成 UTF-8
jieba.cut以及jieba.cut_for_search返回的结构都是一个可迭代的 generator，可以使用 for 循环来获得分词后得到的每一个词语(unicode)，或者用jieba.lcut以及jieba.lcut_for_search直接返回 listjieba.Tokenizer(dictionary=DEFAULT_DICT)新建自定义分词器，可用于同时使用不同词典。jieba.dt为默认分词器，所有全局分词相关函数都是该分词器的映射。
代码示例
# encoding=utf-8
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))
# 新词识别 “杭研”并没有在词典中,但是也被Viterbi算法识别出来了
seg_list = jieba.cut("他来到了网易杭研大厦")
print (u"[新词识别]: ", "/ ".join(seg_list))输出:
【全模式】: 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学
【精确模式】: 我/ 来到/ 北京/ 清华大学
【新词识别】：他, 来到, 了, 网易, 杭研, 大厦 (此处，“杭研”并没有在词典中，但是也被Viterbi算法识别出来了)
【搜索引擎模式】： 小明, 硕士, 毕业, 于, 中国, 科学, 学院, 科学院, 中国科学院, 计算, 计算所, 后, 在, 日本, 京都, 大学, 日本京都大学, 深造
2，添加自定义词典，载入词典
- 开发者可以指定自己自定义的词典，以便包含 jieba 词库里没有的词。虽然 jieba 有新词识别能力，但是自行添加新词可以保证更高的正确率
- 用法： jieba.load_userdict(file_name) # file_name 为文件类对象或自定义词典的路径
- 词典格式和
dict.txt一样，一个词占一行；每一行分三部分：词语、词频（可省略）、词性（可省略），用空格隔开，顺序不可颠倒。file_name若为路径或二进制方式打开的文件，则文件必须为 UTF-8 编码。 - 词频省略时使用自动计算的能保证分出该词的词频。
例如：
创新办 3 i
云计算 5
凱特琳 nz
台中
-
更改分词器（默认为
jieba.dt）的tmp_dir和cache_file属性，可分别指定缓存文件所在的文件夹及其文件名，用于受限的文件系统。 -
范例：
jieba.load_userdict("E:\python\Lib\site-packages\jieba\mydict.txt")-
自定义词典：https://github.com/fxsjy/jieba/blob/master/test/userdict.txt
-
用法示例：https://github.com/fxsjy/jieba/blob/master/test/test_userdict.py
-
之前： 李小福 / 是 / 创新 / 办 / 主任 / 也 / 是 / 云 / 计算 / 方面 / 的 / 专家 /
-
加载自定义词库后： 李小福 / 是 / 创新办 / 主任 / 也 / 是 / 云计算 / 方面 / 的 / 专家 /
-
-
3，调整词典
-
使用
add_word(word, freq=None, tag=None)和del_word(word)可在程序中动态修改词典。 -
使用
suggest_freq(segment, tune=True)可调节单个词语的词频，使其能（或不能）被分出来。 -
注意：自动计算的词频在使用 HMM 新词发现功能时可能无效。
代码示例：
>>> print('/'.join(jieba.cut('如果放到post中将出错。', HMM=False)))
如果/放到/post/中将/出错/。
>>> jieba.suggest_freq(('中', '将'), True)
494
>>> print('/'.join(jieba.cut('如果放到post中将出错。', HMM=False)))
如果/放到/post/中/将/出错/。
>>> print('/'.join(jieba.cut('「台中」正确应该不会被切开', HMM=False)))
「/台/中/」/正确/应该/不会/被/切开
>>> jieba.suggest_freq('台中', True)
69
>>> print('/'.join(jieba.cut('「台中」正确应该不会被切开', HMM=False)))
「/台中/」/正确/应该/不会/被/切开- “通过用户自定义词典来增强歧义纠错能力” — https://github.com/fxsjy/jieba/issues/14
4，关键词提取
4.1，基于 TF-IDF 算法的关键词抽取
import jieba.analyse
- jieba.analyse.extract_tags(sentence, topK=20, withWeight=False, allowPOS=())
- sentence 为待提取的文本
- topK 为返回几个 TF/IDF 权重最大的关键词，默认值为 20
- withWeight 为是否一并返回关键词权重值，默认值为 False
- allowPOS 仅包括指定词性的词，默认值为空，即不筛选
- jieba.analyse.TFIDF(idf_path=None) 新建 TFIDF 实例，idf_path 为 IDF 频率文件
代码示例 （关键词提取）
https://github.com/fxsjy/jieba/blob/master/test/extract_tags.py
关键词提取所使用逆向文件频率（IDF）文本语料库可以切换成自定义语料库的路径
- 用法： jieba.analyse.set_idf_path(file_name) # file_name为自定义语料库的路径
- 自定义语料库示例：https://github.com/fxsjy/jieba/blob/master/extra_dict/idf.txt.big
- 用法示例：https://github.com/fxsjy/jieba/blob/master/test/extract_tags_idfpath.py
关键词提取所使用停止词（Stop Words）文本语料库可以切换成自定义语料库的路径
- 用法： jieba.analyse.set_stop_words(file_name) # file_name为自定义语料库的路径
- 自定义语料库示例：https://github.com/fxsjy/jieba/blob/master/extra_dict/stop_words.txt
- 用法示例：https://github.com/fxsjy/jieba/blob/master/test/extract_tags_stop_words.py
关键词一并返回关键词权重值示例
4.2，基于 TextRank 算法的关键词抽取
- jieba.analyse.textrank(sentence, topK=20, withWeight=False, allowPOS=(‘ns’, ‘n’, ‘vn’, ‘v’)) 直接使用，接口相同，注意默认过滤词性。
- jieba.analyse.TextRank() 新建自定义 TextRank 实例
算法论文： TextRank: Bringing Order into Texts
基本思想:
- 将待抽取关键词的文本进行分词
- 以固定窗口大小(默认为5，通过span属性调整)，词之间的共现关系，构建图
- 计算图中节点的PageRank，注意是无向带权图
使用示例:
5，词性标注
jieba.posseg.POSTokenizer(tokenizer=None)新建自定义分词器，tokenizer参数可指定内部使用的jieba.Tokenizer分词器。jieba.posseg.dt为默认词性标注分词器。- 标注句子分词后每个词的词性，采用和 ictclas 兼容的标记法。
- 用法示例
>>> import jieba.posseg as pseg
>>> words = pseg.cut("我爱北京天安门")
>>> for word, flag in words:
... print('%s %s' % (word, flag))
...
我 r
爱 v
北京 ns
天安门 ns
6，并行分词
-
原理：将目标文本按行分隔后，把各行文本分配到多个 Python 进程并行分词，然后归并结果，从而获得分词速度的可观提升
-
基于 python 自带的 multiprocessing 模块，目前暂不支持 Windows
-
用法：
jieba.enable_parallel(4)# 开启并行分词模式，参数为并行进程数jieba.disable_parallel()# 关闭并行分词模式
-
例子：https://github.com/fxsjy/jieba/blob/master/test/parallel/test_file.py
-
实验结果：在 4 核 3.4GHz Linux 机器上，对金庸全集进行精确分词，获得了 1MB/s 的速度，是单进程版的 3.3 倍。
-
注意：并行分词仅支持默认分词器
jieba.dt和jieba.posseg.dt。
7，Tokenize：返回词语在原文的起止位置
- 注意，输入参数只接受 unicode
- 默认模式
result = jieba.tokenize(u'永和服装饰品有限公司')
for tk in result:
print("word %s\t\t start: %d \t\t end:%d" % (tk[0],tk[1],tk[2]))
word 永和 start: 0 end:2
word 服装 start: 2 end:4
word 饰品 start: 4 end:6
word 有限公司 start: 6 end:10
- 搜索模式
result = jieba.tokenize(u'永和服装饰品有限公司', mode='search')
for tk in result:
print("word %s\t\t start: %d \t\t end:%d" % (tk[0],tk[1],tk[2]))
word 永和 start: 0 end:2
word 服装 start: 2 end:4
word 饰品 start: 4 end:6
word 有限 start: 6 end:8
word 公司 start: 8 end:10
word 有限公司 start: 6 end:10
ChineseAnalyzer for Whoosh 搜索引擎
- 引用：
from jieba.analyse import ChineseAnalyzer - 用法示例：https://github.com/fxsjy/jieba/blob/master/test/test_whoosh.py
8，命令行分词
使用示例：python -m jieba news.txt > cut_result.txt
命令行选项（翻译）：
使用: python -m jieba [options] filename
结巴命令行界面。
固定参数:
filename 输入文件
可选参数:
-h, --help 显示此帮助信息并退出
-d [DELIM], --delimiter [DELIM]
使用 DELIM 分隔词语，而不是用默认的' / '。
若不指定 DELIM，则使用一个空格分隔。
-p [DELIM], --pos [DELIM]
启用词性标注；如果指定 DELIM，词语和词性之间
用它分隔，否则用 _ 分隔
-D DICT, --dict DICT 使用 DICT 代替默认词典
-u USER_DICT, --user-dict USER_DICT
使用 USER_DICT 作为附加词典，与默认词典或自定义词典配合使用
-a, --cut-all 全模式分词（不支持词性标注）
-n, --no-hmm 不使用隐含马尔可夫模型
-q, --quiet 不输出载入信息到 STDERR
-V, --version 显示版本信息并退出
如果没有指定文件名，则使用标准输入。
--help 选项输出：
$> python -m jieba --help
Jieba command line interface.
positional arguments:
filename input file
optional arguments:
-h, --help show this help message and exit
-d [DELIM], --delimiter [DELIM]
use DELIM instead of ' / ' for word delimiter; or a
space if it is used without DELIM
-p [DELIM], --pos [DELIM]
enable POS tagging; if DELIM is specified, use DELIM
instead of '_' for POS delimiter
-D DICT, --dict DICT use DICT as dictionary
-u USER_DICT, --user-dict USER_DICT
use USER_DICT together with the default dictionary or
DICT (if specified)
-a, --cut-all full pattern cutting (ignored with POS tagging)
-n, --no-hmm don't use the Hidden Markov Model
-q, --quiet don't print loading messages to stderr
-V, --version show program's version number and exit
If no filename specified, use STDIN instead.
9，延迟加载机制
jieba 采用延迟加载，import jieba 和 jieba.Tokenizer() 不会立即触发词典的加载，一旦有必要才开始加载词典构建前缀字典。如果你想手工初始 jieba，也可以手动初始化。
import jieba
jieba.initialize() # 手动初始化（可选）
在 0.28 之前的版本是不能指定主词典的路径的，有了延迟加载机制后，你可以改变主词典的路径:
jieba.set_dictionary('data/dict.txt.big')
例子： https://github.com/fxsjy/jieba/blob/master/test/test_change_dictpath.py
10，其他词典
-
占用内存较小的词典文件 https://github.com/fxsjy/jieba/raw/master/extra_dict/dict.txt.small
-
支持繁体分词更好的词典文件 https://github.com/fxsjy/jieba/raw/master/extra_dict/dict.txt.big
下载你所需要的词典，然后覆盖 jieba/dict.txt 即可；或者用 jieba.set_dictionary('data/dict.txt.big')
11、去除停用词
在信息检索中，为节省存储空间和提高搜索效率，在处理自然语言数据（或文本）之前或之后会自动过滤掉某些字或词，比如“的”、“是”、“而且”、“但是”、”非常“等。这些字或词即被称为Stop Words（停用词）。
import jieba
# 去除停用词
stopwords = {}.fromkeys(['的', '包括', '等', '是'])
text = "故宫的著名景点包括乾清宫、太和殿和午门等。其中乾清宫非常精美，午门是紫禁城的正门。"
# 精确模式
segs = jieba.cut(text, cut_all=False)
final = ''
for seg in segs:
if seg not in stopwords:
final += seg
print (final)
seg_list = jieba.cut(final, cut_all=False)
print ("/ ".join(seg_list))运行结果：
故宫著名景点乾清宫、太和殿和午门。其中乾清宫非常精美，午门紫禁城正门。
故宫/ 著名景点/ 乾/ 清宫/ 、/ 太和殿/ 和/ 午门/ 。/ 其中/ 乾/ 清宫/ 非常/ 精美/ ，/ 午门/ 紫禁城/ 正门/ 。原理解析：
1 简介
jieba分词主要是基于统计词典，构造一个前缀词典；然后利用前缀词典对输入句子进行切分，得到所有的切分可能，根据切分位置，构造一个有向无环图；通过动态规划算法，计算得到最大概率路径，也就得到了最终的切分形式。
2 实例讲解
以“去北京大学玩”为例，作为待分词的输入文本。
离线统计的词典形式如下，每一行有三列，第一列是词，第二列是词频，第三列是词性。
...
北京大学 2053 nt
大学 20025 n
去 123402 v
玩 4207 v
北京 34488 ns
北 17860 ns
京 6583 ns
大 144099 a
学 17482 n
...2.1 前缀词典构建
首先是基于统计词典构造前缀词典，如统计词典中的词“北京大学”的前缀分别是“北”、“北京”、“北京大”；词“大学”的前缀是“大”。统计词典中所有的词形成的前缀词典如下所示，你也许会注意到“北京大”作为“北京大学”的前缀，但是它的词频却为0，这是为了便于后面有向无环图的构建。
...
北京大学 2053
北京大 0
大学 20025
去 123402
玩 4207
北京 34488
北 17860
京 6583
大 144099
学 17482
...2.2 有向无环图构建
然后基于前缀词典，对输入文本进行切分，对于“去”，没有前缀，那么就只有一种划分方式；对于“北”，则有“北”、“北京”、“北京大学”三种划分方式；对于“京”，也只有一种划分方式；对于“大”，则有“大”、“大学”两种划分方式，依次类推，可以得到每个字开始的前缀词的划分方式。
在jieba分词中，对每个字都是通过在文本中的位置来标记的，因此可以构建一个以位置为key，相应划分的末尾位置构成的列表为value的映射，如下所示，
0: [0]
1: [1,2,4]
2: [2]
3: [3,4]
4: [4]
5: [5]对于0: [0]，表示位置0对应的词，就是0 ~ 0，就是“去”；对于1: [1,2,4]，表示位置1开始，在1，2，4位置都是词，就是1 ~ 1，1 ~ 2，1 ~ 4，即“北”，“北京”，“北京大学”这三个词。
对于每一种划分，都将相应的首尾位置相连，例如，对于位置1,可以将它与位置1、位置2、位置4相连接，最终构成一个有向无环图，如下所示，
2.3 最大概率路径计算
在得到所有可能的切分方式构成的有向无环图后，我们发现从起点到终点存在多条路径，多条路径也就意味着存在多种分词结果，例如，
# 路径1
0 -> 1 -> 2 -> 3 -> 4 -> 5
# 分词结果1
去 / 北 / 京 / 大 / 学 / 玩
# 路径2
0 -> 1 , 2 -> 3 -> 4 -> 5
# 分词结果2
去 / 北京 / 大 / 学 / 玩
# 路径3
0 -> 1 , 2 -> 3 , 4 -> 5
# 分词结果3
去 / 北京 / 大学 / 玩
# 路径4
0 -> 1 , 2 , 3 , 4 -> 5
# 分词结果4
去 / 北京大学 / 玩
...因此，我们需要计算最大概率路径，也即按照这种方式切分后的分词结果的概率最大。在计算最大概率路径时，jieba分词采用从后往前这种方式进行计算。为什么采用从后往前这种方式计算呢？因为，我们这个有向无环图的方向是从前向后指向，对于一个节点，我们只知道这个节点会指向后面哪些节点，但是我们很难直接知道有哪些前面的节点会指向这个节点。
在采用动态规划计算最大概率路径时，每到达一个节点，它前面的节点到终点的最大路径概率已经计算出来。
3 源码分析
3.1 算法流程
jieba.__init__.py中实现了jieba分词接口函数cut(self, sentence, cut_all=False, HMM=True)。
jieba分词接口主入口函数，会首先将输入文本解码为Unicode编码，然后根据入参，选择不同的切分方式，本文主要以精确模式进行讲解，因此cut_all和HMM这两个入参均为默认值；
切分方式选择，
re_han = re_han_default
re_skip = re_skip_default块切分方式选择，
cut_block = self.__cut_DAG函数__cut_DAG(self, sentence)首先构建前缀词典，其次构建有向无环图，然后计算最大概率路径，最后基于最大概率路径进行分词，如果遇到未登录词，则调用HMM模型进行切分。本文主要涉及前三个部分，基于HMM的分词方法则在下一文章中详细说明。
3.2 前缀词典构建
get_DAG(self, sentence)函数会首先检查系统是否初始化，如果没有初始化，则进行初始化。在初始化的过程中，会构建前缀词典。
构建前缀词典的入口函数是gen_pfdict(self, f)，解析离线统计词典文本文件，每一行分别对应着词、词频、词性，将词和词频提取出来，以词为key，以词频为value，加入到前缀词典中。对于每个词，再分别获取它的前缀词，如果前缀词已经存在于前缀词典中，则不处理；如果该前缀词不在前缀词典中，则将其词频置为0，便于后续构建有向无环图。
jieba分词中gen_pfdict函数实现如下，
# f是离线统计的词典文件句柄
def gen_pfdict(self, f):
# 初始化前缀词典
lfreq = {}
ltotal = 0
f_name = resolve_filename(f)
for lineno, line in enumerate(f, 1):
try:
# 解析离线词典文本文件，离线词典文件格式如第2章中所示
line = line.strip().decode('utf-8')
# 词和对应的词频
word, freq = line.split(' ')[:2]
freq = int(freq)
lfreq[word] = freq
ltotal += freq
# 获取该词所有的前缀词
for ch in xrange(len(word)):
wfrag = word[:ch + 1]
# 如果某前缀词不在前缀词典中，则将对应词频设置为0，
# 如第2章中的例子“北京大”
if wfrag not in lfreq:
lfreq[wfrag] = 0
except ValueError:
raise ValueError(
'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
f.close()
return lfreq, ltotal为什么jieba没有使用trie树作为前缀词典存储的数据结构？
参考jieba中的issue–不用Trie，减少内存加快速度；优化代码细节 #187，本处直接引用该issue的comment，如下，
对于get_DAG()函数来说，用Trie数据结构，特别是在Python环境，内存使用量过大。经实验，可构造一个前缀集合解决问题。
该集合储存词语及其前缀，如set([‘数’, ‘数据’, ‘数据结’, ‘数据结构’])。在句子中按字正向查找词语，在前缀列表中就继续查找，直到不在前缀列表中或超出句子范围。大约比原词库增加40%词条。
该版本通过各项测试，与原版本分词结果相同。
测试：一本5.7M的小说，用默认字典，64位Ubuntu，Python 2.7.6。
Trie：第一次加载2.8秒，缓存加载1.1秒；内存277.4MB，平均速率724kB/s；
前缀字典：第一次加载2.1秒，缓存加载0.4秒；内存99.0MB，平均速率781kB/s；
此方法解决纯Python中Trie空间效率低下的问题。
同时改善了一些代码的细节，遵循PEP8的格式，优化了几个逻辑判断。
3.2 有向无环图构建
有向无环图，directed acyclic graphs，简称DAG，是一种图的数据结构，顾名思义，就是没有环的有向图。
DAG在分词中的应用很广，无论是最大概率路径，还是其它做法，DAG都广泛存在于分词中。因为DAG本身也是有向图，所以用邻接矩阵来表示是可行的，但是jieba采用了Python的dict结构，可以更方便的表示DAG。最终的DAG是以{k : [k , j , ..] , m : [m , p , q] , …}的字典结构存储，其中k和m为词在文本sentence中的位置，k对应的列表存放的是文本中以k开始且词sentence[k: j + 1]在前缀词典中的 以k开始j结尾的词的列表，即列表存放的是sentence中以k开始的可能的词语的结束位置，这样通过查找前缀词典就可以得到词。
get_DAG(self, sentence)函数进行对系统初始化完毕后，会构建有向无环图。
从前往后依次遍历文本的每个位置，对于位置k，首先形成一个片段，这个片段只包含位置k的字，然后就判断该片段是否在前缀词典中，
-
如果这个片段在前缀词典中，
1.1 如果词频大于0，就将这个位置i追加到以k为key的一个列表中；
1.2 如果词频等于0，如同第2章中提到的“北京大”，则表明前缀词典存在这个前缀，但是统计词典并没有这个词，继续循环；
-
如果这个片段不在前缀词典中，则表明这个片段已经超出统计词典中该词的范围，则终止循环；
-
然后该位置加1，然后就形成一个新的片段，该片段在文本的索引为[k:i+1]，继续判断这个片段是否在前缀词典中。
jieba分词中get_DAG函数实现如下，
# 有向无环图构建主函数
def get_DAG(self, sentence):
# 检查系统是否已经初始化
self.check_initialized()
# DAG存储向无环图的数据，数据结构是dict
DAG = {}
N = len(sentence)
# 依次遍历文本中的每个位置
for k in xrange(N):
tmplist = []
i = k
# 位置k形成的片段
frag = sentence[k]
# 判断片段是否在前缀词典中
# 如果片段不在前缀词典中，则跳出本循环
# 也即该片段已经超出统计词典中该词的长度
while i < N and frag in self.FREQ:
# 如果该片段的词频大于0
# 将该片段加入到有向无环图中
# 否则，继续循环
if self.FREQ[frag]:
tmplist.append(i)
# 片段末尾位置加1
i += 1
# 新的片段较旧的片段右边新增一个字
frag = sentence[k:i + 1]
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG以“去北京大学玩”为例，最终形成的有向无环图为，
{0: [0], 1: [1,2,4], 2: [2], 3: [3,4], 4: [4], 5: [5]}3.3 最大概率路径计算
3.2章节中构建出的有向无环图DAG的每个节点，都是带权的，对于在前缀词典里面的词语，其权重就是它的词频；我们想要求得route = (w1,w2,w3,…,wn)，使得 ∑weight(wi)∑weight(wi) 最大。
如果需要使用动态规划求解，需要满足两个条件，
- 重复子问题
- 最优子结构
我们来分析一下最大概率路径问题，是否满足动态规划的两个条件。
重复子问题
对于节点wi和其可能存在的多个后继节点Wj和Wk，
任意通过Wi到达Wj的路径的权重 = 该路径通过Wi的路径权重 + Wj的权重，也即{Ri -> j} = {Ri + weight(j)}
任意通过Wi到达Wk的路径的权重 = 该路径通过Wi的路径权重 + Wk的权重，也即{Ri -> k} = {Ri + weight(k)}即对于拥有公共前驱节点Wi的节点Wj和Wk，需要重复计算达到Wi的路径的概率。
最优子结构
对于整个句子的最优路径Rmax和一个末端节点Wx，对于其可能存在的多个前驱Wi，Wj，Wk…，设到达Wi，Wj，Wk的最大路径分别是Rmaxi，Rmaxj，Rmaxk，有，
Rmax = max(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)于是，问题转化为，求解Rmaxi，Rmaxj，Rmaxk，…等，
组成了最优子结构，子结构里面的最优解是全局的最优解的一部分。
状态转移方程为，
Rmax = max{(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)}jieba分词中计算最大概率路径的主函数是calc(self, sentence, DAG, route)，函数根据已经构建好的有向无环图计算最大概率路径。
函数是一个自底向上的动态规划问题，它从sentence的最后一个字（N-1）开始倒序遍历sentence的每个字（idx）的方式，计算子句sentence[idx ~ N-1]的概率对数得分。然后将概率对数得分最高的情况以（概率对数，词语最后一个位置）这样的元组保存在route中。
函数中，logtotal为构建前缀词频时所有的词频之和的对数值，这里的计算都是使用概率对数值，可以有效防止下溢问题。
jieba分词中calc函数实现如下，
def calc(self, sentence, DAG, route):
N = len(sentence)
# 初始化末尾为0
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])1 基于汉字成词能力的HMM模型识别未登录词的算法简介
在前面已经介绍了基于前缀词典和动态规划方法实现分词，但是如果没有前缀词典或者有些词不在前缀词典中，jieba分词一样可以分词，那么jieba分词是如何对未登录词进行分词呢？这就是本文将要讲解的，
利用HMM模型进行分词，主要是将分词问题视为一个序列标注（sequence labeling）问题，其中，句子为观测序列，分词结果为状态序列。首先通过语料训练出HMM相关的模型，然后利用Viterbi算法进行求解，最终得到最优的状态序列，然后再根据状态序列，输出分词结果。
2 实例
2.1 序列标注
序列标注，就是将输入句子和分词结果当作两个序列，句子为观测序列，分词结果为状态序列，当完成状态序列的标注，也就得到了分词结果。
以“去北京大学玩”为例，我们知道“去北京大学玩”的分词结果是“去 / 北京大学 / 玩”。对于分词状态，由于jieba分词中使用的是4-tag，因此我们以4-tag进行计算。4-tag，也就是每个字处在词语中的4种可能状态，B、M、E、S，分别表示Begin（这个字处于词的开始位置）、Middle（这个字处于词的中间位置）、End（这个字处于词的结束位置）、Single（这个字是单字成词）。具体如下图所示，“去”和“玩”都是单字成词，因此状态就是S，“北京大学”是多字组合成的词，因此“北”、“京”、“大”、“学”分别位于“北京大学”中的B、M、M、E。
2.2 HMM模型
关于HMM模型的介绍，网络上有很多的资源，比如 52nlp整理的 HMM相关文章索引 。博主在此就不再具体介绍HMM模型的原理，但是会对分词涉及的基础知识进行讲解。
HMM模型作的两个基本假设：
-
1.齐次马尔科夫性假设，即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻t无关；
P(states[t] | states[t-1],observed[t-1],…,states[1],observed[1]) = P(states[t] | states[t-1]) t = 1,2,…,T
-
2.观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其它观测和状态无关，
P(observed[t] | states[T],observed[T],…,states[1],observed[1]) = P(observed[t] | states[t]) t = 1,2,…,T
HMM模型有三个基本问题：
- 1.概率计算问题，给定模型 λ=(A,B,π)λ=(A,B,π) 和观测序列 O=(o1,o2,…,oT)O=(o1,o2,…,oT) ，怎样计算在模型 λλ 下观测序列O出现的概率 P(O|λ)P(O|λ) ，也就是Forward-backward算法；
- 2.学习问题，已知观测序列 O=(o1,o2,…,oT)O=(o1,o2,…,oT) ，估计模型 λ=(A,B,π)λ=(A,B,π) ，使得在该模型下观测序列的概率 P(O|λ)P(O|λ) 尽可能的大，即用极大似然估计的方法估计参数；
- 3.预测问题，也称为解码问题，已知模型 λ=(A,B,π)λ=(A,B,π) 和观测序列 O=(o1,o2,…,oT)O=(o1,o2,…,oT) ，求对给定观测序列条件概率 P(S|O)P(S|O) 最大的状态序列 I=(s1,s2,…,sT)I=(s1,s2,…,sT) ，即给定观测序列。求最有可能的对应的状态序列；
其中，jieba分词主要中主要涉及第三个问题，也即预测问题。
HMM模型中的五元组表示：
- 1.观测序列；
- 2.隐藏状态序列；
- 3.状态初始概率；
- 4.状态转移概率；
- 5.状态发射概率；
这里仍然以“去北京大学玩”为例，那么“去北京大学玩”就是观测序列。
而“去北京大学玩”对应的“SBMMES”则是隐藏状态序列，我们将会注意到B后面只能接（M或者E），不可能接（B或者S）；而M后面也只能接（M或者E），不可能接（B或者S）。
状态初始概率表示，每个词初始状态的概率；jieba分词训练出的状态初始概率模型如下所示。其中的概率值都是取对数之后的结果（可以让概率相乘转变为概率相加），其中-3.14e+100代表负无穷，对应的概率值就是0。这个概率表说明一个词中的第一个字属于{B、M、E、S}这四种状态的概率，如下可以看出，E和M的概率都是0，这也和实际相符合：开头的第一个字只可能是每个词的首字（B），或者单字成词（S）。这部分对应jieba/finaseg/prob_start.py，具体可以进入源码查看。
P={'B': -0.26268660809250016,
'E': -3.14e+100,
'M': -3.14e+100,
'S': -1.4652633398537678}状态转移概率是马尔科夫链中很重要的一个知识点，一阶的马尔科夫链最大的特点就是当前时刻T = i的状态states(i)，只和T = i时刻之前的n个状态有关，即{states(i-1),states(i-2),…,states(i-n)}。
再看jieba中的状态转移概率，其实就是一个嵌套的词典，数值是概率值求对数后的值，如下所示，
P={'B': {'E': -0.510825623765990, 'M': -0.916290731874155},
'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937},
'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226},
'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}}P[‘B’][‘E’]代表的含义就是从状态B转移到状态E的概率，由P[‘B’][‘E’] = -0.5897149736854513，表示当前状态是B，下一个状态是E的概率对数是-0.5897149736854513，对应的概率值是0.6，相应的，当前状态是B，下一个状态是M的概率是0.4，说明当我们处于一个词的开头时，下一个字是结尾的概率要远高于下一个字是中间字的概率，符合我们的直觉，因为二个字的词比多个字的词更常见。这部分对应jieba/finaseg/prob_trans.py，具体可以查看源码。
状态发射概率，根据HMM模型中观测独立性假设，发射概率，即观测值只取决于当前状态值，也就如下所示，
P(observed[i],states[j]) = P(states[j]) * P(observed[i] | states[j])其中，P(observed[i] | states[j])就是从状态发射概率中获得的。
P={'B': {'一': -3.6544978750449433,
'丁': -8.125041941842026,
'七': -7.817392401429855,
...
'S': {':': -15.828865681131282,
'一': -4.92368982120877,
'丁': -9.024528361347633,
...P[‘B’][‘一’]代表的含义就是状态处于’B’，而观测的字是‘一’的概率对数值为P[‘B’][‘一’] = -3.6544978750449433。这部分对应jieba/finaseg/prob_emit.py，具体可以查看源码。
2.3 Viterbi算法
Viterbi算法实际上是用动态规划求解HMM模型预测问题，即用动态规划求概率路径最大（最优路径）。这时候，一条路径对应着一个状态序列。
根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻t通过结点 i∗tit∗ ，那么这一路径从结点 i∗tit∗ 到终点 i∗TiT∗ 的部分路径，对于从 i∗tit∗ 到 i∗TiT∗ 的所有可能的部分路径来说，必须是最优的。因为假如不是这样，那么从 i∗tit∗ 到 i∗TiT∗ 就有另一条更好的部分路径存在，如果把它和从 i∗tit∗ 到达 i∗TiT∗ 的部分路径连接起来，就会形成一条比原来的路径更优的路径，这是矛盾的。依据这个原理，我们只需要从时刻t=1开始，递推地计算在时刻t状态i的各条部分路径的最大概率，直至得到时刻t=T状态为i的各条路径的最大概率。时刻t=T的最大概率就是最优路径的概率 P∗P∗ ，最优路径的终结点 i∗TiT∗ 也同时得到。之后，为了找出最优路径的各个结点，从终结点 i∗TiT∗ 开始，由后向前逐步求得结点 i∗T−1,…,i∗1iT−1∗,…,i1∗ ，最终得到最优路径 I∗=(i∗1,i∗2,…,i∗T)I∗=(i1∗,i2∗,…,iT∗) 。
2.4 输出分词结果
由Viterbi算法得到状态序列，也就可以根据状态序列得到分词结果。其中状态以B开头，离它最近的以E结尾的一个子状态序列或者单独为S的子状态序列，就是一个分词。以”去北京大学玩“的隐藏状态序列”SBMMES“为例，则分词为”S / BMME / S“，对应观测序列，也就是”去 / 北京大学 / 玩”。
3 源码分析
jieba分词中HMM模型识别未登录词的源码目录在jieba/finalseg/下，
__init__.py 实现了HMM模型识别未登录词；
prob_start.py 存储了已经训练好的HMM模型的状态初始概率表；
prob_trans.py 存储了已经训练好的HMM模型的状态转移概率表；
prob_emit.py 存储了已经训练好的HMM模型的状态发射概率表；
3.1 HMM模型参数训练
HMM模型的参数是如何训练出来，此处可以参考jieba中Issue 模型的数据是如何生成的？ #7，如下是jieba的开发者的解释：
来源主要有两个，一个是网上能下载到的1998人民日报的切分语料还有一个msr的切分语料。另一个是我自己收集的一些txt小说，用ictclas把他们切分（可能有一定误差），然后用python脚本统计词频。
要统计的主要有三个概率表：1)位置转换概率，即B（开头）,M（中间),E(结尾),S(独立成词）四种状态的转移概率；2）位置到单字的发射概率，比如P(“和”|M)表示一个词的中间出现”和”这个字的概率；3) 词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。
3.2 基于HMM模型的分词流程
jieba分词会首先调用函数cut(sentence)，cut函数会先将输入句子进行解码，然后调用__cut函数进行处理。__cut函数就是jieba分词中实现HMM模型分词的主函数。__cut函数会首先调用viterbi算法，求出输入句子的隐藏状态，然后基于隐藏状态进行分词。
def __cut(sentence):
global emit_P
# 通过viterbi算法求出隐藏状态序列
prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
begin, nexti = 0, 0
# print pos_list, sentence
# 基于隐藏状态序列进行分词
for i, char in enumerate(sentence):
pos = pos_list[i]
# 字所处的位置是开始位置
if pos == 'B':
begin = i
# 字所处的位置是结束位置
elif pos == 'E':
# 这个子序列就是一个分词
yield sentence[begin:i + 1]
nexti = i + 1
# 单独成字
elif pos == 'S':
yield char
nexti = i + 1
# 剩余的直接作为一个分词，返回
if nexti < len(sentence):
yield sentence[nexti:]3.3 Viterbi算法
首先先定义两个变量， δ,ψδ,ψ，定义在时刻t状态i的所有单个路径 (i1,i2,…,it)(i1,i2,…,it) 中概率最大值为
δt(i)=maxi1,i2,..,inP(it=i,it−1,…,i1,ot,…,o1|λ),i=1,2,…,Nδt(i)=maxi1,i2,..,inP(it=i,it−1,…,i1,ot,…,o1|λ),i=1,2,…,N
由此可得变量 δδ 的递推公式为，
δt+1(i)=maxi1,i2,..,inP(it+1=i,it,…,i1,ot+1,…,o1|λ)δt+1(i)=maxi1,i2,..,inP(it+1=i,it,…,i1,ot+1,…,o1|λ)
=max1≤j≤N[δt(j)∗aji]∗bi(ot+1),i=1,2,…,N,t=1,2,…,N−1=max1≤j≤N[δt(j)∗aji]∗bi(ot+1),i=1,2,…,N,t=1,2,…,N−1
定义在时刻t状态i的所有单个路径 (i1,i2,…,it−1,i)(i1,i2,…,it−1,i) 中概率最大的路径的第t-1个结点为，
ψt(i)=argmax1≤j≤N[δt−1(j)∗aji]ψt(i)=argmax1≤j≤N[δt−1(j)∗aji]
Viterbi算法的大致流程：
输入：模型 λ=(A,B,π)λ=(A,B,π) 和观测序列 O=(o1,o2,…,oT)O=(o1,o2,…,oT) ；
输出：最优路径 I∗=(i∗1,i∗2,…,i∗T)I∗=(i1∗,i2∗,…,iT∗)；
（1）初始化
δ1(i)=πi∗bi(o1),i=1,2,…,Nδ1(i)=πi∗bi(o1),i=1,2,…,N
ψ1(i)=0,i=1,2,…,Nψ1(i)=0,i=1,2,…,N
（2）递推
δt(i)=max1≤j≤N[δt−1(j)∗aji]∗bi(ot),i=1,2,…,Nδt(i)=max1≤j≤N[δt−1(j)∗aji]∗bi(ot),i=1,2,…,N
ψt(i)=argmax1≤j≤N[δt−1(j)∗aji],,i=1,2,…,Nψt(i)=argmax1≤j≤N[δt−1(j)∗aji],,i=1,2,…,N
（3）终止
P∗=max1≤j≤NδT(i)P∗=max1≤j≤NδT(i)
i∗T=argmax1≤i≤N[δT(i)]iT∗=argmax1≤i≤N[δT(i)]
（4）最优路径回溯，对于t=T-1，T-2，…，1，
i∗t=ψt+1(i)it∗=ψt+1(i)
最终求得最优路径 I∗=(i∗1,i∗2,…,i∗T)I∗=(i1∗,i2∗,…,iT∗) ；
jieba分词实现Viterbi算法是在viterbi(obs, states, start_p, trans_p, emit_p)函数中实现。viterbi函数会先计算各个初始状态的对数概率值，然后递推计算，每时刻某状态的对数概率值取决于上一时刻的对数概率值、上一时刻的状态到这一时刻的状态的转移概率、这一时刻状态转移到当前的字的发射概率三部分组成。
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}] # tabular
path = {}
# 时刻t = 0，初始状态
for y in states: # init
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
path[y] = [y]
# 时刻t = 1,...,len(obs) - 1
for t in xrange(1, len(obs)):
V.append({})
newpath = {}
# 当前时刻所处的各种可能的状态
for y in states:
# 获取发射概率对数
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# 分别获取上一时刻的状态的概率对数，该状态到本时刻的状态的转移概率对数，本时刻的状态的发射概率对数
# 其中，PrevStatus[y]是当前时刻的状态所对应上一时刻可能的状态
(prob, state) = max(
[(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
V[t][y] = prob
# 将上一时刻最优的状态 + 这一时刻的状态
newpath[y] = path[state] + [y]
path = newpath
# 最后一个时刻
(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')
# 返回最大概率对数和最优路径
return (prob, path[state])相关优化：
-
1.将每一时刻最优概率路径记录下来，避免了第4步的最优路径回溯；
-
2.提前建立一个当前时刻的状态到上一时刻的状态的映射表，记录每个状态在前一时刻的可能状态，降低计算量；如下所示，当前时刻的状态是B，那么前一时刻的状态只可能是（E或者S），而不可能是（B或者M）；
PrevStatus = {
‘B’: ‘ES’,
‘M’: ‘MB’,
‘S’: ‘SE’,
‘E’: ‘BM’
}
1 简介
词性（part-of-speech）是词汇基本的语法范畴，通常也称为词类，主要用来描述一个词在上下文的作用。例如，描述一个概念的词就是名词，在下文引用这个名词的词就是代词。有的词性经常会出现一些新的词，例如名词，这样的词性叫做开放式词性。另外一些词性中的词比较固定，例如代词，这样的词性叫做封闭式词性。因为存在一个词对应多个词性的现象，所以给词准确地标注词性并不是很容易。例如，“改革”在“中国开始对计划经济体制进行改革”这句话中是一个动词，但是在“医药卫生改革中的经济问题”这个句子中是一个名词。把这个问题抽象出来，就是已知单词序列，给每个单词标注词性。词性标注是自然语言处理中一项非常重要的基础性工作。
汉语词性标注同样面临许多棘手的问题，其主要的难点可以归纳为以下三个方面：
- （1） 汉语是一种缺乏词形态变化的语言，词的类别不能像印欧语言那样，直接从词的形态变化来判别；
- （2） 常用词兼类现象严重，越是常用的词，不同的用法越多，尽管兼类现象仅仅占汉语词汇很小的一部分，但是由于兼类使用的程度高，兼类现象纷繁，覆盖面广，涉及汉语中大部分词类，因而造成汉语文本中词类歧义排除的任务量大，而且面广，复杂多样；
- （3） 研究者主观原因造成的困难。语言学界在词性划分的目的、标准等问题还存在分歧；
不同的语言有不同的词性标注集。为了方便指明词的词性，可以给每个词性编码，可以具体参考 ICTCLAS 汉语词性标注集 ，其中，常见的有a表示形容词，d表示副词，n表示名词，p表示介词，v表示动词。
目前采用的词性标注方法主要有基于统计模型的标注方法、基于规则的标注方法、统计方法与规则方法相结合的方法、基于有限状态转换机的标注方法和基于神经网络的词性标注方法。
jieba分词中提供了词性标注功能，可以标注标注句子分词后每个词的词性，词性标注集采用北大计算所词性标注集，属于采用基于统计模型的标注方法，下面将通过实例讲解介绍如何使用jieba分词的词性标注接口、以及通过源码讲解其实现的原理。
PS：
jieba是采用和ICTCLAS兼容的标记法，参考链接：ictclas 词性标注在哪里可以看到？ #47 ， 词性 eng 是啥？ 为什么官方没有词性对照表？ #411；计算所词性标注集的作者是张华平老师，张华平老师也是ICTCLAS的作者，因此ICTCLAS词性标注集就是北大计算所的词性标注集，参考 计算所汉语词性标记集 。ICTCLAS现在已经更新为NLPIR，github地址为 https://github.com/NLPIR-team/NLPIR 。
2 实例讲解
示例代码如下所示，
# 引入词性标注接口
import jieba.posseg as psg
text = "去北京大学玩"
#词性标注
seg = psg.cut(text)
#将词性标注结果打印出来
for ele in seg:
print ele控制台输出，
去/v
北京大学/nt
玩/v可以观察到“去”是动词，“北京大学”是机构名称，“玩”也是动词。
3 jieba分词系统的词性标注流程
jieba分词的词性标注过程非常类似于jieba分词的分词流程，同时进行分词和词性标注。在词性标注的时候，首先基于正则表达式（汉字）进行判断，1）如果是汉字，则会基于前缀词典构建有向无环图，然后基于有向图计算最大概率路径，同时在前缀词典中查找所分出的词的词性，如果没有找到，则将其词性标注为“x”（非语素字 非语素字只是一个符号，字母x通常用于代表未知数、符号）；如果HMM标志位置位，并且该词为未登录词，则通过隐马尔科夫模型对其进行词性标注；2）如果是其它，则根据正则表达式判断其类型，分别赋予“x”，“m”（数词 取英语numeral的第3个字母，n，u已有他用），“eng”（英文）。流程图如下所示，
其中，基于前缀词典构造有向无环图，然后基于有向无环图计算最大概率路径，原理及源码剖析，具体可参考 结巴分词2–基于前缀词典及动态规划实现分词 这篇blog。
其中，基于隐马尔科夫模型进行词性标注，就是将词性标注视为序列标注问题，利用Viterbi算法进行求解，原理及源码剖析，具体可参考 结巴分词3–基于汉字成词能力的HMM模型识别未登录词 这篇blog。
4 源码分析
jieba分词的词性标注功能，是在jieba/posseg目录下实现的。
其中，__init__.py实现了词性标注的大部分函数；
char_state_tab.py存储了离线统计的字及其对应的状态；
prob_emit.py存储了状态到字的发射概率的对数值；
prob_start.py存储了初始状态的概率的对数值；
prob_trans.py存储了前一时刻的状态到当前时刻的状态的转移概率的对数值；
viterbi.py实现了Viterbi算法；
4.1 主调函数
jieba分词的词性标注接口的主调函数是cut函数，位于jieba/posseg/__init__.py文件中。
默认条件下，jieba.pool是None，jieba.pool is None这个条件为True，会执行下面的for循环。
def cut(sentence, HMM=True):
"""
Global cut function that supports parallel processing.
Note that this only works using dt, custom POSTokenizer
instances are not supported.
"""
global dt
# 默认条件下，此条件为True
if jieba.pool is None:
# 执行for循环
for w in dt.cut(sentence, HMM=HMM):
yield w
else:
parts = strdecode(sentence).splitlines(True)
if HMM:
result = jieba.pool.map(_lcut_internal, parts)
else:
result = jieba.pool.map(_lcut_internal_no_hmm, parts)
for r in result:
for w in r:
yield wfor循环中的dt = POSTokenizer(jieba.dt)，POSTokenizer就是jieba分词中的词性标注定义的类，其中jieba.dt是jieba自己实现的分词接口。POSTokenizer类在初始化的时候，会读取离线统计的词典（每行分别为字、频率、词性），加载为词–词性词典。
最终，程序会执行dt.cut函数。
cut函数是默认条件下jieba分词的词性标注过程的执行函数，位于jieba/posseg/__init__.py文件定义的POSTokenizer中。cut函数会执行__cut_internal这个函数。
__cut_internal函数会首先根据标志位，选择不同的分割函数，然后会首先基于正则表达式对输入句子进行分割，如果是汉字，则根据分割函数进行分割；否则，进一步根据正则表达式判断其类型。
默认情况下，HMM标志位为True，因此cut_blk = self.__cut_DAG，也就会使用HMM模型来对未登录词进行词性标注。
def __cut_internal(self, sentence, HMM=True):
self.makesure_userdict_loaded()
sentence = strdecode(sentence)
blocks = re_han_internal.split(sentence)
# 根据标志位判断，选择不同的分割函数
if HMM:
# 使用HMM模型
cut_blk = self.__cut_DAG
else:
# 不使用HMM模型
cut_blk = self.__cut_DAG_NO_HMM
for blk in blocks:
# 匹配汉字的正则表达式，进一步根据分割函数进行切割
if re_han_internal.match(blk):
for word in cut_blk(blk):
yield word
# 没有匹配上汉字的正则表达式
else:
tmp = re_skip_internal.split(blk)
for x in tmp:
if re_skip_internal.match(x):
yield pair(x, 'x')
else:
for xx in x:
# 匹配为数字
if re_num.match(xx):
yield pair(xx, 'm')
# 匹配为英文
elif re_eng.match(x):
yield pair(xx, 'eng')
# 未知类型
else:
yield pair(xx, 'x')4.2 基于有向无环图计算最大概率路径
__cut_DAG函数会首先根据离线统计的词典（每行分别为字、频率、词性）构建前缀词典这个词典。然后基于前缀词典构建有向无环图，然后基于有向无环图计算最大概率路径，对句子进行分割。基于分割结果，如果该词在词–词性词典中，则将词典中该词的词性赋予给这个词，否则赋予“x”；如果前缀词典中不存在该词，则这个词是未登录词，则利用隐马尔科夫模型对其进行词性标注；如果上述两个条件都没有满足，则将词性标注为“x”。
def __cut_DAG(self, sentence):
# 构建有向无环图
DAG = self.tokenizer.get_DAG(sentence)
route = {}
# 计算最大概率路径
self.tokenizer.calc(sentence, DAG, route)
x = 0
buf = ''
N = len(sentence)
while x < N:
y = route[x][1] + 1
l_word = sentence[x:y]
if y - x == 1:
buf += l_word
else:
if buf:
if len(buf) == 1:
# 词--词性词典中有该词，则将词性赋予给该词；否则为“x”
yield pair(buf, self.word_tag_tab.get(buf, 'x'))
# 前缀词典中不存在这个词，则利用隐马尔科夫模型进行词性标注
elif not self.tokenizer.FREQ.get(buf):
recognized = self.__cut_detail(buf)
for t in recognized:
yield t
else:
# 两种条件都不满足，则将词性标注为“x”
for elem in buf:
yield pair(elem, self.word_tag_tab.get(elem, 'x'))
buf = ''
# 默认将词性标注为“x”
yield pair(l_word, self.word_tag_tab.get(l_word, 'x'))
x = y
.......
.......4.3 隐马尔科夫识别未登录词
__cut_detail函数是利用隐马尔科夫模型进行词性标注的主函数。
__cut_detail函数首先利用正则表达式对未登录词组成的句子进行分割，然后根据正则表达式进行判断，如果匹配上，则利用隐马尔科夫模型对其进行词性标注；否则，进一步根据正则表达式，判断其类型。
其中，__cut是隐马尔科夫模型进行词性标注的执行函数。
def __cut_detail(self, sentence):
# 根据正则表达式对未登录词组成的句子进行分割
blocks = re_han_detail.split(sentence)
for blk in blocks:
# 匹配上正则表达式
if re_han_detail.match(blk):
# 利用隐马尔科夫模型对其进行词性标注
for word in self.__cut(blk):
yield word
# 没有匹配上正则表达式
else:
tmp = re_skip_detail.split(blk)
for x in tmp:
if x:
# 匹配为数字
if re_num.match(x):
yield pair(x, 'm')
# 匹配为英文
elif re_eng.match(x):
yield pair(x, 'eng')
# 匹配为未知类型
else:
yield pair(x, 'x')__cut函数会首先执行Viterbi算法，由Viterbi算法得到状态序列（包含分词及词性标注），也就可以根据状态序列得到分词结果。其中状态以B开头，离它最近的以E结尾的一个子状态序列或者单独为S的子状态序列，就是一个分词。以”去北京大玩学城“为例，其中，“去“和”北京”在前缀词典中有，因此直接通过词–词性词典对其匹配即可，它俩的词性分别为“去/v”，“北京/ns”；而对于”大玩学城“这个句子，是未登录词，因此对其利用隐马尔科夫模型对其进行词性标志，它的隐藏状态序列就是[(u’S’, u’a’), (u’B’, u’n’), (u’E’, u’n’), (u’B’, u’n’)]这个列表，列表中的每个元素为一个元组，则分词为”S / BE / B“，对应观测序列，也就是”大 / 玩学 / 城”。
def __cut(self, sentence):
# 执行Viterbi算法
prob, pos_list = viterbi(
sentence, char_state_tab_P, start_P, trans_P, emit_P)
begin, nexti = 0, 0
for i, char in enumerate(sentence):
# 根据状态进行分词
pos = pos_list[i][0]
if pos == 'B':
begin = i
elif pos == 'E':
yield pair(sentence[begin:i + 1], pos_list[i][1])
nexti = i + 1
elif pos == 'S':
yield pair(char, pos_list[i][1])
nexti = i + 1
if nexti < len(sentence):
yield pair(sentence[nexti:], pos_list[nexti][1])4.4 Viterbi算法
viterbi函数是在jieba/posseg/viterbi.py文件中实现。实现过程非常类似于结巴分词3–基于汉字成词能力的HMM模型识别未登录词 这篇blog 3.3 章节中讲解的。
其中，obs是观测序列，也即待标注的句子；
states是每个词可能的状态，在jieba/posseg/char_state_tab.py文件中定义，格式如下，表示字“一”（\u4e00）可能的状态包括1）“B”表明位于词的开始位置，“m”表示词性为为数词；2）“S”表明单字成词，“m”表示词性为为数词等等状态。
P={‘\u4e00’: ((‘B’, ‘m’),
(‘S’, ‘m’),
(‘B’, ‘d’),
(‘B’, ‘a’),
(‘M’, ‘m’),
(‘B’, ‘n’),
…
}
start_p，是初始状态，在jieba/posseg/prob_start.py文件中定义，格式如下，表示1）“B”表明位于词的开始位置，“a”表示为形容词，其对数概率为-4.762305214596967；2）=）“B”表明位于词的开始位置，“b”表示为区别词（取汉字“别”的声母），其初始概率的对数值为-5.018374362109218等等状态。
P={(‘B’, ‘a’): -4.762305214596967,
(‘B’, ‘ad’): -6.680066036784177,
(‘B’, ‘ag’): -3.14e+100,
(‘B’, ‘an’): -8.697083223018778,
(‘B’, ‘b’): -5.018374362109218,
…
}
trans_p，是状态转移概率，在jieba/posseg/prob_trans.py文件中定义中定义，格式如下，表示1）前一时刻的状态为（“B”和“a”），也即前一个字为词的开始位置，词性为形容词，当前时刻的状态为（“E”和“a”），也即当前字位于词的末尾位置，词性为形容词，它的状态转移概率的对数值为-0.0050648453069648755等等状态。
P={(‘B’, ‘a’): {(‘E’, ‘a’): -0.0050648453069648755,
(‘M’, ‘a’): -5.287963037107507},
(‘B’, ‘ad’): {(‘E’, ‘ad’): -0.0007479013978476627,
(‘M’, ‘ad’): -7.198613337130562},
(‘B’, ‘ag’): {},
(‘B’, ‘an’): {(‘E’, ‘an’): 0.0},
…
}
emit_p，是状态发射概率，在jieba/posseg/prob_emit.py文件中定义中定义，格式如下，表示1）当前状态为（“B”和“a”），也即当前字位于词的开始位置，词性为形容词，到汉字“一”的发射概率的对数值为-3.618715666782108；2）到汉字“万”（\u4e07）的发射概率的对数值为-10.500566885381515。
P={(‘B’, ‘a’): {‘\u4e00’: -3.618715666782108,
‘\u4e07’: -10.500566885381515,
‘\u4e0a’: -8.541143017159477,
‘\u4e0b’: -8.445222895280738,
‘\u4e0d’: -2.7990867583580403,
‘\u4e11’: -7.837979058356061,
…
}
viterbi函数会先计算各个初始状态的对数概率值，然后递推计算，依次1）获取前一时刻所有的状态集合；2）根据前一时刻的状态和状态转移矩阵，提前计算当前时刻的状态集合，再根据当前的观察值获得当前时刻的可能状态集合，再与上一步骤计算的状态集合取交集；3）根据每时刻当前所处的状态，其对数概率值取决于上一时刻的对数概率值、上一时刻的状态到这一时刻的状态的转移概率、这一时刻状态转移到当前的字的发射概率三部分组成。最后再根据最大概率路径依次回溯，得到最优的路径，也即为要求的各个时刻的状态。
jieba分词中的状态如何选取？在模型的数据是如何生成的？ #7中提到，
状态多一些使得分词更准确这一点我也赞同。其实，在jieba分词的词性标注子模块posseg中，就是将BMES四种状态和20集中词性做笛卡尔集得到所有的状态，最后的效果也的确比finalseg要好，尤其是人名识别方面，但是速度就严重下降了。https://github.com/fxsjy/jieba/blob/master/jieba/posseg/prob_start.py
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}] # tabular
mem_path = [{}]
# 根据状态转移矩阵，获取所有可能的状态
all_states = trans_p.keys()
# 时刻t=0，初始状态
for y in states.get(obs[0], all_states): # init
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
mem_path[0][y] = ''
# 时刻t=1,...,len(obs) - 1
for t in xrange(1, len(obs)):
V.append({})
mem_path.append({})
#prev_states = get_top_states(V[t-1])
# 获取前一时刻所有的状态集合
prev_states = [
x for x in mem_path[t - 1].keys() if len(trans_p[x]) > 0]
# 根据前一时刻的状态和状态转移矩阵，提前计算当前时刻的状态集合
prev_states_expect_next = set(
(y for x in prev_states for y in trans_p[x].keys()))
# 根据当前的观察值获得当前时刻的可能状态集合，再与上一步骤计算的状态集合取交集
obs_states = set(
states.get(obs[t], all_states)) & prev_states_expect_next
# 如果当前状态的交集集合为空
if not obs_states:
# 如果提前计算当前时刻的状态集合不为空，则当前时刻的状态集合为提前计算当前时刻的状态集合，否则为全部可能的状态集合
obs_states = prev_states_expect_next if prev_states_expect_next else all_states
# 当前时刻所处的各种可能的状态集合
for y in obs_states:
# 分别获取上一时刻的状态的概率对数，该状态到本时刻的状态的转移概率对数，本时刻的状态的发射概率对数
# prev_states是当前时刻的状态所对应上一时刻可能的状态集合
prob, state = max((V[t - 1][y0] + trans_p[y0].get(y, MIN_INF) +
emit_p[y].get(obs[t], MIN_FLOAT), y0) for y0 in prev_states)
V[t][y] = prob
mem_path[t][y] = state
# 最后一个时刻
last = [(V[-1][y], y) for y in mem_path[-1].keys()]
# if len(last)==0:
# print obs
prob, state = max(last)
# 从时刻t = len(obs) - 1,...,0，依次将最大概率对应的状态保存在列表中
route = [None] * len(obs)
i = len(obs) - 1
while i >= 0:
route[i] = state
state = mem_path[i][state]
i -= 1
# 返回最大概率及各个时刻的状态
return (prob, route)1 简介
关键词抽取就是从文本里面把跟这篇文档意义最相关的一些词抽取出来。这个可以追溯到文献检索初期，当时还不支持全文搜索的时候，关键词就可以作为搜索这篇论文的词语。因此，目前依然可以在论文中看到关键词这一项。
除了这些，关键词还可以在文本聚类、分类、自动摘要等领域中有着重要的作用。比如在聚类时将关键词相似的几篇文档看成一个团簇，可以大大提高聚类算法的收敛速度；从某天所有的新闻中提取出这些新闻的关键词，就可以大致了解那天发生了什么事情；或者将某段时间内几个人的微博拼成一篇长文本，然后抽取关键词就可以知道他们主要在讨论什么话题。
总之，关键词就是最能够反映出文本主题或者意思的词语。但是网络上写文章的人不会像写论文那样告诉你本文的关键词是什么，这个时候就需要利用计算机自动抽取出关键词，算法的好坏直接决定了后续步骤的效果。
关键词抽取从方法来说大致有两种：
- 第一种是关键词分配，就是有一个给定的关键词库，然后新来一篇文档，从词库里面找出几个词语作为这篇文档的关键词；
- 第二种是关键词抽取，就是新来一篇文档，从文档中抽取一些词语作为这篇文档的关键词；
目前大多数领域无关的关键词抽取算法（领域无关算法的意思就是无论什么主题或者领域的文本都可以抽取关键词的算法）和它对应的库都是基于后者的。从逻辑上说，后者比前着在实际使用中更有意义。
从算法的角度来看，关键词抽取算法主要有两类：
- 有监督学习算法，将关键词抽取过程视为二分类问题，先抽取出候选词，然后对于每个候选词划定标签，要么是关键词，要么不是关键词，然后训练关键词抽取分类器。当新来一篇文档时，抽取出所有的候选词，然后利用训练好的关键词抽取分类器，对各个候选词进行分类，最终将标签为关键词的候选词作为关键词；
- 无监督学习算法，先抽取出候选词，然后对各个候选词进行打分，然后输出topK个分值最高的候选词作为关键词。根据打分的策略不同，有不同的算法，例如TF-IDF，TextRank等算法；
jieba分词系统中实现了两种关键词抽取算法，分别是基于TF-IDF关键词抽取算法和基于TextRank关键词抽取算法，两类算法均是无监督学习的算法，下面将会通过实例讲解介绍如何使用jieba分词的关键词抽取接口以及通过源码讲解其实现的原理。
2 示例
下面将会依次介绍利用jieba分词系统中的TF-IDF及TextRank接口抽取关键词的过程。
2.1 基于TF-IDF算法进行关键词抽取
基于TF-IDF算法进行关键词抽取的示例代码如下所示，
from jieba import analyse
# 引入TF-IDF关键词抽取接口
tfidf = analyse.extract_tags
# 原始文本
text = "线程是程序执行时的最小单位，它是进程的一个执行流，\
是CPU调度和分派的基本单位，一个进程可以由很多个线程组成，\
线程间共享进程的所有资源，每个线程有自己的堆栈和局部变量。\
线程由CPU独立调度执行，在多CPU环境下就允许多个线程同时运行。\
同样多线程也可以实现并发操作，每个请求分配一个线程来处理。"
# 基于TF-IDF算法进行关键词抽取
keywords = tfidf(text)
print "keywords by tfidf:"
# 输出抽取出的关键词
for keyword in keywords:
print keyword + "/",控制台输出，
keywords by tfidf:
线程/ CPU/ 进程/ 调度/ 多线程/ 程序执行/ 每个/ 执行/ 堆栈/ 局部变量/ 单位/ 并发/ 分派/ 一个/ 共享/ 请求/ 最小/ 可以/ 允许/ 分配/ 2.2 基于TextRank算法进行关键词抽取
基于TextRank算法进行关键词抽取的示例代码如下所示，
from jieba import analyse
# 引入TextRank关键词抽取接口
textrank = analyse.textrank
# 原始文本
text = "线程是程序执行时的最小单位，它是进程的一个执行流，\
是CPU调度和分派的基本单位，一个进程可以由很多个线程组成，\
线程间共享进程的所有资源，每个线程有自己的堆栈和局部变量。\
线程由CPU独立调度执行，在多CPU环境下就允许多个线程同时运行。\
同样多线程也可以实现并发操作，每个请求分配一个线程来处理。"
print "\nkeywords by textrank:"
# 基于TextRank算法进行关键词抽取
keywords = textrank(text)
# 输出抽取出的关键词
for keyword in keywords:
print keyword + "/",控制台输出，
keywords by textrank:
线程/ 进程/ 调度/ 单位/ 操作/ 请求/ 分配/ 允许/ 基本/ 共享/ 并发/ 堆栈/ 独立/ 执行/ 分派/ 组成/ 资源/ 实现/ 运行/ 处理/3 理论分析
下面将会依次分析TF-IDF算法及TextRank算法的原理。
3.1 TF-IDF算法分析
在信息检索理论中，TF-IDF是Term Frequency – Inverse Document Frequency的简写。TF-IDF是一种数值统计，用于反映一个词对于语料中某篇文档的重要性。在信息检索和文本挖掘领域，它经常用于因子加权。
TF-IDF的主要思想就是：如果某个词在一篇文档中出现的频率高，也即TF高；并且在语料库中其他文档中很少出现，即DF的低，也即IDF高，则认为这个词具有很好的类别区分能力。
TF-IDF在实际中主要是将二者相乘，也即TF * IDF，TF为词频（Term Frequency），表示词t在文档d中出现的频率；IDF为反文档频率（Inverse Document Frequency），表示语料库中包含词t的文档的数目的倒数。
TF公式：
TF计算公式为，
TF=count(t)count(di)TF=count(t)count(di)
式中，count(t)表示文档di中包含词t的个数；
count(di)表示文档di的词的总数；
IDF公式：
IDF计算公式为，
IDF=num(corpus)num(t)+1IDF=num(corpus)num(t)+1
式中，num(corpus)表示语料库corpus中文档的总数；
num(t)表示语料库corpus中包含t的文档的数目；
应用到关键词抽取：
1. 预处理，首先进行分词和词性标注，将满足指定词性的词作为候选词；
2. 分别计算每个词的TF-IDF值；
3. 根据每个词的TF-IDF值降序排列，并输出指定个数的词汇作为可能的关键词；3.2 TextRank算法分析
类似于PageRank的思想，将文本中的语法单元视作图中的节点，如果两个语法单元存在一定语法关系（例如共现），则这两个语法单元在图中就会有一条边相互连接，通过一定的迭代次数，最终不同的节点会有不同的权重，权重高的语法单元可以作为关键词。
节点的权重不仅依赖于它的入度结点，还依赖于这些入度结点的权重，入度结点越多，入度结点的权重越大，说明这个结点的权重越高；
TextRank迭代计算公式为，
WS(Vi)=(1−d)+d∗∑Vj∈In(Vi)wji∑Vk∈Out(Vj)wjk∗WS(Vj)WS(Vi)=(1−d)+d∗∑Vj∈In(Vi)wji∑Vk∈Out(Vj)wjk∗WS(Vj)
节点i的权重取决于节点i的邻居节点中i-j这条边的权重 / j的所有出度的边的权重 * 节点j的权重，将这些邻居节点计算的权重相加，再乘上一定的阻尼系数，就是节点i的权重；
阻尼系数 d 一般取0.85；
算法通用流程：
1. 标识文本单元，并将其作为顶点加入到图中；
2. 标识文本单元之间的关系，使用这些关系作为图中顶点之间的边，边可以是有向或者无向，加权或者无权；
3. 基于上述公式，迭代直至收敛；
4. 按照顶点的分数降序排列；-
1.本模型使用co-occurrence关系，如果两个顶点相应的语义单元共同出现在一个窗口中（窗口大小从2-10不等），那么就连接这两个顶点；
-
2.添加顶点到图中时，需要考虑语法过滤，例如只保留特定词性（如形容词和名词）的词；
应用到关键短语抽取：
1. 预处理，首先进行分词和词性标注，将单个word作为结点添加到图中；
2. 设置语法过滤器，将通过语法过滤器的词汇添加到图中；出现在一个窗口中的词汇之间相互形成一条边；
3. 基于上述公式，迭代直至收敛；一般迭代20-30次，迭代阈值设置为0.0001；
4. 根据顶点的分数降序排列，并输出指定个数的词汇作为可能的关键词；
5. 后处理，如果两个词汇在文本中前后连接，那么就将这两个词汇连接在一起，作为关键短语；4 源码分析
jieba分词的关键词抽取功能，是在jieba/analyse目录下实现的。
其中，__init__.py主要用于封装jieba分词的关键词抽取接口；
tfidf.py实现了基于TF-IDF算法抽取关键词；
textrank.py实现了基于TextRank算法抽取关键词；
4.1 TF-IDF算法抽取关键词源码分析
基于TF-IDF算法抽取关键词的主调函数是TFIDF.extract_tags函数，主要是在jieba/analyse/tfidf.py中实现。
其中TFIDF是为TF-IDF算法抽取关键词所定义的类。类在初始化时，默认加载了分词函数tokenizer = jieba.dt、词性标注函数postokenizer = jieba.posseg.dt、停用词stop_words = self.STOP_WORDS.copy()、idf词典idf_loader = IDFLoader(idf_path or DEFAULT_IDF)等，并获取idf词典及idf中值（如果某个词没有出现在idf词典中，则将idf中值作为这个词的idf值）。
def __init__(self, idf_path=None):
# 加载
self.tokenizer = jieba.dt
self.postokenizer = jieba.posseg.dt
self.stop_words = self.STOP_WORDS.copy()
self.idf_loader = IDFLoader(idf_path or DEFAULT_IDF)
self.idf_freq, self.median_idf = self.idf_loader.get_idf()然后开始通过TF-IDF算法进行关键词抽取。
首先根据是否传入了词性限制集合，来决定是调用词性标注接口还是调用分词接口。例如，词性限制集合为[“ns”, “n”, “vn”, “v”, “nr”]，表示只能从词性为地名、名词、动名词、动词、人名这些词性的词中抽取关键词。
1） 如果传入了词性限制集合，首先调用词性标注接口，对输入句子进行词性标注，得到分词及对应的词性；依次遍历分词结果，如果该词的词性不在词性限制集合中，则跳过；如果词的长度小于2，或者词为停用词，则跳过；最后将满足条件的词添加到词频词典中，出现的次数加1；然后遍历词频词典，根据idf词典得到每个词的idf值，并除以词频词典中的次数总和，得到每个词的tf * idf值；如果设置了权重标志位，则根据tf-idf值对词频词典中的词进行降序排序，然后输出topK个词作为关键词；
2） 如果没有传入词性限制集合，首先调用分词接口，对输入句子进行分词，得到分词；依次遍历分词结果，如果词的长度小于2，或者词为停用词，则跳过；最后将满足条件的词添加到词频词典中，出现的次数加1；然后遍历词频词典，根据idf词典得到每个词的idf值，并除以词频词典中的次数总和，得到每个词的tf * idf值；如果设置了权重标志位，则根据tf-idf值对词频词典中的词进行降序排序，然后输出topK个词作为关键词；
def extract_tags(self, sentence, topK=20, withWeight=False, allowPOS=(), withFlag=False):
# 传入了词性限制集合
if allowPOS:
allowPOS = frozenset(allowPOS)
# 调用词性标注接口
words = self.postokenizer.cut(sentence)
# 没有传入词性限制集合
else:
# 调用分词接口
words = self.tokenizer.cut(sentence)
freq = {}
for w in words:
if allowPOS:
if w.flag not in allowPOS:
continue
elif not withFlag:
w = w.word
wc = w.word if allowPOS and withFlag else w
# 判断词的长度是否小于2，或者词是否为停用词
if len(wc.strip()) < 2 or wc.lower() in self.stop_words:
continue
# 将其添加到词频词典中，次数加1
freq[w] = freq.get(w, 0.0) + 1.0
# 统计词频词典中的总次数
total = sum(freq.values())
for k in freq:
kw = k.word if allowPOS and withFlag else k
# 计算每个词的tf-idf值
freq[k] *= self.idf_freq.get(kw, self.median_idf) / total
# 根据tf-idf值进行排序
if withWeight:
tags = sorted(freq.items(), key=itemgetter(1), reverse=True)
else:
tags = sorted(freq, key=freq.__getitem__, reverse=True)
# 输出topK个词作为关键词
if topK:
return tags[:topK]
else:
return tags4.2 TextRank算法抽取关键词源码分析
基于TextRank算法抽取关键词的主调函数是TextRank.textrank函数，主要是在jieba/analyse/textrank.py中实现。
其中，TextRank是为TextRank算法抽取关键词所定义的类。类在初始化时，默认加载了分词函数和词性标注函数tokenizer = postokenizer = jieba.posseg.dt、停用词表stop_words = self.STOP_WORDS.copy()、词性过滤集合pos_filt = frozenset((‘ns’, ‘n’, ‘vn’, ‘v’))，窗口span = 5，((“ns”, “n”, “vn”, “v”))表示词性为地名、名词、动名词、动词。
首先定义一个无向有权图，然后对句子进行分词；依次遍历分词结果，如果某个词i满足过滤条件（词性在词性过滤集合中，并且词的长度大于等于2，并且词不是停用词），然后将这个词之后窗口范围内的词j（这些词也需要满足过滤条件），将它们两两（词i和词j）作为key，出现的次数作为value，添加到共现词典中；
然后，依次遍历共现词典，将词典中的每个元素，key = （词i，词j），value = 词i和词j出现的次数，其中词i，词j作为一条边起始点和终止点，共现的次数作为边的权重，添加到之前定义的无向有权图中。
然后对这个无向有权图进行迭代运算textrank算法，最终经过若干次迭代后，算法收敛，每个词都对应一个指标值；
如果设置了权重标志位，则根据指标值值对无向有权图中的词进行降序排序，最后输出topK个词作为关键词；
def textrank(self, sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v'), withFlag=False):
self.pos_filt = frozenset(allowPOS)
# 定义无向有权图
g = UndirectWeightedGraph()
# 定义共现词典
cm = defaultdict(int)
# 分词
words = tuple(self.tokenizer.cut(sentence))
# 依次遍历每个词
for i, wp in enumerate(words):
# 词i 满足过滤条件
if self.pairfilter(wp):
# 依次遍历词i 之后窗口范围内的词
for j in xrange(i + 1, i + self.span):
# 词j 不能超出整个句子
if j >= len(words):
break
# 词j不满足过滤条件，则跳过
if not self.pairfilter(words[j]):
continue
# 将词i和词j作为key，出现的次数作为value，添加到共现词典中
if allowPOS and withFlag:
cm[(wp, words[j])] += 1
else:
cm[(wp.word, words[j].word)] += 1
# 依次遍历共现词典的每个元素，将词i，词j作为一条边起始点和终止点，共现的次数作为边的权重
for terms, w in cm.items():
g.addEdge(terms[0], terms[1], w)
# 运行textrank算法
nodes_rank = g.rank()
# 根据指标值进行排序
if withWeight:
tags = sorted(nodes_rank.items(), key=itemgetter(1), reverse=True)
else:
tags = sorted(nodes_rank, key=nodes_rank.__getitem__, reverse=True)
# 输出topK个词作为关键词
if topK:
return tags[:topK]
else:
return tags其中，无向有权图的的定义及实现是在UndirectWeightedGraph类中实现的。根据UndirectWeightedGraph类的初始化函数__init__，我们可以发现，所谓的无向有权图就是一个词典，词典的key是后续要添加的词，词典的value，则是一个由（起始点，终止点，边的权重）构成的三元组所组成的列表，表示以这个词作为起始点的所有的边。
无向有权图添加边的操作是在addEdge函数中完成的，因为是无向图，所以我们需要依次将start作为起始点，end作为终止点，然后再将start作为终止点，end作为起始点，这两条边的权重是相同的。
def addEdge(self, start, end, weight):
# use a tuple (start, end, weight) instead of a Edge object
self.graph[start].append((start, end, weight))
self.graph[end].append((end, start, weight))执行textrank算法迭代是在rank函数中完成的。
首先对每个结点赋予相同的权重，以及计算出该结点的所有出度的次数之和；
然后迭代若干次，以确保得到稳定的结果；
在每一次迭代中，依次遍历每个结点；对于结点n，首先根据无向有权图得到结点n的所有
入度结点（对于无向有权图，入度结点与出度结点是相同的，都是与结点n相连的结点），在前面我们已经计算出这个入度结点的所有出度的次数，而它对于结点n的权值的贡献等于它本身的权值 乘以 它与结点n的共现次数 / 这个结点的所有出度的次数 ，将各个入度结点得到的权值相加，再乘以一定的阻尼系数，即可得到结点n的权值；
迭代完成后，对权值进行归一化，并返回各个结点及其对应的权值。
def rank(self):
ws = defaultdict(float)
outSum = defaultdict(float)
wsdef = 1.0 / (len(self.graph) or 1.0)
# 初始化各个结点的权值
# 统计各个结点的出度的次数之和
for n, out in self.graph.items():
ws[n] = wsdef
outSum[n] = sum((e[2] for e in out), 0.0)
# this line for build stable iteration
sorted_keys = sorted(self.graph.keys())
# 遍历若干次
for x in xrange(10): # 10 iters
# 遍历各个结点
for n in sorted_keys:
s = 0
# 遍历结点的入度结点
for e in self.graph[n]:
# 将这些入度结点贡献后的权值相加
# 贡献率 = 入度结点与结点n的共现次数 / 入度结点的所有出度的次数
s += e[2] / outSum[e[1]] * ws[e[1]]
# 更新结点n的权值
ws[n] = (1 - self.d) + self.d * s
(min_rank, max_rank) = (sys.float_info[0], sys.float_info[3])
# 获取权值的最大值和最小值
for w in itervalues(ws):
if w < min_rank:
min_rank = w
if w > max_rank:
max_rank = w
# 对权值进行归一化
for n, w in ws.items():
# to unify the weights, don't *100.
ws[n] = (w - min_rank / 10.0) / (max_rank - min_rank / 10.0)
return ws4.3 使用自定义停用词集合
jieba分词中基于TF-IDF算法抽取关键词以及基于TextRank算法抽取关键词均需要利用停用词对候选词进行过滤。实现TF-IDF算法抽取关键词的类TFIDF和实现TextRank算法抽取关键词的类TextRank都是类KeywordExtractor的子类。而在类KeywordExtractor，实现了一个方法，可以根据用户指定的路径，加载用户提供的停用词集合。
类KeywordExtractor是在jieba/analyse/tfidf.py中实现。
类KeywordExtractor首先提供了一个默认的名为STOP_WORDS的停用词集合。
然后，类KeywordExtractor实现了一个方法set_stop_words，可以根据用户指定的路径，加载用户提供的停用词集合。
可以将extra_dict/stop_words.txt拷贝出来，并在文件末尾两行分别加入“一个”和
“每个”这两个词，作为用户提供的停用词文件，使用用户提供的停用词集合进行关键词抽取的实例代码如下，
from jieba import analyse
# 引入TF-IDF关键词抽取接口
tfidf = analyse.extract_tags
# 使用自定义停用词集合
analyse.set_stop_words("stop_words.txt")
# 原始文本
text = "线程是程序执行时的最小单位，它是进程的一个执行流，\
是CPU调度和分派的基本单位，一个进程可以由很多个线程组成，\
线程间共享进程的所有资源，每个线程有自己的堆栈和局部变量。\
线程由CPU独立调度执行，在多CPU环境下就允许多个线程同时运行。\
同样多线程也可以实现并发操作，每个请求分配一个线程来处理。"
# 基于TF-IDF算法进行关键词抽取
keywords = tfidf(text)
print "keywords by tfidf:"
# 输出抽取出的关键词
for keyword in keywords:
print keyword + "/",关键词结果为，
keywords by tfidf:
线程/ CPU/ 进程/ 调度/ 多线程/ 程序执行/ 执行/ 堆栈/ 局部变量/ 单位/ 并发/ 分派/ 共享/ 请求/ 最小/ 可以/ 允许/ 分配/ 多个/ 运行/对比章节2.1中的关键词抽取结果，可以发现“一个”和“每个”这两个词没有抽取出来。
keywords by tfidf:
线程/ CPU/ 进程/ 调度/ 多线程/ 程序执行/ 每个/ 执行/ 堆栈/ 局部变量/ 单位/ 并发/ 分派/ 一个/ 共享/ 请求/ 最小/ 可以/ 允许/ 分配/ 实现原理 ，这里仍然以基于TF-IDF算法抽取关键词为例。
前面已经介绍了，jieba/analyse/__init__.py主要用于封装jieba分词的关键词抽取接口，在__init__.py首先将类TFIDF实例化为对象default_tfidf，而类TFIDF在初始化时会设置停用词表，我们知道类TFIDF是类KeywordExtractor的子类，而类KeywordExtractor中提供了一个名为STOP_WORDS的停用词集合，因此类TFIDF在初始化时先将类KeywordExtractor中的STOP_WORDS拷贝过来，作为自己的停用词集合stop_words。
# 实例化TFIDF类
default_tfidf = TFIDF()
# 实例化TextRank类
default_textrank = TextRank()
extract_tags = tfidf = default_tfidf.extract_tags
set_idf_path = default_tfidf.set_idf_path
textrank = default_textrank.extract_tags
# 用户设置停用词集合接口
def set_stop_words(stop_words_path):
# 更新对象default_tfidf中的停用词集合
default_tfidf.set_stop_words(stop_words_path)
# 更新对象default_textrank中的停用词集合
default_textrank.set_stop_words(stop_words_path)如果用户需要使用自己提供的停用词集合，则需要调用analyse.set_stop_words(stop_words_path)这个函数，set_stop_words函数是在类KeywordExtractor实现的。set_stop_words函数执行时，会更新对象default_tfidf中的停用词集合stop_words，当set_stop_words函数执行完毕时，stop_words也就是更新后的停用词集合。我们可以做个实验，验证在调用analyse.set_stop_words(stop_words_path)函数前后，停用词集合是否发生改变。
from jieba import analyse
import copy
# 将STOP_WORDS集合深度拷贝出来
stopwords0 = copy.deepcopy(analyse.default_tfidf.STOP_WORDS)
# 设置用户自定停用词集合之前，将停用词集合深度拷贝出来
stopwords1 = copy.deepcopy(analyse.default_tfidf.stop_words)
print stopwords0 == stopwords1
print stopwords1 - stopwords0
# 设置用户自定停用词集合
analyse.set_stop_words("stop_words.txt")
# 设置用户自定停用词集合之后，将停用词集合深度拷贝出来
stopwords2 = copy.deepcopy(analyse.default_tfidf.stop_words)
print stopwords1 == stopwords2
print stopwords2 - stopwords1结果如下所示，
True
set([])
False
set([u'\u6bcf\u4e2a', u'\u8207', u'\u4e86', u'\u4e00\u500b', u'\u800c', u'\u4ed6\u5011', u'\u6216', u'\u7684', u'\u4e00\u4e2a', u'\u662f', u'\u5c31', u'\u4f60\u5011', u'\u5979\u5011', u'\u6c92\u6709', u'\u57fa\u672c', u'\u59b3\u5011', u'\u53ca', u'\u548c', u'\u8457', u'\u6211\u5011', u'\u662f\u5426', u'\u90fd'])说明：
- 没有加载用户提供的停用词集合之前，停用词集合就是类KeywordExtractor中的STOP_WORDS拷贝过来的；
- 加载用户提供的停用词集合之后，停用词集合在原有的基础上进行了扩；
证明了我们的想法。
原文请参考：
http://www.cnblogs.com/zhbzz2007/p/6076246.html
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/148639.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
