笔记转载于GitHub项目:https://github.com/NLP-LOVE/Introduction-NLP
互联网词库(SogouW, 15万个词条)、清华大学开放中文词库(THUOCL)、HanLP词库(千万级词条)
这里以HanLP附带的迷你核心词典为例(本项目路径):data/dictionnary/CoreNatureDictionary.mini.txt
上升 v 98 vn 18
上升期 n 1
上升股 n 1
上午 t 147
上半叶 t 3
上半场 n 2
上半夜 t 1
HanLP中的词典格式是一种以空格分隔的表格形式,第一列是单词本身,之后每两列分别表示词性与相应的词频。
首先,加载词典:
def load_dictionary():
dic = set()
# 按行读取字典文件,每行第一个空格之前的字符串提取出来。
for line in open("CoreNatureDictionary.mini.txt","r"):
dic.add(line[0:line.find(' ')])
return dic
def count_single_char(word_list: list): # 统计单字成词的个数 return sum(1 for word in word_list if len(word) == 1) def bidirectional_segment(text, dic): f = forward_segment(text, dic) b = backward_segment(text, dic) if len(f) < len(b): # 词数更少优先级更高 return f elif len(f) > len(b): return b else: if count_single_char(f) < count_single_char(b): # 单字更少优先级更高 return f else: return b # 都相等时逆向匹配优先级更高 print(bidirectional_segment('研究生命起源', dic)) print(bidirectional_segment('项目的研究', dic)) 输出: ['研究', '生命', '起源'] ['项', '目的', '研究']
通过以上几种切分算法,我们可以做一个对比:
上图显示,双向最长匹配的确在2、3、5这3种情况下选择出了最好的结果,但在4号句子上选择了错误的结果,使得最终正确率 3/6 反而小于逆向最长匹配的 4/6 , 由此,规则系统的脆弱可见一斑。规则集的维护有时是拆东墙补西墙,有时是帮倒忙。
匹配算法的瓶颈之一在于如何判断集合(词典)中是否含有字符串。如果用有序集合TreeMap)的话,复杂度是o(logn) ( n是词典大小);如果用散列表( Java的HashMap. Python的dict )的话,账面上的时间复杂度虽然下降了,但内存复杂度却上去了。有没有速度又快、内存又省的数据结构呢?这就是字典树。
其中,蓝色标记着该节点是一个词的结尾,数字是人为的编号。按照路径我们可以得到如下表所示: 词语 路径 入门 0-1-2 自然 0-3-4 自然人 0-3-4-5 自然语言 0-3-4-6-7 自语 0-3-8 当词典大小为 n 时,虽然最坏情况下字典树的复杂度依然是O(logn) (假设子节点用对数复杂度的数据结构存储,所有词语都是单字),但它的实际速度比二分查找快。这是因为随着路径的深入,前缀匹配是递进的过程,算法不必比较字符串的前缀。
字典树的数据结构在以上的切分算法中已经很快了,但厉害的是作者通过自己的努力改进了基于字典树的算法,把分词速度推向了千万字每秒的级别,这里不一一详细介绍,详情见书,主要按照以下递进关系优化:
HanLP何晗–《自然语言处理入门》笔记:
https://github.com/NLP-LOVE/Introduction-NLP
项目持续更新中…
目录
章节 |
---|
第 1 章:新手上路 |
第 2 章:词典分词 |
第 3 章:二元语法与中文分词 |
第 4 章:隐马尔可夫模型与序列标注 |
第 5 章:感知机分类与序列标注 |
第 6 章:条件随机场与序列标注 |
第 7 章:词性标注 |
第 8 章:命名实体识别 |
第 9 章:信息抽取 |
第 10 章:文本聚类 |
第 11 章:文本分类 |
第 12 章:依存句法分析 |
第 13 章:深度学习与自然语言处理 |