Question

2.1 基于词库

2.1.1 词库组织

本人采用的是基于词表匹配的分词方法，因而词库是分词系统的基础。整个分词过程实际上就是在词词上的查找匹配过程，因而词库的组织相当重要。

对于词表存放在一个文本文件里，每一个词条由两项组成，一个是词的 ID（WordId）、另一个就是词本身。同时在词表上加上静态索引，本人对词表 进行分组管理并在上面添加三级索引。首先对词条按字数分组，字数相同的词条放在同一组里，并对词表按首汉字的内码从小到大排序。一级索引是加在各个分组 上，一级索引记录了各分组的开始位置，再根据下一分组的起始位置可以确定当前分组的终止位置。二级索引是加在一级索引内部的，在同一组内部由于有很多的词 条，二级索引是按词的首汉字内码建立的，它加在以不同汉字开头的词条组中，这样通过三级索引可以进一步缩小查找范围。另外在汉字中以有些字开头的词条过 多，这样进行匹配的次数过多，不利于提高匹配速度。因而在二级索引的基础之上添加一个三级索引，它是按照一定的密度间隔添加，我设定了一个默认的合理的值 就是每隔 50 个词条添加一个三级索引，同样三级索引也是根据汉字内码添加的（三级索引和二级索引的定义相同）。词条及索引的定义如下：

//根据汉字内码建立的索引结点（二级和三级索引）

   typedef struct CodeIndexNode{
    char KeyValue[17];
    int nIndex;
   }CodeIndex;

   //根据词语字数建立的一级索引结点
   typedef struct WordsIndexNode{
    int nKeyCount;
    int nKeyBeginIndex;
    int nKeyEndIndex;
    int CodeIndexCount;
    CArray<CodeIndexNode*,CodeIndexNode*>HexIndex;
   }WordsIndex;

   //关键字结点
   typedef struct KeyWordNode{
    CString strKeyWord; //关键字
    int       nID;          //关键字 ID
   };

词表及一级、二级、三级索引之间的关系如下图所示：

2.1.2 切分方法

由于采用的是基于词库匹配的正向最大匹配算法（通常简称为 MM 法），其基本思想为：设 D 为词典，MAX 表示 D 中的最大词长，str 为待切分的字串。 MM 法是每次从 str 中取长度为 MAX 的子串与 D 中的词进行匹配。若成功，则该子串为词，指针后移 MAX 个汉字后继续匹配，否则子串逐次减一进行匹配。所 以主要切词过程如下：(流程图如下图所示)

1）、读取词库，并读取相应的静态索引，建立词库上的索引；

2）、读取待切分的字串 str；

3）、从待切分字串 str 中取出一个长度为 MAX 的子串 sstr，到词典中去匹配，若匹配成功则取下一个长度为 MAX 的子串进行匹配，否则将子串 sstr 从后面截去一个字后继续匹配，直到匹配成功或者子串 sstr 中只有一个字为止。若匹配成功则从匹配成功的词的位置开始再截取下一长度为 MAX 的子 串 sstr 进行匹配，依次循环直到将 str 串匹配完为止。

4）匹配过程：首先根据子串 sstr 的长度（这里指的是字数）确定一级索引也就是确定分组，这个过程可以二分查找法，也可以采用 Hash 函数直接定 位，但是由于分组数很少（不会超过 20）因而两种方法没有多大的区别。在确定了分组后再根据首汉字的内码确定二级索引，因为二级索引是按内码从小到大的顺 序因而可采用拆半查找方法，找到以后再确定三级索引，这样将进行匹配的过程缩小到一个很小的范围，在这个范围内匹配不成功则进行下一个串的匹配。通过确定 三级索引确定了进行匹配的最小词条集。

2.1.3 切分结果的保存

切分结果也就是顺排档数据的保存。

由于数据量很大，不能全存放在内存中，所以每处理完一文档就将其切分结果存放到外部文件中，这里可以借助其它关系型数据库，这有利于于索引器导出数据将其导成倒排档索引文件。主要用到的结构体定义如下：

//Hit 结点
typedef struct HitNode{
    int   nPos;//位置
    HitNode* pNext;//下一 hit 指针
};

//文档列表结点
typedef struct DocListNode{
    _int64  nDocID;//DOC ID
    int    nHits;//词出现的次数
    float   fWeight;//词在文中的要重
    HitNode* pHitHead;//Hit 链表头指针
    DocListNode* pNext;
};

//一级索引结点
typedef struct LexIconNode{
    int             nKeyWordID;//关键字 ID
    int             nDocs;//文档数
    DocListNode* pDocListHead;//文档链表头指针
    LexIconNode* pNext;
};

在数据库中存放的字段主要有：DocID、WordID、Hit（位置）、Weight（权值）。这样索引器导出时将会按 WordID 和权值进行排序。

2.1.4 经验总结

1、 存在的问题

1）、在词库组织方面采用静态的索引不利于于词库的变化，若有一新词出现，则需要重建整个词库的索引，因为下标都发生了变量。这不利于词库的扩充。

2）、词的 ID 分配机制也有些不足，这里的 ID 都是跟词的内码相关，也就是跟词在词库中的排序顺序有关，这样若有新词添加进来后，就会改变其后面所有词的 ID。

3）、切词的速度不够快，虽然每秒能达到 400 多字，但是词库比较小，只有 5 万多的词条。若司库很大时速度会有所下降。

4）、因为汉字是双字节表示的，所以在切分之前转换成 Unicode，转换成多字节表示，经过测试发现，多字节转换占用了很大一块 CPU 时间，将近占去了 40%的时间。

5）、在进行多字节转换时开设的缓冲区为 1000 个汉字，若需要转换的汉字多于 1000 则会出错，但若开设的缓冲区过大是对系统资源的浪费。

6）、是一种机械的切词方法，没有对歧义词进行排除和分析。

7）、没有新词的识别功能，也就是不通过词典不能识别切分出新的词。

2、 改进的方向

1）、词表组织

在词表上添加三级索引是一个较好的方法，但是采用静态的索引不利于词库的扩充，因而词库的索引可动态生成，在读取词库的同时构建索引，但是这种方法 对于查询器会产生一个不利影响，因为查询器也需要读取词库而构建索引的过程比较费时间，这样用户查询时会有一定的延时，所以应根据需要采用一种折衷的办 法。

整个切词过程实际就是在词表上的查找过程，而词表相当于就是一个查找表，所以这个查找表的组织相当关键，它决定切分的速度。所以在这个查找表上必须 添加索引来加快速度，本人觉得可以根据各词的前两个汉字的内码建立一个 Hash 函数索引，这样即不需要分组也不需要用二分法来查找，直接定位肯定会减少进 行匹配的次数。但需要解决冲突问题，因为有的词属于其他词的前向子串。

2）、词条 ID 分配

​ 词条 ID(WordId) 可按入库的先后顺序递增，不管其内码。但是入库后应该按其内码插入到适当的位置。但是在建立倒排档索引数据时应该按 WordID 从小到大排序，这样对于查询器可以根据 WordID 用 Hash 函数直接定位到相应的读取位置。

3）、多字节转换问题

​ 多字节转换需要将所有的待切分串都转换成多字节表示，这个过程相当费时，若不需要转换直接切分则会大大提高速度，对于纯汉字的字串可以这样做，但是有中英 文混合的字符串就不太适合，因为英文字符只占一个字节表示，这样会出现将一个当字从中间切开。这样字符串移位时先判断其是否是 Ansi 码，若是则移一个字 节，若不是则移两个字节。

4）、歧义识别

5）、新词识别

​ 新词的识别，可以按词频统计的方法，若某一字串出现的次数高于某一频率时可以认为一个词，将其切分出来。

2.2 机器学习

2.2.1 简介

• 判别式模型：通过判别函数产生预测模型进行预测。
• 产生式模型：通过概率密度模型形成产生式模型进行预测。

表格 5 判别式和产生式模型比较

模型	优点	缺点
判别式模型	数据信息相对丰富，研究单类别问题灵活性较强。 能够充分利用先验数据。 模型可以通过增量学习的方式获得。	学习过程相对复杂。 在目标分类的问题中容易产生较大的错误率。
产生式模型	分类边界比较灵活，适用于多类别问题研究。 能够较好地分辨出类别之间的差异特征。	不能反映训练样本的本身特性。 描述信息具有一定局限性。

备注：产生式模型可以通过贝叶斯公式转换为判别式模型，反之则不行。

2.2.2 CRF 条件随机场

条件随机场的分词步骤：

• 准备语料库。
• 初步语料库特征学习。序列标注状态~BMES
• 词语特征学习。
• 分词。

2.3 Jieba 分词（Python）

简介

依赖包 ： pip install jieba

主要功能 ：分词、自定义词典、词性标注、关键词抽取、并行分词（类 Unix）

特色 ： 支持繁体分词、MIT 授权协议

支持三种分词模式：

• 精确模式，试图将句子最精确地切开，适合文本分析；
• 全模式，把句子中所有的可以成词的词语都扫描出来，速度非常快，但是不能解决歧义；
• 搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。

在线演示 http://jiebademo.ap01.aws.af.cm/

网站代码 ： https://github.com/fxsjy/jiebademo

算法 ： Bigram + HMM

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

示例

表格 Jieba 主要功能和函数

功能	函数	参数	功能
1 分词	cut(self, sentence, cut_all=False, HMM=True)/lcut	sentence 需要分词的字符串；cut_all 参数用来控制是否采用全模式；HMM 参数用来控制是否使用 HMM 模型	切词。cut, lcut 是 Tokenizer 类的方法。cut 返回 Tokenizer.cut 生成器，lcut 返回列表
	cut_for_search/lcut_for_search	二个参数：需要分词的字符串；是否使用 HMM 模型。	该方法适合用于搜索引擎构建倒排索引的分词，粒度比较细
	Tokenizer(dictionary=DEFAULT_DICT)	jieba.dt 为默认分词器，所有全局分词相关函数都是该分词器的映射。	新建自定义分词器，可用于同时使用不同词典。
2 自定义词典	load_userdict(file_name)	file_name 为文件类对象或自定义词典的路径。 file_name 若为路径或二进制方式打开的文件，则文件必须为 UTF-8 编码。	词典格式和 dict.txt 一样，一个词占一行；每一行分三部分：词语、词频（可省略）、词性（可省略），用空格隔开，顺序不可颠倒。词频省略时使用自动计算的能保证分出该词的词频。
	add_word(word, freq=None, tag=N)		添加新词到词典
	del_word(word)		删除词典的词语
	suggest_freq(self, segment, tune=False)		可调节单个词语的词频，使其能（或不能）被分出来。自动计算的词频在使用 HMM 新词发现功能时可能无效。
3 词性标注	import jieba.posseg as pseg pseg.cut(sentence, HMM=True)		word, flag 示例：李小福 / nr , 是 / v， 创新办 / i , 主任 / b ,
4 关键词抽取	import jieba.analysejieba.analyse.extract_tags(sentence, topK=20, withWeight=False, allowPOS=())		基于 TF-IDF 算法的关键词抽取
	jieba.analyse.textrank(content, topK=topK)		基于 TextRank 算法 的关键词抽取
5Tokenize 返回词语位置

备注：1. 分词： cut 返回可迭代类型 generator，lcut 返回列表。

2. 自定义词典：自定义调节词典解决歧义分词问题。

3. 更改分词器（默认为 jieba.dt ）的 tmp_dir 和 cache_file 属性，可分别指定缓存文件所在的文件夹及其文件名，用于受限的文件系统。

4. 并行分词：原理：将目标文本按行分隔后，把各行文本分配到多个 Python 进程并行分词，然后归并结果，从而获得分词速度的可观提升。基于 python 自带的 multiprocessing 模块，目前暂不支持 Windows。

   # 例子：https://github.com/fxsjy/jieba/blob/master/test/parallel/test_file.py
   jieba.enable_parallel(4) # 开启并行分词模式，参数为并行进程数
   jieba.disable_parallel() # 关闭并行分词模式
   

5. 延迟加载机制： import jieba 和 jieba.Tokenizer() 不会立即触发词典的加载，一旦有必要才开始加载词典构建前缀字典。如果你想手工初始 jieba，也可以手动初始化 jieba.initialize() 。

类 C 函数 （2 个分词器： POSTokenizer， Tokenizer-缺省）

# default Tokenizer instance
dt = Tokenizer()

# global functions
get_FREQ = lambda k, d=None: dt.FREQ.get(k, d)
add_word = dt.add_word
calc = dt.calc
cut = dt.cut   # def cut(self, sentence, cut_all=False, HMM=True):
lcut = dt.lcut
cut_for_search = dt.cut_for_search
lcut_for_search = dt.lcut_for_search
del_word = dt.del_word
get_DAG = dt.get_DAG
get_dict_file = dt.get_dict_file
initialize = dt.initialize
load_userdict = dt.load_userdict
set_dictionary = dt.set_dictionary    # 设置主词典路径
suggest_freq = dt.suggest_freq
tokenize = dt.tokenize # def tokenize(self, unicode_sentence, mode="default", HMM=True):
user_word_tag_tab = dt.user_word_tag_tab

示例 1：分词 （三种分词模式：精确、全、搜索引擎）

import jieba
# 全模式
text = "我来到北京清华大学"
seg_list = jieba.cut(text, cut_all=True)
print(u"[全模式]: ", "/ ".join(seg_list))

# 精确模式
seg_list = jieba.cut(text, cut_all=False)
print(u"[精确模式]: ", "/ ".join(seg_list))

# 默认是精确模式
seg_list = jieba.cut(text)
print(u"[默认模式]: ", "/ ".join(seg_list))

# 搜索引擎模式
seg_list = jieba.cut_for_search(text)
print(u"[搜索引擎模式]: ", "/ ".join(seg_list))

### 运行结果
Building prefix dict from the default dictionary ...
Dumping model to file cache C:\Users\keefe\AppData\Local\Temp\jieba.cache
Loading model cost 1.436 seconds.
Prefix dict has been built succesfully.
[全模式]: 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学
[精确模式]: 我/ 来到/ 北京/ 清华大学
[默认模式]: 我/ 来到/ 北京/ 清华大学
[搜索引擎模式]: 我/ 来到/ 北京/ 清华/ 华大/ 大学/ 清华大学

示例 2：自定义词典

dict.txt 格式为：词语 词频（可选） 词性（可选）

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

实现

>>> 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)))
「/台中/」/正确/应该/不会/被/切开

示例 3： 词性标注

import jieba.posseg as pseg
test_sent = ("李小福是创新办主任也是云计算方面的专家")
result = pseg.cut(test_sent)    # 词性标注
for w in result:
    print(w.word, "/", w.flag, ", ", end=' ')


# 运行结果
李小福 / nr ,  是 / v ,  创新 / v ,  办 / v ,  主任 / b ,  也 / d ,  是 / v ,  云 / n ,  计算 / v ,  方面 / n ,  的 / uj ,  专家 / n ,  

示例 4：抽取关键词

import jieba.analyse

# 法 1：TF-IDF
jieba.set_stop_words(file_name)  # 可以直接这样填写
jieba.analyse.set_idf_path(file_name)
jieba.analyse.extract_tags(sentence)

# 法 2：TextRank
s = "此外，公司拟对全资子公司吉林欧亚置业有限公司增资 4.3 亿元，增资后，吉林欧亚置业注册资本由 7000 万元增加到 5 亿元。吉林欧亚置业主要经营范围为房地产开发及百货零售等业务。目前在建吉林欧亚城市商业综合体项目。2013 年，实现营业收入 0 万元，实现净利润-139.13 万元。"
for t, w in jieba.analyse.textrank(s, withWeight=True):
    print('%s, %s'% (t, w))

# 或者这样写
tr = jieba.analyse.TextRank()
for t, w in tr.textrank(s, withWeight=True):
    print('%s, %s'% (t, w))

示例 5：Tokenize：返回词语在原文的起止位置

import jieba
# 默认模式
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]))
print('\n')    
# 搜索模式
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:10

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

本章参考

python jieba 分词（结巴分词)、提取词，加载词，修改词频，定义词库 https://cloud.tencent.com/developer/article/1065715