自然语言处理之中文自动分词

摘要：中文分词技术属于自然语言处理技术范畴，中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。诸如机器翻译（MT）、语音合成、自动分类、自动摘要、自动校对等等。本章首先介绍中文分词及其特点和难点，其次对常用的中文分词方法进行阐述；紧接着我们将介绍几个典型的中文分词工具，有兴趣的读者还可对文中所列出的其他工具自行深入研究。最后，本章将对结巴中文分词进行详细介绍，从原理到使用逐渐深入，力求让读者快速掌握其思想及原理。（本文原创，转载必须注明出处.）

中文分词简介

中文分词

中文分词指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。我们知道，在英文的行文中，单词之间是以空格作为自然分界符的，而中文只是句段能通过明显的分界符来简单划界，而词是没有一个形式上的分界符的。虽然英文也同样存在短语的划分问题，不过在词这一层上，中文比之英文要复杂得多、困难得多。

例如:

英文句子: I am a student.
中文意思: 我是一名学生。

由于英文的语言使用习惯，通过空格我们很容易拆分出单词；而中文字词接线模糊往往不容易区别哪些是“字”，哪些是“词”。这也是为什么我们想把中文的词语进行切分的原因。

中文分词的发展

与英文为代表的印欧语系语言相比，中文由于继承自古代汉语的传统，词语之间常没有分隔。古代汉语中除了连绵词和人名地名等，词通常就是单个汉字，所以当时没有分词书写的必要。而现代汉语中双字或多字词逐渐增多，一个字已经不再等同于一个词了。

在中文里，“词”和“词组”边界模糊。现代汉语的基本表达单元虽然为“词”，且以双字或者多字词居多，但由于人们认识水平的不同，对词和短语的边界还很难去区分。

• 例如：“对随地吐痰者给予处罚”，“随地吐痰者”本身是一个词还是一个短语，不同的人会有不同的标准，同样的“海上”“酒厂”等等，即使是同一个人也可能做出不同判断，如果汉语真的要分词书写，必然会出现混乱，难度很大。

中文分词的方法其实不局限于中文应用，也被应用到英文处理。例如手写识别，英文单词之间的空格就不很清楚，中文分词方法可以反过来帮助判别英文单词的边界。

中文分词的用途

中文分词是文本处理的基础，对于输入的一段中文，成功的进行中文分词，可以达到电脑自动识别语句含义的效果。中文分词技术属于自然语言处理技术范畴，目前在自然语言处理技术中，中文处理技术比西文处理技术要落后很大一截，而许多西文的处理方法中文却不能直接采用，就是因为中文必需有分词这道工序。中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。其他的比如机器翻译（MT）、语音合成、自动分类、自动摘要、自动校对等等，都需要用到分词。因为中文需要分词，可能会影响一些研究，但同时也为一些企业带来机会，因为国外的计算机处理技术要想进入中国市场，首先也是要解决中文分词问题。在中文研究方面，相比外国人来说，中国人有十分明显的优势。

中文分词对于搜索引擎来说，最重要的并不是找到所有结果，因为在上百亿的网页中找到所有结果没有太多的意义，没有人能看得完；相反，最重要的是把最相关的结果排在最前面，这也称为相关度排序。中文分词的准确与否，常常直接影响到对搜索结果的相关度排序。从定性分析来说，搜索引擎的分词算法不同，词库的不同都会影响页面的返回结果。

中文分词的特点和难点

中文分词简而言之就是让计算机在词之间加上边界标记。当前研究所面临的问题和困难主要体现在三个方面：分词的规范、歧义词的切分和未登录词识别。

分词的规范

中文因其自身语言特性的局限，字(词)的界限往往很模糊，关于字(词)的抽象定义和词边界的划定尚没有一个公认的、权威的标准。曾经有专家对母语是汉语者调查结果显示，对汉语文本中“词”的认同率仅有百分之七十左右。正是由于这种不同的主观分词差异，给汉语分词造成了极大的困难。尽管在1992年国家颁布了《信息处理用现代词汉语分词规范》，但是这种规范很容易受主观因素影响，在处理现实问题时也不免相形见绌。

歧义词切分

中文中的歧义词是很普遍的，歧义词即同一个词有多种切分方式，该如何去处理这种问题。普遍认为中文歧义词有三种类型：

• 交集型切分歧义，汉语词如AJB类型，满足AJ和JB分别成词。如“大学生”一种切分方式“大学/生”，另一种切分方式“大/学生”。你很难去判定那种切分正确，即使是人工切分也只能依据上下文，类似的有“结合成”、“美国会”等等。

• 组合型切分歧义，汉语词如AB，满足A，B，AB分别成词。如“郭靖有武功高超的才能”中的“才能”，一种切分“郭靖/有/武功/高超/的/才能”，另一种切分“中国/什么/时候/才/能/达到/发达/国家/水平”显示是不同的切分方式。

• 混合型切分歧义，汉语词包含如上两种共存情况。如“郭靖说这把剑太重了”，其中“太重了”是交集型字段，“太重”是组合型字段。

未登录词（新词）识别

未登录词又称新词。这类词通常指两个方面，其一是词库中没有收录的词，其二是训练语料没有出现过的词。未登录词主要体现在以下几种：

• 新出现的网络用词：如“屌丝”、“蓝牙”、“蓝瘦香菇”、“房姐”、“奥特”、“累觉不爱”等。

• 研究领域名称：特定领域和新出现领域的专有名词。如“苏丹红”、“禽流感”、“埃博拉”、“三聚氰胺”等。

• 其他专有名词：诸如城市名、公司企业、职称名、电影、书籍、专业术语、缩写词等。如“成都”、“阿里巴巴”、“毛主席”、“三少爷的剑”、“NLP”、“川大”等。

综述所述，处理汉语词边界、歧义词切分和未登录词切分问题比较复杂，其中未登录词的影响大大超过了歧义词的影响，所以如何处理未登录词是关键问题。

常见中文分词方法

早在80年代就有中文分词的研究工作，曾有人提出“正向最大匹配法”、“逆向最大匹配法”、“双向扫描匹配法”、“逐词遍历法”等方法，共计多达16种之多。由于这些分词方法多是基于规则和词表的方法，随着统计方法的发展，不少学者提出很多关于统计模型的中文分词方法。关于规则的中文自动方法主要有以下几种：

基于字符串匹配的分词方法

基本思想是基于词典匹配，将待分词的中文文本根据一定规则切分和调整，然后跟词典中的词语进行匹配，匹配成功则按照词典的词分词，匹配失败通过调整或者重新选择，如此反复循环即可。代表方法有基于正向最大匹配和基于逆向最大匹配及双向匹配法。

基于理解的分词方法

基本思想是通过专家系统或者机器学习神经网络方法模拟人的理解能力。前者是通过专家对分词规则的逻辑推理并总结形成特征规则，不断迭代完善规则，其受到资源消耗大和算法复杂度高的制约。后者通过机器模拟人类理解的方式，虽可以取得不错的效果，但是依旧受训练时间长和过拟合等因素困扰。

基于统计的分词方法

关于统计的中文分词方法的基本思想本文整理如下：

• 基于隐马尔可夫模型的中文分词方法。基本思想是通过文本作为观测序列去确定隐藏序列的过程。该方法采用Viterbi算法对新词识别效果不错，但具有生成式模型的缺点，需要计算联合概率，因此随着文本增大存在计算量大问题。
• 基于最大熵模型的中文分词方法。基本思想是学习概率模型时，在可能的概率分布模型中，认为熵最大的进行切分。该法可以避免生成模型的不足，但是存在偏移量问题。
• 基于条件随机场模型的中文分词方法。基本思想主要来源最大熵马尔可夫模型，主要关注的字跟上下文标记位置有关，进而通过解码找到词边界。因此需要大量训练语料，而训练和解码又非常耗时。

综上所述，关于词典和规则的方法其分词速度较快，但是在不同领域取得效果差异很大，还存在构造费时费力、算法复杂度高、移植性差等缺点。基于统计的中文分词，虽然其相较于规则的方法取得不错的效果，但也依然存在模型训练时间长、分词速度慢等问题。针对这些问题，本文提出基于隐马尔可夫统计模型和自定义词典结合的方法，其在分词速度、歧义分析、新词发现和准确率方面都取得不错效果。

典型中文分词工具

Stanford NLP分词

Stanford NLP介绍

Stanford NLP是由斯坦福大学的 NLP 小组开源的 Java 实现的 NLP 工具包，同样对 NLP 领域的各个问题提供了解决办法。斯坦福大学的 NLP 小组是世界知名的研究小组，能将 NLTK 和 Stanford NLP 这两个工具包结合起来使用，那对于自然语言开发者是再好不过了。2004 年 Steve Bird 在 NLTK 中加上了对 Stanford NLP 工具包的支持，通过调用外部的 jar 文件来使用 Stanford NLP 工具包的功能这样一来就变得更为方便好用。

Python 调用Stanford NLP进行中文分词

(1) 安装配置说明

本文以Python 3.5.2和java version “1.8.0_111”版本进行配置，具体安装需要注意以下几点：

1 Stanford NLP 工具包需要 Java 8 及之后的版本，如果出错请检查 Java 版本
2 本文的配置都是以 Stanford NLP 3.6.0 为例，如果使用的是其他版本，请注意替换相应的文件名
3 本文的配置过程以 NLTK 3.2 为例，如果使用 NLTK 3.1，需要注意该旧版本中 StanfordSegmenter 未实现，其余大致相同
4 下面的配置过程是具体细节可以参照：http://nlp.stanford.edu/software/

(2) 下载必要工具包

只需要下载以下3个文件就够了，stanfordNLTK文件里面就是StanfordNLP工具包在NLTK中所依赖的jar包和相关文件.

1 stanfordNLTK(https://pan.baidu.com/s/1nvEYdfj) ：作者已将所有需要的包和相关文件打包在了一起，下面有具体讲解。
2 Jar1.8(http://pan.baidu.com/s/1miubwq0) ：如果你本机是Java 8以上版本，可以不用下载。
3 NLTK(https://pan.baidu.com/s/1pKA9XuN) ：这个工具包提供Standford NLP接口。

注意：以上文件下载后，Jar如果是1.8的版本可以不用下载，另外两个压缩包下载到本地，解压后拷贝文件夹到你的python安装主路径下，然后cmd进入NLTK下通过python setup.py install即可。后面操作讲路径是进行简单修改即可。（如果不能正常进行分词等操作，查看python是否是3.2以上版本，java是否是8以后版本，jar环境变量是否配置正确）

(3) 对中文进行分词

StanfordSegmenter 中文分词：下载52nlp改过的NLTK包nltk-develop(https://pan.baidu.com/s/1misFxna)，解压后将其拷贝到你的python目录下，进去E:\Python\nltk-develop采用python 编辑器打开setup.py文件，F5运行，输入以下代码：

>>> from nltk.tokenize.stanford_segmenter import StanfordSegmenter
>>> segmenter = StanfordSegmenter(
    path_to_jar=r"E:\tools\stanfordNLTK\jar\stanford-segmenter.jar",
    path_to_slf4j=r"E:\tools\stanfordNLTK\jar\slf4j-api.jar",
    path_to_sihan_corpora_dict=r"E:\tools\stanfordNLTK\jar\data",
    path_to_model=r"E:\tools\stanfordNLTK\jar\data\pku.gz",
    path_to_dict=r"E:\tools\stanfordNLTK\jar\data\dict-chris6.ser.gz"
)
>>> str="我在博客园开了一个博客，我的博客名叫伏草惟存，写了一些自然语言处理的文章。"
>>> result = segmenter.segment(str)
>>> result

程序解读：StanfordSegmenter 的初始化参数说明:

• path_to_jar: 用来定位jar包，本程序分词依赖stanford-segmenter.jar（注: 其他所有 Stanford NLP 接口都有 path_to_jar 这个参数。）
• path_to_slf4j: 用来定位slf4j-api.jar作用于分词
• path_to_sihan_corpora_dict: 设定为 stanford-segmenter-2015-12-09.zip 解压后目录中的 data 目录， data 目录下有两个可用模型 pkg.gz 和 ctb.gz 需要注意的是，使用 StanfordSegmenter 进行中文分词后，其返回结果并不是 list ，而是一个字符串，各个汉语词汇在其中被空格分隔开。

(4) 分词结果

我 在 博客 园 开 了 一个 博客 ， 我 的 博客 名叫 伏 草 惟 存 ， 写 了 一些 自然 语言 处理 的 文章 。

HanLP中文分词

HanLP

HanLP是由一系列模型与算法组成的Java工具包，目标是普及自然语言处理在生产环境中的应用。HanLP具备功能完善、性能高效、架构清晰、语料时新、可自定义等特点。 在提供丰富功能的同时，HanLP内部模块坚持低耦合、模型坚持惰性加载、服务坚持静态提供、词典坚持明文发布，使用起来非常方便，同时自带一些语料处理工具，帮助用户训练自己的语料。

Python调用HanLP进行中文分词

(1) 下载Hanlp的jar包hanlp.jar(http://hanlp.linrunsoft.com/services.html)
(2) 安装配置jre1.7+，本文省略具体安装步骤
(3) 在py文件启动JVM

 
from jpype import *
startJVM(getDefaultJVMPath(), "-Djava.class.path=C:\hanlp\hanlp-1.3.2.jar;
         C:\hanlp", "-Xms1g", "-Xmx1g") # 启动JVM，Linux需替换分号;为冒号:

此处是hanlp的具体调用方法

shutdownJVM()

Python调用hanlp分词

• 默认分词
  

  paraStr1='中国科学院计算技术研究所的宗成庆教授正在教授自然语言处理课程'
  print("="*30+"HanLP分词"+"="*30)
  HanLP = JClass('com.hankcs.hanlp.HanLP')
  print(HanLP.segment(paraStr1))
  

  
  运行结果

==============================HanLP分词==============================
[中国科学院计算技术研究所/nt, 的/ude1, 宗成庆/nr, 教授/nnt, 正在/d, 教授/nnt, 自然语言处理/nz, 课程/n]

• 标准分词
  

  print("="*30+"标准分词"+"="*30)
  StandardTokenizer = JClass('com.hankcs.hanlp.tokenizer.StandardTokenizer')
  print(StandardTokenizer.segment(paraStr1))
  

  
  运行结果

==============================标准分词==============================
[中国科学院计算技术研究所/nt, 的/ude1, 宗成庆/nr, 教授/nnt, 正在/d, 教授/nnt, 自然语言处理/nz, 课程/n]

• NLP分词
  

  print("="*30+"NLP分词"+"="*30)
  NLPTokenizer = JClass('com.hankcs.hanlp.tokenizer.NLPTokenizer')
  print(NLPTokenizer.segment(paraStr1))
  

  
  运行结果

==============================NLP分词==============================
[中国科学院计算技术研究所/nt, 的/ude1, 宗成庆/nr, 教授/nnt, 正在/d, 教授/v, 自然语言处理/nz, 课程/n]

• 索引分词
  

  print("="*30+"索引分词"+"="*30)
  IndexTokenizer = JClass('com.hankcs.hanlp.tokenizer.IndexTokenizer')
  termList= IndexTokenizer.segment(paraStr1);
  for term in termList :
  print(str(term) + " [" + str(term.offset) + ":" + str(term.offset + len(term.word)) + "]")
  

  
  运行结果

==============================索引分词==============================
中国科学院计算技术研究所/nt [0:12]
中国/ns [0:2]
中国科学院/nt [0:5]
科学/n [2:4]
科学院/nis [2:5]
学院/nis [3:5]
计算/v [5:7]
技术/n [7:9]
研究/vn [9:11]
研究所/nis [9:12]
的/ude1 [12:13]
宗成庆/nr [13:16]
自然语言/gm [13:17]
自然语言处理/nz [13:19]
教授/nnt [16:18]
正在/d [18:20]
教授/nnt [20:22]
自然语言处理/nz [22:28]
自然/n [22:24]
语言/n [24:26]
处理/vn [26:28]
课程/n [28:30]

• 极速词典分词
  

  print("="*30+" 极速词典分词"+"="*30)
  SpeedTokenizer = JClass('com.hankcs.hanlp.tokenizer.SpeedTokenizer')
  print(NLPTokenizer.segment(paraStr1))
  

  
  运行结果

============================== 极速词典分词==============================
[中国科学院计算技术研究所/nt, 的/ude1, 宗成庆/nr, 教授/nnt, 正在/d, 教授/v, 自然语言处理/nz, 课程/n]

• 自定义分词
  

  paraStr2 = '攻城狮逆袭单身狗，迎娶白富美，走上人生巅峰'
  print("="*30+" 自定义分词"+"="*30)
  CustomDictionary = JClass('com.hankcs.hanlp.dictionary.CustomDictionary')
  CustomDictionary.add('攻城狮')
  CustomDictionary.add('单身狗')
  HanLP = JClass('com.hankcs.hanlp.HanLP')
  print(HanLP.segment(paraStr2))
  

  
  运行结果

============================== 自定义分词==============================
[攻城狮/nz, 逆袭/nz, 单身狗/nz, ，/w, 迎娶/v, 白富美/nr, ，/w, 走上/v, 人生/n, 巅峰/n]

## 其他中文分词工具 - BosonNLP：玻森实验室开发的一款分词工具 - 语言云：以哈工大社会计算与信息检索研究中心研发的 “语言技术平台（LTP）” 为基础，为用户提供高效精准的中文自然语言处理云服务 - NLPIR：中科院分词系统 - 新浪云 - 搜狗分词 - 结巴分词 - SCWS：简易中文分词系统缩写。SCWS 由 hightman 开发， 并以 BSD 许可协议开源发布，源码托管在 github - 腾讯文智 - 盘古分词 - IKAnalyzer：一个开源的，基于java语言开发的轻量级的中文分词工具包 关于中文分词工具可分为基于规则的分词方法和基于统计的分词方法。本节所给出的相关常见分词工具，读者感兴趣可以自行深入研究。特别说明的是，随着深度学习的快速发展，深度学习在中文分词的应用也越来越流行。由于开发过程中多数开发人员及其相关研究者使用结巴中文分词的比较多，所以本文将其单独立为一节进行深入学习。 # 结巴中文分词 ## 基于Python的结巴中文分词 > 结巴中文分词的特点 (1) 支持三种分词模式： - 精确模式，试图将句子最精确地切开，适合文本分析； - 全模式，把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义； - 搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。 (2) 支持繁体分词 (3) 支持自定义词典 (4) MIT 授权协议 - 在线演示：http://jiebademo.ap01.aws.af.cm/ - 网站代码：https://github.com/fxsjy/jiebademo > 安装说明：代码对 Python 2/3 均兼容 - 全自动安装：easy_install jieba 或者 pip install jieba / pip3 install jieba - 半自动安装：先下载 http://pypi.python.org/pypi/jieba/解压后运行 python setup.py install - 手动安装：将 jieba 目录放置于当前目录或者 site-packages 目录 - 通过 import jieba 来引用 > 结巴分词工具下载 - hanllp jar包（http://download.csdn.net/download/lb521200200/9686915） - ik 分词 5.0.0版本jar包（http://download.csdn.net/download/youyao816/9676084） - ik分词 1.10.1版本jar包（http://download.csdn.net/download/youyao816/9676082） - IKAnalyzer所需的jar包（http://download.csdn.net/download/jingjingchen1014/9659225） - jieba分词包（http://download.csdn.net/download/u014018025/9652341） > 主要分词功能 - 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 直接返回 list - jieba.Tokenizer(dictionary=DEFAULT_DICT) 新建自定义分词器，可用于同时使用不同词典。jieba.dt 为默认分词器，所有全局分词相关函数都是该分词器的映射。 代码示例

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算法识别出来了)
【搜索引擎模式】： 小明, 硕士, 毕业, 于, 中国, 科学, 学院, 科学院, 中国科学院, 计算, 计算所, 后, 在, 日本, 
                  京都, 大学, 日本京都大学, 深造

添加自定义词典

载入词典

• 开发者可以指定自己自定义的词典，以便包含 jieba 词库里没有的词。虽然 jieba 有新词识别能力，但是自行添加新词可以保证更高的正确率
• 用法： jieba.load_userdict(file_name) # file_name 为文件类对象或自定义词典的路径
• 词典格式和 dict.txt 一样，一个词占一行；每一行分三部分：词语、词频（可省略）、词性（可省略），用空格隔开，顺序不可颠倒。file_name 若为路径或二进制方式打开的文件，则文件必须为 UTF-8 编码。
• 词频省略时使用自动计算的能保证分出该词的词频。

例如：

创新办 3 i
云计算 5
凱特琳 nz
台中

自定义分词前后对比

之前： 李小福 / 是 / 创新 / 办 / 主任 / 也 / 是 / 云 / 计算 / 方面 / 的 / 专家 /
加载自定义词库后：　李小福 / 是 / 创新办 / 主任 / 也 / 是 / 云计算 / 方面 / 的 / 专家 /

结巴分词工具详解

结巴分词的算法策略

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

结巴源码组织形式

jieba 
|-- Changelog 
|-- extra_dict 
| |-- dict.txt.big 
| |-- dict.txt.small 
| |-- idf.txt.big 
| `-- stop_words.txt 
|-- jieba 
| |-- analyse 
| | |-- analyzer.py 
| | |-- idf.txt 
| | |-- __init__.py 
| | |-- textrank.py 
| | `-- tfidf.py 
| |-- _compat.py 
| |-- dict.txt 
| |-- finalseg 
| | |-- __init__.py 
| | |-- prob_emit.p 
| | |-- prob_emit.py 
| | |-- prob_start.p 
| | |-- prob_start.py 
| | |-- prob_trans.p 
| | `-- prob_trans.py 
| |-- __init__.py 
| |-- __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 
|-- LICENSE 
|-- setup.py `-- test 
|-- *.py 
|-- parallel 
| |-- extract_tags.py 
| `-- test*.py `-- userdict.txt

算法实现分词

（1） 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);

作者这个版本中使用前缀字典实现了词库的存储(即dict.txt文件中的内容)，而弃用之前版本的trie树存储词库，想想也是，python中实现的trie树是基于dict类型的数据结构而且dict中又嵌套dict 类型，这样嵌套很深，导致内存耗费严重，详情见作者把trie树改成前缀词典的缘由, 具体实现见 gen_pfdict(self, f_name)。接着说DAG有向无环图, 生成句子中汉字所有可能成词情况所构成的有向无环图。DAG根据我们生成的前缀字典来构造一个这样的DAG，对一个sentence DAG是以{key:list[i,j…], …}的字典结构存储，其中key是词的在sentence中的位置，list存放的是在sentence中以key开始且词sentence[key:i+1]在我们的前缀词典中以key开始i结尾的词的末位置i的列表，即list存放的是sentence中以位置key开始的可能词语的结束位置，这样通过查字典得到词, 开始位置+结束位置列表。

例如:句子“抗日战争”生成的DAG中{0:[0,1,3]} 这样一个简单的DAG, 就是表示0位置开始, 在0,1,3位置都是词, 
     就是说0~0,0~1,0~3 即 “抗”，“抗日”，“抗日战争”这三个词 在dict.txt中是词。 

（2）采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
基于上面的DAG利用动态规划查找最大概率路径，这个理解DP算法的很容易就能明白了。根据动态规划查找最大概率路径的基本思路就是对句子从右往左反向计算最大概率。依次类推, 最后得到最大概率路径, 得到最大概率的切分组合（这里满足最优子结构性质，可以利用反证法进行证明），这里代码实现中有个小trick，即概率对数(可以让概率相乘的计算变成对数相加,防止相乘造成下溢，因为在语料、词库中每个词的出现概率平均下来还是很小的浮点数)。

（3）对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法；
未登录词(即jieba中文分词源码分析（一）)中说的OOV， 其实就是词典 dict.txt 中没有记录的词。这里采用了HMM模型,HMM是个简单强大的模型，可以参考这个网络资源进行学习，HMM在实际应用中主要用来解决3类问题:

1. 评估问题(概率计算问题) ：即给定观测序列 O=O1,O2,O3…Ot和模型参数λ=(A,B,π)，怎样有效计算这一观测序列出现的概率. (Forward-backward算法)
2. 解码问题(预测问题) ：即给定观测序列 O=O1,O2,O3…Ot和模型参数λ=(A,B,π)，怎样寻找满足这种观察序列意义上最优的隐含状态序列S。 (viterbi算法,近似算法)
3. 学习问题 ：即HMM的模型参数λ=(A,B,π)未知，如何求出这3个参数以使观测序列O=O1,O2,O3…Ot的概率尽可能的大. (即用极大似然估计的方法估计参数,Baum-Welch,EM算法)

模型的关键相应参数λ=(A,B,π)，经过作者对大量语料的训练, 得到了finalseg目录下的三个文件（初始化状态概率（π）即词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。这个就是起始向量, 就是HMM系统的最初模型状态，对应文件prob start.py；隐含状态概率转移矩A 即字的几种位置状态(BEMS四个状态来标记, B是开始begin位置, E是end, 是结束位置, M是middle, 是中间位置, S是single, 单独成词的位置)的转换概率，对应文件prob trans.py；观测状态发射概率矩阵B 即位置状态到单字的发射概率，比如P(“狗”|M)表示一个词的中间出现”狗”这个字的概率，对应文件prob_emit.py）。

结巴分词核心内容

结巴分词的算法策略

作者在这个版本(0.37)中使用前缀字典实现了词库的存储(即dict.txt文件中的内容)，而弃用之前版本的trie树存储词库，Python中实现的trie树是基于dict类型的数据结构而且dict中又嵌套dict 类型，这样嵌套很深，导致内存耗费严重，具体点这里，下面是@gumblex commit的内容:

对于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空间效率低下的问题。

jieba0.37版本中实际使用是前缀字典具体实现(对应代码中Tokenizer.FREQ字典)，即就是利用python中的dict把dict.txt中出现的词作为key，出现频次作为value，比如sentece : “北京大学”,处理后的结果为：{u’北’:17860, u’北京’ :34488,u’北京大’: 0,u’北京大学’: 2053}，具体详情见代码：def gen_pfdict(self, f_name): > DAG DAG根据我们生成的前缀字典来构造一个这样的DAG，对sentence DAG是以{key:list[i,j…], …}的字典结构存储，其中key是词的在sentence中的位置，list存放的是在sentence中以key开始且词sentence[key:i+1]在我们的前缀词典中 的以key开始i结尾的词的末位置i的列表，即list存放的是sentence中以位置key开始的可能的词语的结束位置，这样通过查字典得到词, 开始位置+结束位置列表。 例如句子”去北京大学玩“对应的DAG为： {0 : [0], 1 : [1, 2, 4], 2 : [2], 3 : [3, 4], 4 : [4], 5 : [5]} 例如DAG中{0:[0]} 这样一个简单的DAG, 就是表示0位置对应的是词, 就是说0~0,即”去”这个词 在dict.txt中是词条。DAG中{1:[1,2,4]}, 就是表示1位置开始, 在1,2,4位置都是词, 就是说1~1,1~2,1~4 即 “北”，“北京”，“北京大学”这三个词 在dict.txt对应文件的词库中。 > 基于词频最大切分组合 通过上面两小节可以得知，我们已经有了词库(dict.txt)的前缀字典和待分词句子sentence的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):
    # [x+1][0]即表示取句子x+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])

从代码中可以看出calc是一个自底向上的动态规划(重叠子问题、最优子结构)，它从sentence的最后一个字(N-1)开始倒序遍历sentence的字(idx)的方式，计算子句sentence[isdx~N-1]概率对数得分（这里利用DAG及历史计算结果route实现，同时使用概率对数以有效防止下溢问题）。然后将概率对数得分最高的情况以（概率对数，词语最后一个字的位置）这样的tuple保存在route中。 根据上面的结束写了如下的测试：输出结果为：

“去北京大学玩”的前缀字典: 
去 123402 
去北 0 
去北京 0 
去北京大 0 
去北京大学 0 
去北京大学玩 0 
“去北京大学玩”的DAG: 
0 : [0] 
1 : [1, 2, 4] 
2 : [2] 
3 : [3, 4] 
4 : [4] 
5 : [5] 
route: 
{0: (-26.039894284878688, 0), 1: (-19.851543754900984, 4), 2: (-26.6931716802707, 2), 
 3: (-17.573864399983357, 4), 4: (-17.709674112779485, 4), 5: (-9.567048044164698, 5), 6: (0, 0)} 
去/北京大学/玩

中文分词的未登录词

因此可以看到，未登录词是分词中的一个重要问题，jieba分词中对于OOV的解决方法是：采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法。

• 分词规范，词的定义还不明确 (《统计自然语言处理》宗成庆)

• 歧义切分问题，交集型切分问题，多义组合型切分歧义等。结婚的和尚未结婚的 => 结婚／的／和／尚未／结婚／的 结婚／的／和尚／未／结婚／的。

• 未登录词问题 有两种解释：一是已有的词表中没有收录的词，二是已有的训练语料中未曾出现过的词，第二种含义中未登录词又称OOV(Out of Vocabulary)。对于大规模真实文本来说，未登录词对于分词的精度的影响远超歧义切分。一些网络新词，自造词一般都属于这些词。

因此可以看到，未登录词是分词中的一个重要问题，jieba分词中对于OOV的解决方法是：采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法。

结巴分词基本用法

安装结巴分词

• 全自动安装：easy_install jieba 或者 pip install jieba / pip3 install jieba
• 半自动安装：先下载 http://pypi.python.org/pypi/jieba/ ，解压后运行 python setup.py install
• 手动安装：将 jieba 目录放置于当前目录或者 site-packages 目录
• 通过 import jieba 来引用

本机是win10 64位，已经安装了pip工具，关于pip下载安装（here），然后win+R，输入pip install jieba，效果如下：

 图9-1 结巴分词安装成功图

结巴几种模式下的分词操作：（以下默认已导入：import jieba）

全模式分词

>>> import jieba
>>> str="我是白宁超来自博客园"
>>> seg_list=jieba.cut(str,cut_all=True)
>>> print("Full Mode: " + "/ ".join(seg_list))  # 全模式
Full Mode: 我/ 是/ 白/ 宁/ 超/ 来自/ 博客/ 博客园

结果分析

显然我的名字：白宁超，没有正确分词，这是因为全模式把句子中所有可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义。

精确模式分词

>>> seg_list=jieba.cut(str,cut_all=False)
>>> print("Default Mode: " + "/ ".join(seg_list))  # 精确模式
Default Mode: 我/ 是/ 白宁超/ 来自/ 博客园
>>> seg_list=jieba.cut(str)
>>> print("Default Mode: " + "/ ".join(seg_list))  # 默认模式
Default Mode: 我/ 是/ 白宁超/ 来自/ 博客园

结果分析

首先默认模式就是精确模式，即cut_all=False。这里很好的将“白宁超”划分为一个词。与全模式分词是有区别的。精确模式适合文本分析。

默认精确模式分词

>>> seg_list = jieba.cut("他来到了网易杭研大厦")  # 默认是精确模式
>>> print("【新词发现】\t"+", ".join(seg_list))
【新词发现】  他, 来到, 了, 网易, 杭研, 大厦

结果分析

此处杭研并没有在词典中，但是也被Viterbi算法识别出来了。实际上是基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法可以发现新词。当然也可以到自定义字典中去收集新词。

搜索引擎模式分词

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

结果分析

在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。

繁体分词

>>> str='''此開卷第一回也．作者自云：因曾歷過一番夢幻之后，故將真事隱去，
而借"通靈"之說，撰此《石頭記》一書也．故曰"甄士隱"云云．但書中所記
何事何人？自又云：“今風塵碌碌，一事無成，忽念及當日所有之女子，一
一細考較去，覺其行止見識，皆出于我之上．何我堂堂須眉，誠不若彼裙釵
哉？實愧則有余，悔又無益之大無可如何之日也！'''
>>> str=jieba.cut(str)
>>> print('/ '.join(str))

此開卷/ 第一回/ 也/ ．/ 作者/ 自云/ ：/ 因曾/ 歷過/ 一番/ 夢/ 幻之后/ ，/ 故將/ 真事/ 隱去/ ，/
/ 而/ 借/ "/ 通靈/ "/ 之/ 說/ ，/ 撰此/ 《/ 石頭記/ 》/ 一書/ 也/ ．/ 故/ 曰/ "/ 甄士/ 隱/ "/ 云云/ ．/ 但書中/ 所記/
/ 何事何/ 人/ ？/ 自又云/ ：/ “/ 今風/ 塵碌碌/ ，/ 一事/ 無成/ ，/ 忽念及/ 當日/ 所/ 有/ 之/ 女子/ ，/ 一/
/ 一細/ 考較/ 去/ ，/ 覺其/ 行止/ 見識/ ，/ 皆/ 出于/ 我/ 之/ 上/ ．/ 何/ 我堂/ 堂須/ 眉/ ，/ 誠不若/ 彼/ 裙釵/
/ 哉/ ？/ 實愧則/ 有/ 余/ ，/ 悔/ 又/ 無益/ 之/ 大/ 無/ 可/ 如何/ 之/ 日/ 也/ ！
>>>

自定义分词器

#encoding=utf-8
from __future__ import print_function, unicode_literals
import sys
sys.path.append("../")
import jieba
jieba.load_userdict("userdict.txt")
import jieba.posseg as pseg

jieba.add_word('凱特琳')
jieba.del_word('自定义词')

test_sent = (
"李小福和李铁军是创新办主任也是云计算方面的专家; 什么是八一双鹿\n"
"例如我输入一个带“韩玉赏鉴”的标题，在自定义词库中也增加了此词为N类\n"
"「台中」正確應該不會被切開。mac上可分出「石墨烯」；此時又可以分出來凱特琳了。"
)
words = jieba.cut(test_sent)
print('/'.join(words))

print("="*40)

result = pseg.cut(test_sent)

for w in result:
    print(w.word, "/", w.flag, ", ", end=' ')

print("\n" + "="*40)

terms = jieba.cut('easy_install is great')
print('/'.join(terms))
terms = jieba.cut('python 的正则表达式是好用的')
print('/'.join(terms))

print("="*40)
# test frequency tune
testlist = [
('今天天气不错', ('今天', '天气')),
('如果放到post中将出错。', ('中', '将')),
('我们中出了一个叛徒', ('中', '出')),
]

for sent, seg in testlist:
    print('/'.join(jieba.cut(sent, HMM=False)))
    word = ''.join(seg)
    print('%s Before: %s, After: %s' % (word, jieba.get_FREQ(word), jieba.suggest_freq(seg, True)))
    print('/'.join(jieba.cut(sent, HMM=False)))
    print("-"*40

结果分析

首先对一段话分词处理,此处“李小福“和“李铁军”都是人名，结果却分词“李小福”和“李铁”，而“军是”当做一个词处理，显然不对。
我们可以将“李铁军”当着一个词加入自定义文本中.处理后结果显然经过自定义分词有所好转。而石墨/烯分词错误。

词性标注

print("="*40)
result = pseg.cut(test_sent)
for w in result:
    print(w.word, "/", w.flag, ", ", end=' ')
print("\n" + "="*40)
terms = jieba.cut('easy_install is great')
print('/'.join(terms))
terms = jieba.cut('python 的正则表达式是好用的')
print('/'.join(terms))
print("="*40) 
# 结果
========================================
李小福 / nr ,  和 / c ,  李铁军 / x ,  是 / v ,  创新办 / i ,  主任 / b ,  也 / d ,  是 / v ,  云计算 / x , 
方面 / n ,  的 / uj ,  专家 / n ,  ; / x ,    / x ,  什么 / r ,  是 / v ,  八一双鹿 / nz , / x ,  例如 / v ,  
我 / r ,  输入 / v ,  一个 / m ,  带 / v ,  “ / x ,  韩玉赏鉴 / nz ,  ” / x ,  的 / uj ,  标题 / n ,  ， / x ,  
在 / p ,  自定义词 / n ,  库中 / nrt ,  也 / d ,  增加 / v ,  了 / ul ,  此 / r ,  词 / n ,  为 / p ,  N / eng ,  
类 / q ,  / x ,  「 / x ,  台中 / s ,  」 / x ,  正確 / ad ,  應該 / v ,  不 / d ,  會 / v ,  被 / p ,  切開 
/ ad ,  。 / x ,  mac / eng ,  上 / f ,  可 / v ,  分出 / v ,  「 / x ,  石墨烯 / x ,  」 / x ,  ； / x ,  
此時 / c ,  又 / d ,  可以 / c ,  分出 / v ,  來 / zg ,  凱特琳 / x ,  了 / ul ,  。 / x , 
========================================
easy_install/ /is/ /great
python/ /的/正则表达式/是/好用/的
========================================

结果分析:
李小福 / nr , 李铁军 / x 都是名字，属于名词，而李铁军 / x显然词性不对，这是由于刚刚jieba.addword(‘李铁军’)时候，没有进行词性参数输入，我们看看jieba.add word(‘李铁军’)源码：

def add_word(self, word, freq=None, tag=None)
jieba.add_word('李铁军',tag='nr')修改后结果

再次查看结果：

李小福 / nr , 和 / c , 李铁军 / nr , 是 / v , 创新办 / i , 主任 / b , 也 / d , 是 / v , 云计算 / x , 方面 / n ,
的 / uj , 专家 / n , ; / x , / x , 什么 / r , 是 / v , 八一双鹿 / nz , / x , 例如 / v , 我 / r , 输入 / v ,
一个 / m , 带 / v , “ / x , 韩玉赏鉴 / nz , ” / x , 的 / uj , 标题 / n , ， / x , 在 / p , 自定义词 / n ,
库中 / nrt , 也 / d , 增加 / v , 了 / ul , 此 / r , 词 / n , 为 / p , N / eng , 类 / q , / x , 「 / x ,
台中 / s , 」 / x , 正確 / ad , 應該 / v , 不 / d , 會 / v , 被 / p , 切開 / ad , 。 / x , mac / eng ,
上 / f , 可 / v , 分出 / v , 「 / x , 石墨烯 / x , 」 / x , ； / x , 此時 / c , 又 / d , 可以 / c ,

分出 / v , 來 / zg , 凱特琳 / x , 了 / ul , 。 / x ,

</pre>

自定义调整词典

# test frequency tune
testlist = [
('今天天气不错', ('今天', '天气')),
('如果放到post中将出错。', ('中', '将')),
('我们中出了一个叛徒', ('一', '个')),
]
for sent, seg in testlist:
    print('/'.join(jieba.cut(sent, HMM=False)))
    word = ''.join(seg)
    print('%s Before: %s, After: %s' % (word, jieba.get_FREQ(word), jieba.suggest_freq(seg, True)))
    print('/'.join(jieba.cut(sent, HMM=False)))
    print("-"*40)
结果：
========================================
今天天气/不错
今天天气 Before: 3, After: 0
今天天气/不错
----------------------------------------
如果/放到/post/中将/出错/。
中将 Before: 763, After: 494
如果/放到/post/中/将/出错/。
----------------------------------------
我们/中/出/了/一个/叛徒
一个 Before: 142747, After: 454
我们/中/出/了/一/个/叛徒
----------------------------------------

结果分析：列表中的每一条数据如(‘今天天气不错’, (‘今天’, ‘天气’)),其中(‘今天’, ‘天气’)调整分词颗粒精度的。如第三句正常分词：我们/中/出/了/一个/叛徒。我们假设某些情况下一和个分别分词，可以做如上处理。

使用 add word(word, freq=None, tag=None) 和 del word(word) 可在程序中动态修改词典。
使用 suggest_freq(segment, tune=True) 可调节单个词语的词频，使其能（或不能）被分出来。
注意：自动计算的词频在使用 HMM 新词发现功能时可能无效。

自定义调节词典解决歧义分词问题

>>> import jieba
>>> print('/'.join(jieba.cut('如果放到post中将出错。', HMM=False)))
Building prefix dict from the default dictionary ...
Loading model from cache C:\Users\cuitbnc\AppData\Local\Temp\jieba.cache
Loading model cost 1.069 seconds.
Prefix dict has been built succesfully.
如果/放到/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)))
「/台中/」/正确/应该/不会/被/切开

词性标注

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

---

参考文献

1. 数据挖掘十大算法：https://wizardforcel.gitbooks.io/dm-algo-top10/content/apriori.html
2. 中文维基百科：https://zh.wikipedia.org/wiki/%E5%85%88%E9%AA%8C%E7%AE%97%E6%B3%95
3. GitHub：https://github.com/BaiNingchao/MachineLearning-1
4. 图书：《机器学习实战》
5. 图书：《自然语言处理理论与实战》

完整代码下载

源码请进【机器学习和自然语言QQ群：436303759】文件下载：

作者声明

本文版权归作者所有，旨在技术交流使用。未经作者同意禁止转载，转载后需在文章页面明显位置给出原文连接，否则相关责任自行承担。