数据价值-DataValues

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 571|回复: 0

[python] jieba分词学习笔记(三)_python jieba中文分词

[复制链接]

1万

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
39787
发表于 2017-5-15 20:52:38 | 显示全部楼层 |阅读模式
jieba分词学习笔记(三),
关键词:jieba分词 python、python jieba中文分词、数据分析师,DAG(有向无环图),
有向无环图,directed acyclic graphs,简称DAG,是一种图的数据结构,其实很naive,就是没有环的有向图_(:з」∠)_,
DAG在分词中的应用很广,无论是最大概率路径,还是后面套NN的做法,DAG都广泛存在于分词中。,
因为DAG本身也是有向图,所以用邻接矩阵来表示是可行的,但是jieba采用了python的dict,更方便地表示DAG,其表示方法为:,{prior1:[next1,next2...,nextN],prior2:[next1',next2'...nextN']...},
以句子 “国庆节我在研究结巴分词”为例,其生成的DAG的dict表示为:,{0: [0, 1, 2], 1: [1], 2: [2], 3: [3], 4: [4], 5: [5, 6], 6: [6], 7: [7, 8], 8: [8], 9: [9, 10], 10: [10]}
其中,
国[0] 庆[1] 节[2] 我[3] 在[4] 研[5] 究[6] 结[7] 巴[8] 分[9] 词[10],
get_DAG()函数代码如下:,def get_DAG(self, sentence):
        self.check_initialized()
        DAG = {}
        N = len(sentence)
        for k in xrange(N):
            tmplist = []
            i = k
            frag = sentence[k]
            while i and frag in self.FREQ:
                if self.FREQ[frag]:
                    tmplist.append(i)
                i += 1
                frag = sentence[k:i + 1]
            if not tmplist:
                tmplist.append(k)
            DAG[k] = tmplist
        return DAG,
frag即fragment,可以看到代码循环切片句子,FREQ即是词典的{word:frequency}的dict,
因为在载入词典的时候已经将word和word的所有前缀加入了词典,所以一旦frag not in FREQ,即可以断定frag和以frag为前缀的词不在词典里,可以跳出循环。,
由此得到了DAG,下一步就是使用dp动态规划对最大概率路径进行求解。,最大概率路径,
值得注意的是,DAG的每个结点,都是带权的,对于在词典里面的词语,其权重为其词频,即FREQ[word]。我们要求得route = (w1, w2, w3 ,.., wn),使得Σweight(wi)最大。,动态规划求解法,
满足dp的条件有两个,
  • 重复子问题
  • 最优子结构
    ,
    我们来分析最大概率路径问题。,重复子问题,
    对于结点Wi和其可能存在的多个后继Wj和Wk,有:,任意通过Wi到达Wj的路径的权重为该路径通过Wi的路径权重加上Wj的权重{Ri->j} = {Ri + weight(j)} ;
    任意通过Wi到达Wk的路径的权重为该路径通过Wi的路径权重加上Wk的权重{Ri->k} = {Ri + weight(k)} ;,
    即对于拥有公共前驱Wi的节点Wj和Wk,需要重复计算到达Wi的路径。,最优子结构,
    对于整个句子的最优路径Rmax和一个末端节点Wx,对于其可能存在的多个前驱Wi,Wj,Wk…,设到达Wi,Wj,Wk的最大路径分别为Rmaxi,Rmaxj,Rmaxk,有:,
    Rmax = max(Rmaxi,Rmaxj,Rmaxk…) + weight(Wx),
    于是问题转化为,
    求Rmaxi, Rmaxj, Rmaxk…,
    组成了最优子结构,子结构里面的最优解是全局的最优解的一部分。,状态转移方程,
    由上一节,很容易写出其状态转移方程,
    Rmax = max{(Rmaxi,Rmaxj,Rmaxk…) + weight(Wx)},代码,
    上面理解了,代码很简单,注意一点total的值在加载词典的时候求出来的,为词频之和,然后有一些诸如求对数的trick,代码是典型的dp求解代码。,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]),
    转载请注明:数据分析 » jieba分词学习笔记(三)_python jieba中文分词
  • 回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    小黑屋|Archiver|手机版|DataValues ( 赣ICP备16006919号-3 点击这里给我发消息 DataValues

    GMT+8, 2018-12-11 20:21 , Processed in 0.106283 second(s), 32 queries .

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表