首页 > 代码库 > Jieba分词包(三)——基于词频最大切分组合
Jieba分词包(三)——基于词频最大切分组合
Jieba分词包(三)——基于词频最大切分组合
在前面,我们已经知道dict中所有的单词和词频信息已经存在了一个trie树中,并且需要分词的句子已经构建成了一个DAG图,构建的过程也运用了dict。那么这次我们来说如何基于每句话的DAG图,找到一个组合路径,使得该组合最合理(即打分最高)?
我们直接针对Jieba分词的源代码来解释,其中已经有了很多注释:
def calc(sentence,DAG,idx,route): #动态规划,计算最大概率的切分组合 #输入sentence是句子,DAG句子的有向无环图 N = len(sentence) #句子长度 route[N] = (0.0,'') for idx in xrange(N-1,-1,-1): #和range用法一样,不过还是建议使用xrange #可以看出是从后往前遍历每个分词方式的 #下面的FREQ保存的是每个词在dict中的频度得分,打分的公式是 log(float(v)/total),其中v就是被打分词语的频数 #FREQ.get(sentence[idx:x+1],min_freq)表示,如果字典get没有找到这个key,那么我们就使用最后的frequency来做 #由于DAG中是以字典+list的结构存储的,所以确定了idx为key之外, #仍然需要for x in DAG[idx]来遍历所有的单词结合方式(因为存在不同的结合方法,例如“国”,“国家”等) #以(频度得分值,词语最后一个字的位置)这样的tuple保存在route中 candidates = [ ( FREQ.get(sentence[idx:x+1],min_freq) + route[x+1][0] , x ) for x in DAG[idx] ] route[idx] = max(candidates)
整体的思路就是使用动态规划方法,从后往前遍历,选择一个频度得分最大的一个切分组合。
那么可能会问为何是从后往前实现动态规划呢?因为汉语句子的重心经常落在后面, 就是落在右边, 因为通常情况下形容词太多, 后面的才是主干, 因此, 从右往左计算, 正确率要高于从左往右计算, 这个类似于逆向最大匹配!
http://ddtcms.com/blog/archive/2013/2/4/69/jieba-fenci-suanfa-lijie/
http://blog.csdn.net/rav009/article/details/12310077
Jieba分词包(三)——基于词频最大切分组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。