自己架设网站服务器,大学生网站设计大作业,中国建设银行网址是什么,刚做的网站怎么才能搜到我查词典和字标注 目前中文分词主要有两种思路#xff1a;查词典和字标注。 首先#xff0c;查词典的方法有#xff1a;机械的最大匹配法、最少词数法#xff0c;以及基于有向无环图的最大概率组合#xff0c;还有基于语言模型的最大概率组合#xff0c;等等。 查词典的方法…查词典和字标注 目前中文分词主要有两种思路查词典和字标注。 首先查词典的方法有机械的最大匹配法、最少词数法以及基于有向无环图的最大概率组合还有基于语言模型的最大概率组合等等。 查词典的方法简单高效得益于动态规划的思想尤其是结合了语言模型的最大概率法能够很好地解决歧义问题但对于中文分词一大难度——未登录词中文分词有两大难度歧义和未登录词则无法解决为此人们也提出了基于字标注[BIOS, BME]的思路所谓字标注就是通过几个标记比如4标注的是single单字成词begin多字词的开头middle三字以上词语的中间部分end多字词的结尾把句子的正确分词法表示出来。这是一个序列输入句子到序列标记序列的过程能够较好地解决未登录词的问题但速度较慢而且对于已经有了完备词典的场景下字标注的分词效果可能也不如查词典方法。 总之各有优缺点似乎是废话实际使用可能会结合两者像结巴分词用的是有向无环图的最大概率组合而对于连续的单字则使用字标注的HMM模型来识别。 1 中文分词
1.1 查词典优化之AC自动机
1.1.1 AC 自动机 本文首先要实现的是查词典方法的分词。1、给定一批词查找给定句子中是不是含有这个词2、如果有的话怎么解决歧义性问题。 第一步在计算机中称为“多模式匹配”。 这步看上去简单但事实上要高效地实现并不容易。 一个完备的词典少说也有十几万词语如果一个个枚举查找那计算量是吃不消的事实上我们在查字典的时候会首先看首字母然后只在首字母相同的那一块找然后又比较下一个字母依此下去。 这需要两个条件 1、一个做好特殊排序的词典我们有所谓的前缀树trie 2、有效的查找技巧我们有一些经典的算法比如AC自动机Aho and Corasick。 对于AC自动机就是一个使用了trie数据结构的高效多模式匹配算法。 我们也不用亲自实现它因为Python已经有对应的库了pyahocorasick。 因此我们只需要关心怎么使用它就行了。 官方的教程已经很详细地介绍了pyahocorasick的基本使用方法了这里也不赘述。遗憾的是虽然pyahocorasick已经同时支持python2和python3了但是在python2中它只支持bytes字符串不支持unicode字符串而在python3中则默认使用unicode编码这对我们写程度会带来一点困惑当然不是本质性的。 pyahocorasick构建AC自动机有一个很人性化的地方它能够以“键-注释”这样成对的形式添加词汇请留意dic.add_word(i, (i, log(j/total)))这一句这样我们可以在注释这里添加我们想要的信息比如频数、词性等然后在查找的时候会一并返回。有了上述AC自动机我们就能很方便地构建一个全模式分词也就是把词典中有的词都扫描出来其实这本来就是AC自动机的本职工作。 构建一个基于AC自动机的分词系统首先需要有一个文本词典假设词典有两列每一行是词和对应的频数用空格分开。那么就可以构建一个AC自动机。 1.1.3 最大匹配法 最大匹配法是指从左到右逐渐匹配词库中的词语匹配到最长的词语为止。 上面说的最大匹配法准确来说是“正向最大匹配法”类似地还有“逆向最大匹配法”顾名思义是从右到左扫描句子进行最大匹配效果一般比正向最大匹配要好些。如果用AC自动机来实现唯一的办法就是对词典所有的词都反序存储然后对输入的句子也反序然后进行正向最大匹配了。 def max_match_cut(sentence):sentence sentence.decode(utf-8)words []for i in sentence:i i.encode(utf-8)if dic.match(words[-1] i):words[-1] ielse:words.append(i)return words1.1.4 最大概率组合
基于最大概率组合的方法是目前兼顾了速度和准确率的比较优秀的方法。它说的是对于一个句子如果切分为词语w1,w2,…,wn是最优的切分方案那么应该使得下述概率最大P(w1,w2,…,wn)
直接估计这概率是不容易的一般用一些近似方案比如 P(w1,w2,…,wn)≈P(w1)P(w2|w1)P(w3|w2)…P(wn|wn−1) 这里P(wk|wk−1)就称为语言模型它已经初步地考虑了语义了。当然普通分词工具是很难估计P(wk|wk−1)的一般采用更加简单的近似方案。P(w1,w2,…,wn)≈P(w1)P(w2)P(w3)…P(wn) 放到图论来看这就是有向无环图里边的最大概率路径了。
def max_proba_cut(sentence):paths {0:([], 0)}end 0for i,j in dic.iter(sentence):start,end 1i-len(j[0]), i1if start not in paths:last max([i for i in paths if i start])paths[start] (paths[last][0][sentence[last:start]], paths[last][1]-10)proba paths[start][1]j[1]if end not in paths or proba paths[end][1]:paths[end] (paths[start][0][j[0]], proba)if end len(sentence):return paths[end][0] [sentence[end:]]else:return paths[end][0]
def min_words_cut(sentence):paths {0:([], 0)}end 0for i,j in dic.iter(sentence):start,end 1i-len(j[0]), i1if start not in paths:last max([i for i in paths if i start])paths[start] (paths[last][0][sentence[last:start]], paths[last][1]1)num paths[start][1]1if end not in paths or num paths[end][1]:paths[end] (paths[start][0][j[0]], num)if end len(sentence):return paths[end][0] [sentence[end:]]else:return paths[end][0]1.2 字标注
1.2.1 HMM 对于字标注的分词方法来说输入就是n个字输出就是n个标签。我们用λλ1λ2…λn表示输入的句子oo1o2…on表示输出。 那什么是最优的输出呢从概率的角度来看我们当然希望下面的条件概率最大 maxP(o|λ)maxP(o1o2…on|λ1λ2…λn) 换句话说o有很多可能性而最优的o应该是最大概率的o。 要注意P(o|λ)是关于2n个变量的条件概率而且n还是不定的。这种情况下我们几乎不可能对P(o|λ)进行精确的建模。即便如此我们可以稍微做些简化比如如果我们假设每个字的输出仅仅与当前字有关那么我们就有P(o1o2…on|λ1λ2…λn)P(o1|λ1)P(o2|λ2)…P(on|λn) 而估计P(ok|λk)就容易多了。这时候问题也得到很大简化因为要使得P(o|λ)最大只需要每个P(ok|λk)最大就行。我们所做的假设就称为独立性假设。 以上简化是一种方案但是完全没有考虑到上下文而且会出现不合理的情况比如按照我们的4标注那么b后面只能接m或e但是按照这种最大的方法我们可能得到诸如bbb的输出这是不合理的。于是我们就反过来提出了一种隐含的模型隐马尔可夫模型就如同数学中的函数与反函数一般反过来思考。 由贝叶斯公式我们得到P(o|λ)P(o,λ)P(λ)P(λ|o)P(o)P(λ) 由于λ是给定的输入那么P(λ)就是常数可以忽略。那么最大化P(o|λ)就等价于最大化P(λ|o)P(o) 现在我们可以对P(λ|o)作独立性假设得到P(λ|o)P(λ1|o1)P(λ2|o2)…P(λn|on) 同时对P(o)有P(o)P(o1)P(o2|o1)P(o3|o1,o2)…P(on|o1,o2,…,on−1) 这时候可以作一个马尔可夫假设每个输出仅仅于上一个输出有关那么 P(o)P(o1)P(o2|o1)P(o3|o2)…P(on|on−1)∼P(o2|o1)P(o3|o2)…P(on|on−1) 这时候P(λ|o)P(o)∼P(λ1|o1)P(o2|o1)P(λ2|o2)P(o3|o2)…P(on|on−1)P(λn|on) 我们称P(λk|ok)为发射概率P(ok|ok−1)为转移概率。这时候可以通过设置某些P(ok|ok−1)0 来排除诸如bb、bs这些不合理的组合。 可以看到HMM对问题作了大量的简化简化到不可能十分精确因此HMM模型一般都是用来解决“在查词典方法的过程中不能解决的部分”就好比结巴分词所做的。当然你可以把马尔可夫假设加强——比如假设每个状态跟前面两个状态有关那样肯定会得到更精确的模型但是模型的参数就更难估计了。 怎么训练一个HMM分词模型主要就是P(λk|ok)和P(ok|ok−1)这两部分概率的估计了。如果有一批标注语料那么估计这两个概率应该不难但是如果没有呢有一个词典也凑合。我们可以将一个带有频数的词典转化为一个HMM模型 代码的第一部分就是用一个字典来表示P(λk|ok)P(λk|ok)的计算是通过词典来获取的比如将词典中所有的一字词都计入s标签下把多字词的首字都计入b标签下等等。计算过程中还使用了对数概率防止溢出 第二部分的转移概率直接根据直觉估算的 第三部分就是通过viterbi算法动态规划求的最大概率路径了。对于概率估算简单采用了加1平滑法没出现的单字都算1次。 from collections import Counter
from math import loghmm_model {i:Counter() for i in sbme}with open(dict.txt) as f:for line in f:lines line.decode(utf-8).split( )if len(lines[0]) 1:hmm_model[s][lines[0]] int(lines[1])else:hmm_model[b][lines[0][0]] int(lines[1])hmm_model[e][lines[0][-1]] int(lines[1])for m in lines[0][1:-1]:hmm_model[m][m] int(lines[1])log_total {i:log(sum(hmm_model[i].values())) for i in sbme}trans {ss:0.3,sb:0.7,bm:0.3,be:0.7, mm:0.3,me:0.7,es:0.3,eb:0.7}trans {i:log(j) for i,j in trans.iteritems()}def viterbi(nodes):paths nodes[0]for l in range(1, len(nodes)):paths_ pathspaths {}for i in nodes[l]:nows {}for j in paths_:if j[-1]i in trans:nows[ji] paths_[j]nodes[l][i]trans[j[-1]i]k nows.values().index(max(nows.values()))paths[nows.keys()[k]] nows.values()[k]return paths.keys()[paths.values().index(max(paths.values()))]def hmm_cut(s):nodes [{i:log(j[t]1)-log_total[i] for i,j in hmm_model.iteritems()} for t in s]tags viterbi(nodes)words [s[0]]for i in range(1, len(s)):if tags[i] in [b, s]:words.append(s[i])else:words[-1] s[i]return words字标注法有效有两个主要的原因 第一个原因是它将分词问题变成了一个序列标注问题而且这个标注是对齐的也就是输入的字跟输出的标签是一一对应的这在序列标注中是一个比较成熟的问题 第二个原因是这个标注法实际上已经是一个总结语义规律的过程以4tag标注为为例我们知道“李”字是常用的姓氏一半作为多字词人名的首字即标记为b而“想”由于“理想”之类的词语也有比较高的比例标记为e这样一来要是“李想”两字放在一起时即便原来词表没有“李想”一词我们也能正确输出be也就是识别出“李想”为一个词也正是因为这个原因即便是常被视为最不精确的HMM模型也能起到不错的效果。 关于标注还有一个值得讨论的内容就是标注的数目。常用的是4tag事实上还有6tag和2tag 而标记分词结果最简单的方法应该是2tag即标记“切分/不切分”就够了但效果不好。为什么反而更多数目的tag效果更好呢因为更多的tag实际上更全面概括了语义规律。比如用4tag标注我们能总结出哪些字单字成词、哪些字经常用作开头、哪些字用作末尾但仅仅用2tag就只能总结出哪些字经常用作开头从归纳的角度来看是不够全面的。但6tag跟4tag比较呢我觉得不一定更好6tag的意思是还要总结出哪些字作第二字、第三字但这个总结角度是不是对的我觉得似乎并没有哪些字固定用于第二字或者第三字的这个规律的总结性比首字和末字的规律弱多了不过从新词发现的角度来看6tag更容易发现长词。 1.2.2 字标注之双向LSTM的seq2seq 关于深度学习与分词很早就有人尝试过了比如下列文章 http://blog.csdn.net/itplus/article/details/13616045 https://github.com/xccds/chinese_wordseg_keras http://www.leiphone.com/news/201608/IWvc75oJglAIsDvJ.html 这些文章中不管是用简单的神经网络还是LSTM它们的做法都跟传统模型是一样的都是通过上下文来预测当前字的标签这里的上下文是固定窗口的比如用前后5个字加上当前字来预测当前字的标签。这种做法没有什么不妥之处但仅仅是把以往估计概率的方法如HMM、ME、CRF等换为了神经网络而已整个框架是没变的本质上还是n-gram模型。而有了LSTMLSTM本身可以做序列到序列seq2seq的输出因此为什么不直接输出原始句子的序列呢这样不就真正利用了全文信息了吗这就是本文的尝试。 LSTM可以根据输入序列输出一个序列这个序列考虑了上下文的联系因此可以给每个输出序列接一个softmax分类器来预测每个标签的概率。基于这个序列到序列的思路我们就可以直接预测句子的标签。 1.3 基于语言模型的无监督分词 从最大概率法出发如果一个长度为l的字符串s1,s2,…,sl最优分词结果为w1,w2,…,wm那么它应该是所有切分中概率乘积p(w1)p(w2)…p(wm)最大 假如没有词表自然也就不存在w1,w2,…,wm这些词了。但是我们可以用贝叶斯公式将词的概率转化为字的组合概率p(w)p(c1)p(c2|c1)p(c3|c1c2)…p(ck|c1c2…ck−1)其中w是一个k字词c1,c2,…,ck分别是w的第1,2,…,k个字。可以发现p(ck|c1c2…ck−1)就是我们前面提到过的字的语言模型。 如果s1,s2应该合并为一个词那么它的路径概率是p(s1s2)p(s3)…p(sl)p(s1)p(s2|s1)p(s3)…p(sl) 对于句子中的一个字sk来说就有 p(b)p(sk) 单字词或者多字词的首字 p©p(sk|sk−1)多字词的第二字 p(d)p(sk|sk−2sk−1) 多字词的第三字 p(e)p(sk|sk−3sk−2sk−1)多字词的其余部分 这就是将分词问题变成了一种字标注问题而每个标签的概率由语言模型给出。而且显然b后面只能接b或者c类似地就得到非零的转移概率只有p(b|b),p(c|b),p(b|c),p(d|c),p(b|d),p(e|d),p(b|e),p(e|e) 这些转移概率的值决定了划分出来的是长词还是短词。最后找最优路径依旧由viterbi算法完成。
到这里问题就变成了语言模型的训练了这是无监督的。我们只需要花心思优化语言模型而这方面不论是理论还是实战都已经很成熟了有不少现成的工具可以用。简单地可以只用传统的“统计平滑”模型如果要从语义来做那么就可以用最新的神经语言模型。总而言之分词的效果取决于语言模型的质量。
2 新词发现
2.1 怎么做新词发现 参考互联网时代的社会语言学基于SNS的文本数据挖掘 怎样的文本片段才算一个词 1.看这个文本片段出现的次数是否足够多。 2.不过光是出现频数高还不够一个经常出现的文本片段有可能不是一个词而是多个词构成的词组。 内部凝固程度:令 p(x) 为文本片段 x 在整个语料中出现的概率那么我们定义“电影院”的凝合程度就是 p(电影院) 与 p(电) · p(影院) 比值和 p(电影院) 与 p(电影) · p(院) 的比值中的较小值“的电影”的凝合程度则是 p(的电影) 分别除以 p(的) · p(电影) 和 p(的电) · p(影) 所得的商的较小值。 3.我们还需要从整体来看它在外部的表现。文本片段的自由运用程度也是判断它是否成词的重要标准。如果一个文本片段能够算作一个词的话它应该能够灵活地出现在各种不同的环境中具有非常丰富的左邻字集合和右邻字集合。 我们用信息熵来衡量一个文本片段的左邻字集合和右邻字集合有多随机。考虑这么一句话“吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮”“葡萄”一词出现了四次其中左邻字分别为 {吃, 吐, 吃, 吐} 右邻字分别为 {不, 皮, 倒, 皮} 。根据公式“葡萄”一词的左邻字的信息熵为 – (1/2) · log(1/2) – (1/2) · log(1/2) ≈ 0.693 它的右邻字的信息熵则为 – (1/2) · log(1/2) – (1/4) · log(1/4) – (1/4) · log(1/4) ≈ 1.04 。可见在这个句子中“葡萄”一词的右邻字更加丰富一些。 我们不妨就把一个文本片段的自由运用程度定义为它的左邻字信息熵和右邻字信息熵中的较小值。 主要利用了三个指标——频数、凝固度取对数之后就是我们所说的互信息熵、自由度边界熵——来判断一个片段是否成词 缺点首先为了得到n字词就需要找出1∼n字的切片然后分别做计算这对于n比较大时是件痛苦的时间其次最最痛苦的事情是边界熵的计算边界熵要对每一个片段就行分组统计然后再计算这个工作量的很大的。本文提供了一种方案可以使得新词发现的计算量大大降低。 2.2 一个新的方法 新词发现做的事情就是根据语料判断给定片段是不是真的成词了而所谓成词就是它相对独立不可切分。那为什么不反过来呢为什么我们不去找一下哪些片段不能成词呢根据前面的说法我们说片段的凝固度大于一定程度时片段可能成词接下来要去考虑它的边界熵。那这不就是说如果片段的凝固度低于一定程度时这个片段就不可能成词了吗那么我们就可以在原来的语料中把它断开了。 我们可以做适当的简化如果a,b是语料中相邻两字那么可以统计(a,b)成对出现的次数#(a,b)继而估计它的频率P(a,b)然后我们分别统计a,b出现的次数#a,#b然后估计它们的频率P(a),P(b)如果 那么就应该在原来的语料中把这两个字断开。这个操作本质上就是——我们根据这个指标对原始语料进行初步的分词在完成初步分词后我们就可以统计词频了然后根据词频来筛选。 对比matrix67文章中的三个指标我们现在只用了两个频数和凝固度去掉了计算量最大的边界熵而且在计算凝固度时我们只需要计算二字片段的凝固度省掉了更多字片段的凝固度计算但是由于我们是基于切分的方式做的因此我们少了很多计算量但理论上却能够得任意长度的词语 参考链接【中文分词系列】 2. 基于切分的新词发现 import pymongodb pymongo.MongoClient().baike.items
def texts():for a in db.find(no_cursor_timeoutTrue).limit(1000000):yield a[content]from collections import defaultdict #defaultdict是经过封装的dict它能够让我们设定默认值
from tqdm import tqdm #tqdm是一个非常易用的用来显示进度的库
from math import log
import reclass Find_Words:def __init__(self, min_count10, min_pmi0):self.min_count min_countself.min_pmi min_pmiself.chars, self.pairs defaultdict(int), defaultdict(int) #如果键不存在那么就用int函数#初始化一个值int()的默认结果为0self.total 0.def text_filter(self, texts): #预切断句子以免得到太多无意义不是中文、英文、数字的字符串for a in tqdm(texts):for t in re.split(u[^\u4e00-\u9fa50-9a-zA-Z], a): #这个正则表达式匹配的是任意非中文、非英文、非数字因此它的意思就是用任意非中文、非英文、非数字的字符断开句子if t:yield tdef count(self, texts): #计数函数计算单字出现频数、相邻两字出现的频数for text in self.text_filter(texts):self.chars[text[0]] 1for i in range(len(text)-1):self.chars[text[i1]] 1self.pairs[text[i:i2]] 1self.total 1self.chars {i:j for i,j in self.chars.items() if j self.min_count} #最少频数过滤self.pairs {i:j for i,j in self.pairs.items() if j self.min_count} #最少频数过滤self.strong_segments set()for i,j in self.pairs.items(): #根据互信息找出比较“密切”的邻字_ log(self.total*j/(self.chars[i[0]]*self.chars[i[1]]))if _ self.min_pmi:self.strong_segments.add(i)def find_words(self, texts): #根据前述结果来找词语self.words defaultdict(int)for text in self.text_filter(texts):s text[0]for i in range(len(text)-1):if text[i:i2] in self.strong_segments: #如果比较“密切”则不断开s text[i1]else:self.words[s] 1 #否则断开前述片段作为一个词来统计s text[i1]self.words[s] 1 #最后一个“词”self.words {i:j for i,j in self.words.items() if j self.min_count} #最后再次根据频数过滤fw Find_Words(16, 1)
fw.count(texts())
fw.find_words(texts())import pandas as pd
words pd.Series(fw.words).sort_values(ascendingFalse)2.3 更好的新词发现算法 以文本分类为例估计最简单高效的方案就是“朴素贝叶斯分类器”了类似的比较现代的是FastText它可以看作是“朴素贝叶斯”的“神经网络版”。 要注意朴素贝叶斯基于一个朴素的假设特征之间相互独立。这个假设越成立朴素贝叶斯的效果就越好。然而对于文本来说显然上下文紧密联系这个假设还成立吗 注意到当特征之间明显不独立的时候可以考虑将特征组合之后使得特征之间的相关性减弱再用朴素贝叶斯。 比如对于文本如果以字为特征则朴素假设显然不成立如“我喜欢数学”中的“喜”和“欢”、“数”和“学”都明显相关这时候我们可以考虑将特征进行组合得到“我/喜欢/数学”这样三个片段之间的相关性就没有那么强了因此可以考虑用上述结果。 可以发现这个过程很像分词或者反过来说分词的主要目的之一就是将句子分为若干个相关性比较弱的部分便于进一步处理。从这个角度来看分的可能不一定是“词”也可能是短语、常用搭配等。 说白了分词就是为了削弱相关性降低对词序的依赖这一点哪怕在深度学习模型中都是相当重要的。有些模型不分词但是用CNN也就是把若干个字组合作为特征来看这也是通过字的组合来减弱特征间的相关性的体现。 既然分词是为了削弱相关性那么我们分词就是在相关性弱的地方切断了。 完整的算法步骤如下 第一步统计选取某个固定的n统计2grams、3grams、…、ngrams计算它们的内部凝固度只保留高于某个阈值的片段构成一个集合G这一步可以为2grams、3grams、…、ngrams设置不同的阈值不一定要相同因为字数越大一般来说统计就越不充分越有可能偏高所以字数越大阈值要越高第二步切分用上述grams对语料进行切分粗糙的分词并统计频率。切分的规则是只要一个片段出现在前一步得到的集合G中这个片段就不切分比如“各项目”只要“各项”和“项目”都在G中这时候就算“各项目”不在G中那么“各项目”还是不切分保留下来第三步回溯经过第二步“各项目”会被切出来因为第二步保证宁放过不切错。回溯就是检查如果它是一个小于等于n字的词那么检测它在不在G中不在就出局如果它是一个大于n 字的词那个检测它每个n字片段是不是在G中只要有一个片段不在就出局。还是以“各项目”为例回溯就是看看“各项目”在不在3gram中不在的话就得出局。 每一步的补充说明 1、使用较高的凝固度但综合考虑多字是为了更准比如两字的“共和”不会出现在高凝固度集合中所以会切开比如“我一共和三个人去玩”“共和”就切开了但三字“共和国”出现在高凝固度集合中所以“中华人民共和国”的“共和”不会切开2、第二步就是根据第一步筛选出来的集合对句子进行切分你可以理解为粗糙的分词然后把“粗糙的分词结果”做统计注意现在是统计分词结果跟第一步的凝固度集合筛选没有交集我们认为虽然这样的分词比较粗糙但高频的部分还是靠谱的所以筛选出高频部分3、第三步例如因为“各项”和“项目”都出现高凝固度的片段中所以第二步我们也不会把“各项目”切开但我们不希望“各项目”成词因为“各”跟“项目”的凝固度不高“各”跟“项”的凝固度高不代表“各”跟“项目”的凝固度高所以通过回溯把“各项目”移除只需要看一下“各项目”在不在原来统计的高凝固度集合中即可所以这步计算量是很小的 参考【中文分词系列】 8. 更好的新词发现算法
