2. 词典分词
- 2.1 什么是词
- 2.2 词典
- 2.3 切分算法
- 2.4 字典树
- 2.5 基于字典树的其它算法
- 2.6 HanLP的词典分词实现
- 中文分词：指的是将一段文本拆分为一系列单词的过程，这些单词顺序拼接后等于原文本。
- 中文分词算法大致分为基于词典规则与基于机器学习这两大派。
2.1 什么是词
-
在基于词典的中文分词中，词的定义要现实得多：词典中的字符串就是词。
-
词的性质–齐夫定律：一个单词的词频与它的词频排名成反比。
2.2 词典
互联网词库(SogouW， 15万个词条)、清华大学开放中文词库(THUOCL)、HanLP词库(千万级词条)
例如：
HanLP中的词典格式是一种以空格分隔的表格形式，第一列是单词本身，之后每两列分别表示词性与相应的词频。
2.3 切分算法
首先，加载词典：
-
完全切分
指的是，找出一段文本中的所有单词。
输出：
输出了所有可能的单词。由于词库中含有单字，所以结果中也出现了一些单字。
-
正向最长匹配
上面的输出并不是中文分词，我们更需要那种有意义的词语序列，而不是所有出现在词典中的单词所构成的链表。比如，我们希望“北京大学”成为一整个词，而不是“北京 + 大学”之类的碎片。具体来说，就是在以某个下标为起点递增查词的过程中，优先输出更长的单词，这种规则被称为最长匹配算法。从前往后匹配则称为正向最长匹配，反之则称为逆向最长匹配。
输出：
第二句话就会产生误差了，我们是需要把“研究”提取出来，结果按照正向最长匹配算法就提取出了“研究生”，所以人们就想出了逆向最长匹配。
-
逆向最长匹配
输出：
第一句正确了，但下一句又出错了，可谓拆东墙补西墙。另一些人提出综合两种规则，期待它们取长补短，称为双向最长匹配。
-
双向最长匹配
这是一种融合两种匹配方法的复杂规则集，流程如下：
- 同时执行正向和逆向最长匹配，若两者的词数不同，则返回词数更少的那一个。
- 否则，返回两者中单字更少的那一个。当单字数也相同时，优先返回逆向最长匹配的结果。
输出：
通过以上几种切分算法，我们可以做一个对比：
上图显示，双向最长匹配的确在2、3、5这3种情况下选择出了最好的结果，但在4号句子上选择了错误的结果，使得最终正确率 3/6 反而小于逆向最长匹配的 4/6 ， 由此，规则系统的脆弱可见一斑。规则集的维护有时是拆东墙补西墙，有时是帮倒忙。
2.4 字典树
匹配算法的瓶颈之一在于如何判断集合(词典)中是否含有字符串。如果用有序集合TreeMap)的话，复杂度是o(logn) ( n是词典大小);如果用散列表( Java的HashMap. Python的dict )的话，账面上的时间复杂度虽然下降了，但内存复杂度却上去了。有没有速度又快、内存又省的数据结构呢？这就是字典树。
-
什么是字典树
字符串集合常用宇典树(trie树、前缀树)存储，这是一种字符串上的树形数据结构。字典树中每条边都对应一个字， 从根节点往下的路径构成一个个字符串。字典树并不直接在节点上存储字符串， 而是将词语视作根节点到某节点之间的一条路径，并在终点节点(蓝色) 上做个标记“该节点对应词语的结尾”。字符串就是一 条路径，要查询一个单词，只需顺着这条路径从根节点往下走。如果能走到特殊标记的节点，则说明该字符串在集合中，否则说明不存在。一个典型的字典树如下图所示所示。
其中，蓝色标记着该节点是一个词的结尾，数字是人为的编号。按照路径我们可以得到如下表所示：
词语 路径 入门 0-1-2 自然 0-3-4 自然人 0-3-4-5 自然语言 0-3-4-6-7 自语 0-3-8 当词典大小为 n 时，虽然最坏情况下字典树的复杂度依然是O(logn) (假设子节点用对数复杂度的数据结构存储，所有词语都是单字)，但它的实际速度比二分查找快。这是因为随着路径的深入，前缀匹配是递进的过程，算法不必比较字符串的前缀。
-
字典树增删改
实现及其增删改查的操作见P47-49
2.5 基于字典树的其它算法
字典树的数据结构在以上的切分算法中已经很快了，但厉害的是作者通过自己的努力改进了基于字典树的算法，把分词速度推向了千万字每秒的级别，这里不一一详细介绍，详情见书，主要按照以下递进关系优化：
- 首字散列其余二分的字典树
- 双数组字典树
- AC自动机(多模式匹配)
- 基于双数组字典树的AC自动机
2.6 HanLP的词典分词实现
-
DoubleArrayTrieSegment
DoubleArrayTrieSegment分词器是对DAT最长匹配的封装，默认加载hanlp.properties中CoreDictionaryPath制定的词典。
输出：
-
去掉停用词
停用词词典文件：（data/dictionnary/stopwords.txt）
该词典收录了常见的中英文无意义词汇(不含敏感词)，每行一个词。
输出：