本文摘要· 理论来源：【统计自然语言处理】第七章 自动分词
· 参考文章：https://www.cnblogs.com/Finley/p/6619187.html
· 代码目的：手写N-最短路径法进行中文分词
作者：CSDN 征途黯然.
本代码评分
1、训练集、测试集使用The Second International Chinese Word Segmentation比赛中的PKU的数据集。数据集地址：http://sighan.cs.uchicago.edu/bakeoff2005/。
2、本代码只是简单实现了N最短路径分词，消歧、未登录词暂未解决，评分如下：
精确率 0.7764031562984604 召回率 0.8847287850978248
3、当初比赛部分评分结果如下：
N最短路径分词
N最短路径算法是一种基于词典的分词算法. 每个句子将生成一个有向无环图, 每个字作为图的一个定点, 边代表可能的分词.
在上图中, 边的起点为词的第一个字, 边的终点为词尾的下一个字. 边1表示"我"字单字成词, 边2表示"只是"可以作为一个单词.
每个边拥有一个权值, 表示该词出现的概率. 最简单的做法是采用词频作为权值, 也可以采用TF-IDF值作为权值提高对低频词的分词准确度.
N最短路径分词即在上述有向无环图中寻找N条权值和最大的路径, 路径上的边标志了最可能的分词结果.通常我们只寻找权值和最大的那一条路径.
根据上图的权值最大路径得到的分词结果为: "我/只是/做/了/一些/微小/的/工作"
实现词典
词典将根据输入的文本, 统计各单词的词频:
import json import pickle # ############## # main--词典 # 用来读取utf8格式文章库、json格式词典库、停用词； # 可以转存为json形式的txt词典库； # 初始化时默认调用load函数，读取dataset/unknown/words.txt # ############## class WordDictModel: def __init__(self): self.word_dict = {} self.data = None self.stop_words = {} self.load() # 读取词库数据，词库为空格分隔的文章等。文件后缀应当为.utf8 def load_data(self, filename): self.data = open(filename, "r", encoding="utf-8") # 更新新词库数据，把读取的词库转化成内部字典word_dict def update(self): # build word_dict for line in self.data: words = line.split(" ") for word in words: if word in self.stop_words: continue if self.word_dict.get(word): self.word_dict[word] += 1 else: self.word_dict[word] = 1 # 把内部词典里面的数据，转化成txt本文文档，格式为key-value键值对，相对于压缩 def save(self, filename="words.txt", code="txt"): fw = open(filename, 'w', encoding="utf-8") data = { "word_dict": self.word_dict } # encode and write if code == "json": txt = json.dumps(data) fw.write(txt) elif code == "pickle": pickle.dump(data, fw) if code == 'txt': for key in self.word_dict: tmp = "%s %d\n" % (key, self.word_dict[key]) fw.write(tmp) fw.close() # 加载初始词库，是用save()方法保存的key-value形式的词库 def load(self, filename="dataset/unknown/words.txt", code="txt"): fr = open(filename, 'r', encoding='utf-8') # load model model = {} if code == "json": model = json.loads(fr.read()) elif code == "pickle": model = pickle.load(fr) elif code == 'txt': word_dict = {} for line in fr: tmp = line.split(" ") if len(tmp) < 2: continue word_dict[tmp[0]] = int(tmp[1]) model = {"word_dict": word_dict} fr.close() # update word dict word_dict = model["word_dict"] for key in word_dict: if self.word_dict.get(key): self.word_dict[key] += word_dict[key] else: self.word_dict[key] = word_dict[key]
update函数可以在原有词典的基础上, 根据新的输入更新词频.
原始文本输入:
... 罗辑 离开 墓碑 ， 站 到 他 为 自己 挖掘 的 墓穴 旁 ， 将 手枪 顶到 自己 的 心脏 位置 ， 说 ： “ 现在 ， 我 将 让 自己 的 心脏 停止 跳动 ， 与此同时 我 也 将 成为 两个 世界 有史以来 最大 的 罪犯 。 对于 所 犯下 的 罪行 ， 我 对 两个 文明 表示 深深 的 歉意 ， 但 不会 忏悔 ， 因为 这是 唯一 的 选择 。 我 知道 智子 就 在 身边 ， 但 你们 对 人类 的 呼唤 从不 理睬 ， 无言 是 最大 的 轻蔑 ， 我们 忍受 这种 轻蔑 已经 两个 世纪 了 ， 现在 ， 如果 你们 愿意 ， 可以 继续 保持 沉默 ， 我 只 给 你们 三十 秒钟 时间 ...
产生词频词典:
{ ... "伏击战": 26, "生态园林": 3, "造谣诽谤": 3, "下关市": 11, "水彩颜料": 3, "虎踞龙盘": 5, ... }
最短路径分词
分词器需要继承WordDictModel, 并利用其词典. 遍历输入语句中所有子串, 并查询其词频构造有向无环图:
class DAGSegger(WordDictModel): # 构建有向无环图 def build_dag(self, sentence): dag = {} for start in range(len(sentence)): unique = [start + 1] tmp = [(start + 1, 1)] for stop in range(start+1, len(sentence)+1): fragment = sentence[start:stop] # use tf_idf? num = self.word_dict.get(fragment, 0) if num > 0 and (stop not in unique): tmp.append((stop, num)) unique.append(stop) dag[start] = tmp return dag
产生的dag格式:
{ 0: [(1,1)], 1: [(2,1), (3,738)], 2: [(3,1)], 3: [(4,1)], 4: [(5,1)], 5: [(6,1), (7,2309)], 6: [(7,1)], 7: [(8,1), (9,304)], 8: [(9,1)], 9: [(10,1)], 10: [(11,1), (12,2605)], 11: [(12,1)], }
字典中的值代表其键的后继顶点, 如1: [(2,1), (3,738)]表示顶点1到顶点2的权值为1, 到顶点3的权值为738
最短路径最好使用Floyd或Dijsktra算法. 但其耗时太久, 大多数情况下使用贪心算法求得次优解就可以达到所需精度:
# 从N个路径中，挑选出最优路径 def predict(self, sentence): Len = len(sentence) route = [0] * Len dag = self.build_dag(sentence) # {i: (stop, num)} for i in range(0, Len): route[i] = max(dag[i], key=lambda x: x[1])[0] return route
词典法分词本身就是一种不精确的方法, 最短路径的最优解和次优解在分词效果上相差并不大.
但是, 求得最优解需要将时间复杂度由O(n2)提高到O(n3). 考虑常见句子的长度, 造成的性能损失难以接受.
最后, 做一下测试:
# 测试 def test(self): cases = [ "小朋友，你是否有很多烦恼", "别人在嘻嘻哈哈，你却在研究中文分词", "我是周杰伦，我为自己歌唱", "我只是做了一些微小的工作", "中秋节我在看统计自然语言处理,我特别开心" ] for case in cases: result = self.cut(case) # for word in result: # print(word) print('/'.join(result))
测试结果:
小朋友/，/你/是否/有/很多/烦恼 别人/在/嘻嘻哈哈/，/你/却/在/研究/中文/分词 我/是/周杰伦/，/我/为/自己/歌唱 我/只是/做/了/一些/微小/的/工作 中秋节/我/在/看/统计/自然/语言/处理/,/我/特别/开心
