（二）词典分词

1.什么是词2.齐夫定律3.切分算法4.字典树首字散列其余二分的字典树前缀的妙用 双数组字典树AC自动机评测标准混淆矩阵准确率精确率（简称P，precision）召回率（recall）F1score中文分词当中的P,R,F1计算 未登录词OOV 与IV登录词字典树的其他应用停用词

1.什么是词

词语的定义是具备独立意义的最小单位 基于词典的中文分词中，词的定义是：词典中的字符串就是词，根据定义词典之外的字符串就不是词了。

2.齐夫定律

一个单词的词频与它的排名成反比，大致呈现1/x的曲线形状。

3.切分算法

代码基于hanlp

''' 完全切分 ''' def full_segement(text,dic): word_list=[] for i in range(len(text)): for j in range(i+1,len(text)+1): word=text[i:j] if word in dic: word_list.append(word) return word_list ''' 正向最长匹配 ''' def forward_segement(text,dic): word_list=[] i=0#开始于0 while i<len(text): # for i in range(len(text)):#这个写法不正确，因为下面的i+=不能改变这个i的值 long_word=text[i] for j in range(i+1,len(text)+1):#正逆向匹配的区别在这里，正向是从当前的位置匹配到最后 word=text[i:j] if word in dic: if len(word)>len(long_word): long_word=word word_list.append(long_word) i+=len(long_word) return word_list ''' 逆向最长匹配 ''' def backword_segement(text,dic): word_list=[] i=len(text)-1#开始与最后 while i>=0: long_word=text[i] for j in range(0,i):#正逆向匹配的区别在这里，正向是从当前的位置匹配到开头，逆着匹配 word=text[j:i+1]#注意python 当中的区间大部分是左闭右开的 if word in dic: if len(word)>len(long_word): long_word=word word_list.insert(0,long_word) i-=len(long_word) return word_list ''' 双向最长匹配 ''' def count_single_char(word_list:list): return sum(1 for word in word_list if len(word)==1) def bidirection_segment(text,dic): forward_dic=forward_segement(text,dic) backword_dic=backword_segement(text,dic) if len(forward_dic)>len(backword_dic): return backword_dic elif len(forward_dic)<len(backword_dic): return forward_dic else: if count_single_char(forward_dic)<count_single_char(backword_dic): return forward_dic else: return backword_dic ''' 字典树 ''' class Node(object): def __init__(self, value) -> None: self._children = {} self._value = value def _add_child(self, char, value, overwrite=False): child = self._children.get(char) if child is None: child = Node(value) self._children[char] = child elif overwrite: child._value = value return child class Trie(Node): def __init__(self)->None : super().__init__(None) def __contains__(self, key): return self[key] is not None def __getitem__(self, key): state=self for char in key: state=state._children.get(char) if state is None: return None return state._value def __setitem__(self, key, value): state=self # print("调用") for i,char, in enumerate(key): if i<len(key) -1: state=state._add_child(char,None,False) else: state = state._add_child(char,value,True) if __name__ == '__main__': dic = load_dictionary() # print(full_segement("商品和服务",dic)) # print(full_segement("就读北京大学",dic)) # print(forward_segement("就读北京大学",dic)) # print(backword_segement("研究生命起源",dic)) # print(bidirection_segment("项目的研究",dic)) # print(bidirection_segment("结婚的和尚未结婚的",dic)) trie=Trie() trie['自然'] = 'nature' trie['自然人'] = 'human' trie['自然语言'] = 'language' trie['自语'] = 'talk to oneself' trie['入门'] = 'introduction' trie['自然']=None assert '自然' not in trie trie['自然语言'] = 'human language' assert trie['自然语言'] == 'human language' assert trie['入门'] == 'introduction' '''

4.字典树

字符串集合常用字典树来存储，这种存储结构会大大降低存储空间的使用，而且在查询上效率高。我会使用通俗的解释来记录。 使用例子来讲解是最清楚的。 字典树相当于是一个有限状态自动机，下图中可以理解为从一个状态可以到达另一个状态或者从一个状态转换为另一个状态转换失败。 假设我们要将字典入门，自然，自然人（ren），自然语言，自语插入字典树当中。 设当前指针p的位置是0

开始的时候我们规定只有一个root结点，规定编号为0

我们要将‘入’插入树当中，让0结点其出边为“入”，从而转换为1状态，此时P指向1

3.接着我们插入’门’，此时P在1处，发现其没有标识为‘门’的出边，于是建立新结点2，并且标识边为‘门’，同时要将2结点标识为一个词语的终结点，指针P移到root。

4.再插入新词‘自然’，首先我们看P没有出边为‘自’的标识，所以创建新的结点3，并且标识出边为‘自’，P移动到3。

5.整体创建完成之后为

要注意的是每个词语结束之后的标记和指针的移动。 注意字典树的增删查改都是先去查 其实在汉语的分词当中还可以进一步改进字典树，hanlp使用的是Java中hashcode，同时使用UTF-16字符集，在Python当中使用的64位的散列值，返回64位整数，但是Unicode字符集总共才136690个小于2^64,这样如果将字进行散列的话内存距离会非常远，

hash('池’)-hash（’江‘）=2668313623312284569

而Java中为UTF-16编码，查看hashcode的源码发现其返回的是一个下转型数据return (int) value，所以返回的就是UTF-16的编码。

System.out.println(new Character('池')-new Character('江').hashCode())；//输出1

首字散列其余二分的字典树

这种字典树只是在根节点的下的第一层使用了散列函数进行散列，这样效率就会有所提升。 java代码实现字典树的增删改查

import java.util.*; public class dictionaryTree { public static void main(String[] args) { Trie dictree=new Trie(); dictree.insert("我是好人们说的"); dictree.insert("们喝酒"); dictree.insert("好东西"); System.out.println(dictree.search("人们")); System.out.println(dictree.search("们喝酒")); System.out.println(dictree.search("们喝")); dictree.change("们喝"); System.out.println(dictree.search("们喝")); dictree.deleted("们喝"); System.out.println(dictree.search("们喝")); } } class Trie{ Node root; public Trie(){ root=new Node(); root.isEnd=true; } public void insert(String word){ Node node=root; for (int i=0;i<word.length();i++){ Character c=new Character(word.charAt(i)); if(!node.children.containsKey(c)){ node.children.put(c,new Node()); } node=node.children.get(c); } node.isEnd=true; } public boolean search(String word){ Node node=root; for (int i=0;i<word.length();i++){ Character c = new Character(word.charAt(i)); if(!node.children.containsKey(c)){ return false; } node=node.children.get(c); } return node.isEnd; } public void change(String word){ Node node=root; for (int i=0;i<word.length();i++){ Character c = new Character(word.charAt(i)); if(!node.children.containsKey(c)){ System.out.println("不存在前缀，无法修改"); return; } node=node.children.get(c); node.isEnd=true; } } public void deleted(String word){ Node node=root; Stack<Node>st=new Stack<Node>(); for (int i=0;i<word.length();i++){ Character c = new Character(word.charAt(i)); if(!node.children.containsKey(c)){ System.out.println("不存在，无法删除"); return; } node=node.children.get(c); st.push(node); } if (!node.isEnd){ System.out.println("不存在，无法删除"); return; } if(node.children.size()>0) { node.isEnd = false; }else{ while (!st.isEmpty()){ Node p=st.pop(); p=null; } System.gc(); } } } class Node{ boolean isEnd=false; Map<Character,Node> children; public Node(){ children=new HashMap<Character, Node>(); isEnd=false; } }

前缀的妙用

在使用上，如果查询词语如’自然‘，'自然人’如果我们发现‘自然’这条路径不存在那么‘自然人’也不存在，加速了查询速度，因为他们使用的是共同的前缀。后面的AC自动机使用我们会看到多模式匹配当中前缀加后缀。

双数组字典树

上面的字典树当每个词为单个字且数据量非常大的时候的时候查询速度依然很慢为O(logn)n为词个数。现在双数组字典树可以实现将查询的时间复杂度减低到常数！双数组字典树由两个数组来维护base和check数组，他的工作是这样的当前状态b接受字符c转移到字符p的时候满足 $$\begin{gathered} p=base[b]+c \\ check[p]=base[b] \end{gathered}$$ 实现及其复杂，涉及到冲突解决，我也只是了解它是如何工作的，让我写还真费点功夫，具体可以参考https://blog.csdn.net/u013300579/article/details/78869742

AC自动机

AC自动机可以用来做多模式的匹配，AC自动机由3个表来维持：goto表，fail表，output表组成。使用AC自动机来进行查询可以快速匹配多个模式串，这点有点类似于KMP算法，不同的是KMP算法只匹配一个模式串，而AC自动机可以匹配多个模式串。它本质上还是一个前缀字典树，但不同的是它添加了fail指针，相当于KMP的next数组，这样当匹配失败的时候就知道从哪个最长后缀开始匹配了。下面我用图解的方式说明AC自动机。

我们有词语：a,ab,bc,bbc.建立一棵前缀树如图 goto表其实就是一棵前缀树

output表就是终结点的词语以及以终结点结尾的最长后缀 其中编号5就是包含了bbc和它的最长后缀bc

接着使用广度优先遍历（层次遍历）来建立fail表

首先我们初始化初始状态，由于初始状态即0号位置它的前一个状态是没有的因此它的由一个空转移到0号状态是不会失败的，因此它的fail指针空的。

由于AC自动机的fail指针永远指向比当前结点深度浅的，所以我们直接规定第一层的fail全部指向0号状态，也就是起始的状态，所以1和3的fail都指向了0号状态。

接着我们开始到达第三层，2号状态，要得到2号状态的fail指针，首先我我们要看它的父亲结点的fail指针，如果父亲结点的fail指针指向的结点(暂且叫它fafail)的儿子使得fafail的接受b之后的状态不为空，也就是fafail的出边为b。在此处我们看2号状态父亲为1号状态，所以它的fafail为0号状态，0号状态带有出边为b，所以2号状态的fail指针指向了3号状态。是不是有点乱，最后我会再次总结。

我们来看6号结点，它的fafail为0号状态，而它并没有出边为c的边，要想使得接受字符c之后进行状态转移部位空只能指向0号状态，这意味着没有相同的最长后缀要进行重新匹配。

其他状态按照层次的顺序依次类推，值得注意的是，fail指向的层次永远是小于当前节点的层次的。全部构造完成后

我们来总结一下建立fail表的程序，设父亲状态为a,儿子状态为b,从a到b要接受一个字符x，所有的第一层的fail指针指向初始状态，接着来看一般情况：要找到b的fail就要看父亲a的fail也就是上面的fafail，如果fafail有出边为x的指针那么就让b的fail指向fafail以x为出边的儿子。 上面的理解仅仅是我参考了好多资料后找出的，如果有什么错误，请留言，我会尽力去修改。 其实上面的AC自动机还可以与双数组字典树进行结合，那个相当麻烦。

评测标准

混淆矩阵

我们在了解下面的评测标准前首先了解下混淆矩阵 TP（true positive）：将正类预测为正类 FP(false positive)：将负类预测为正类 FN(false negative)：将正类预测为负类 TN(true negative)：将负类预测为负类 其实上面的简写我们看英文便一目了然

准确率

准确率accurate注意它不是AUC！ ！ 准确率指得是在所有的试验中正确的次数占总实验数的比重 $准确率=\frac{预测正确次数}{总的试验次数}$

缺点：当样本不均衡的时候就不行了，例如一个99负样本，1个正样本那么模型预测全部是负样本那么准确率看似很高，但我们忽略了仅有一个的负样本。

精确率（简称P，precision）

$$P=准确率=\frac{正确预测为正的样本}{正确预测为正的样本+错误预测为正的样本}=\frac{TP}{TP+FP}$$上面公式其实就是预测为正的样本数量中正确的个数占比。注意的一点就是我们将自己所关注的设置为正样本

召回率（recall）

$$R=召回率=\frac{正确预测为正的样本}{正确预测为正的样本+错误预测为负样本的数量}=\frac{TP}{TP+FN}$$ 上面的公式就是预测为正样本的数量占真正正样本总数量的比重。

F1score

$$F1=\frac{2\ast P\ast R}{P+R}$$ P为精确率，R为召回率，这样做其实是做了一个均衡。P,和R同时高F1才能高。精确率和召回率很难做到同时高，精确率高的系统召回率低，召回率高的系统精确率低。

中文分词当中的P,R,F1计算

上面的混淆矩阵是针对分类问题设定的，而在中文分词当中却是一个分块问题。我们需要将上面的做一下转换，将分块问题转化为分类问题。 对于长为n的字符串，分词结果是一系列单词。每一个单词按它在文本中的起止位置可基座区间[i,j]，其中1<=i<=j<=n,那么标准答案的所有区间构成一个集合A，作为正类。A集合之外的所有区间构成另一个集合A^c（补集）。同理记分词结果所有单词区间构成集合B那么： $$TP并FN=A$$ $$TP并FP=B$$ $$TP=A交B$$ $$P=\frac{TP}{B}$$ $$R=\frac{TP}{A}$$

未登录词OOV 与IV登录词

未登录词就是新词语，词典未收录的词语。如何准确切分OOV ,乃至识别其语义，是整个NLP领域的核心难题。IV 指的是登录词相应IV Recall Rate指的是词典中的词汇被正确召回的概率。如果词典词汇都无法百分之百召回，说明词典的消除歧义的能力不好。

字典树的其他应用

字典树除了可以用于中文分词之外，还可以用于停用词过滤，简繁转化，拼音转化任务。

停用词

汉语中有一类没有多少意义的词语，比如助词’的’，连词’以及’,副词’甚至’语气词’吧’等，一个句子去掉了停用词不影响理解。停用词也可以用做网站敏感词过滤。