龙岗商城网站建设哪家便宜,潍坊哪里做网站好,百度客户管理系统登录,万网首页结巴分词器工作原理
结巴分词是一款python写成的开源中文分词器#xff0c;分词过程大致如下#xff1a;
首先#xff0c;结巴使用正则表达式将输入文本切割成若干中文块#xff0c;接着对每个中文块B做处理#xff0c;将B转成有向无环图(DAG)。DAG是以{key:list[i,j...…结巴分词器工作原理
结巴分词是一款python写成的开源中文分词器分词过程大致如下
首先结巴使用正则表达式将输入文本切割成若干中文块接着对每个中文块B做处理将B转成有向无环图(DAG)。DAG是以{key:list[i,j...], ...}的字典结构存储其中key是词在block中的起始位置list存放的是block中以位置key开始的可能词语的结束位置。这里所谓的可能词语指的是词典里有的词基本上所有的中文分词器都离不开词典。比如“特性开通”生成的DAG如下
{0: [0, 1], 1: [1], 2: [2, 3], 3: [3]}亦即特、性、开、通、特性、开通这6个词在词典里都存在。
接下来结巴会区分两种模式全模式和精准模式。
全模式只是简单的遍历DAG所以全模式速度是最快的它找出所有可能的分词比如“清华大学”结巴会找出
清华/ 清华大学/ 华大/ 大学这是一个全集因为这些词都是词典里已经存在的。
注意全模式分词逻辑上并不一定是正确的它依赖于词典的完备性比如“话统计算”理应分词为
话统/ 计算但由于结巴自带的词典里没有收录“话统”这个词全模式会把它分成 话/ 统计/ 计算 这时我们需要手动把“话统”这个词加进词典全模式才会分词为
话统/ 统计/ 计算精准模式则不是简单的遍历DAG它采用动态规划查找最大概率路径, 找出基于词频的最大切分组合基本思路就是对句子从右往左反向计算最大概率最后得到最大概率路径所以“清华大学”在精准模式下会分成
清华/大学下面是用动态规划计算最大概率路径的核心算法 #动态规划计算最大概率的切分组合def calc(self, sentence, DAG, route):N len(sentence)route[N] (0, 0)# 对概率值取对数之后的结果(可以让概率相除的计算变成对数相减,防止相除造成下溢)logtotal log(self.total)# 从后往前遍历句子 反向计算最大概率for idx in xrange(N - 1, -1, -1):# 列表推导求最大概率对数路径# route[idx] max([ (概率对数词语末字位置) for x in DAG[idx] ])# 以idx:(概率对数最大值词语末字位置)键值对形式保存在route中# route[x1][0] 表示 词路径[x1,N-1]的最大概率对数,# [x1][0]即表示取句子x1位置对应元组(概率对数词语末字位置)的概率对数route[idx] max((log(self.FREQ.get(sentence[idx:x 1]) or 1) -logtotal route[x 1][0], x) for x in DAG[idx])从代码中可以看出calc是一个自底向上的动态规划它从block的最后一个字(N-1)开始倒序遍历block的每个字位置为idx计算子句block[idx~N-1]概率对数得分这里利用DAG及历史计算结果实现同时作者使用了概率对数这样有效防止浮点数下溢问题。然后将概率对数得分最高的情况以概率对数词语最后一个字的位置这样的tuple保存在route中。这样route已经把概率最大路径给标出来了tuple[1]就是这条路径的中间节点。
由上可知由于精准模式额外使用了动态规划算法效率肯定不及全模式高。
未登录词的处理
所谓未登录词就是词典里没有收录的词前面说过中文分词器离不开词典那词典没这个词我又如何能把它识别出来呢结巴使用的是基于隐马尔可夫模型HMM的Viterbi 算法。
HMM 模型有个五元组表示
{ states//状态空间 observations//观察空间 start_probability//状态的初始分布 transition_probability//状态的转移概率emission_probability//状态产生观察的概率}
其中states(状态空间) 用B E M S四个状态来标记汉字在一个词中可能出现的位置分别代表 Begin End Middle 和 Single B代表该字是词语中的起始字M代表是词语中的中间字E代表是词语中的结束字S则代表是单字成词。
observations(观察空间)就是所有汉字甚至包括标点符号所组成的集合。
由状态空间的元素组成的序列称为状态序列类似的观察空间的元素组成了观察序列。
在HMM模型中文分词中观察序列是输入就是待分词的句子状态序列是输出是这个句子中每个字的状态值。 如
观察序列我在北京 状态序列SSBE 对于上面的状态序列按简单的规则例如B后面只可能接M or E不可能接B or S而M后面也只可能接M or E不可能接B or S做划分即可得到分词方案这里状态序列要划分成 S/S/BE/ 则最终的分词结果是
我/ 在/ 北京/ 现在只剩下一个问题了如何从观察序列中得到状态序列这就要用到Viterbi 算法和那三个概率初始、转移、发射概率具体的实现算法可参看相关文章。
至于转移、发射概率的值是可以从语料库中训练得到的对语料库中各种情况的出现次数做统计即可。
本质上未登录词的识别是一个序列标注问题。
从词频到概率的转换
结巴词典里存的是词频但分词的时候要计算多条分词路径的最大概率所以这里有个“词频-概率”的转换过程结巴会在生成前缀词典的时候用self.FREQ存储每个词的词频用self.total记录总词频。相关代码为
def gen_pfdict(self, f):lfreq {}ltotal 0f_name resolve_filename(f)for lineno, line in enumerate(f, 1):try:line line.strip().decode(utf-8)word, freq line.split( )[:2]freq int(freq)lfreq[word] freqltotal freqfor ch in xrange(len(word)):wfrag word[:ch 1]if wfrag not in lfreq:lfreq[wfrag] 0except ValueError:raise ValueError(invalid dictionary entry in %s at Line %s: %s % (f_name, lineno, line))f.close()return lfreq, ltotaldef initialize(self, dictionaryNone):...self.FREQ, self.total self.gen_pfdict(self.get_dict_file()) ...概率的计算方法则是
某个词的词频/总词频
见calc函数
def calc(self, sentence, DAG, route):N len(sentence)route[N] (0, 0)logtotal log(self.total)for idx in xrange(N - 1, -1, -1):route[idx] max((log(self.FREQ.get(sentence[idx:x 1]) or 1) -logtotal route[x 1][0], x) for x in DAG[idx])注意这个部分
(log(self.FREQ.get(sentence[idx:x 1]) or 1) - logtotal这里计算[idx,x]所组词的概率实际是词频/总词频,因取了对数所以变成了减法。
如何消除分词错误
jieba下可通过添加新词、加大词频等方式解决分词错误。默认词频数一般是4如果分不出来可以加到10甚至更大。
jieba的优点在于我们可以通过调整词频数这么一个很简单的方式就获得我们希望的分词效果但这也是它的缺点因为汉语分词的最大问题在于“切分歧义”在不同的语境下可以有不同的切分方法。例如
这个标志牌是指示前进的方向该物品是指示例中的图片吗两句话里都有“是指示”但前者应切分为“是/指示”后者则应切分为“是指/示例”。
由于jieba核心词典没有收录“是指”这个词所以我们加一条
是指 100000 v
则第二句话划分没问题了
该/ 物品/ 是指/ 示例/ 中/ 的/ 图片/ 吗注意这里为了超过“指示”成词的概率我们将“是指”的词频调的很高也许过高了实测调成10000即可这里为了说明问题改成了10w确保最大概率路径往“是指”倾斜。但这样写死概率的做法很不灵活一旦有下面的情况
这个标志牌是指明前进的方向就会分词为
这个/ 标志牌/ 是指/ 明/ 前进/ 的/ 方向也就是说写死的概率在保证语境A下分词成功的同时有可能造成语境B分词错误
究其原因在于相邻词的概率不同“指示”的词频大于“指明”所以“是指示”划分没问题“是指明”则划分的有问题了。
综上只依靠设置单个词的词频是解决不了“切分歧义”问题的因为它没考虑句子的上下文情境。所以这是jieba分词的问题。
