jieba分词学习笔记（三）

nevermind 发布于2019-07-24 18:16 / 2803人阅读

摘要：由此得到了，下一步就是使用动态规划对最大概率路径进行求解。最大概率路径值得注意的是，的每个结点，都是带权的，对于在词典里面的词语，其权重为其词频，即。动态规划求解法满足的条件有两个重复子问题最优子结构我们来分析最大概率路径问题。

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 < N 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])

GPU云服务器云服务器 jieba分词学习笔记学习笔记一基础学习笔记

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37649.html

jieba分词学习笔记（二）

分词模式 jieba分词有多种模式可供选择。可选的模式包括：全切分模式精确模式搜索引擎模式同时也提供了HMM模型的开关。其中全切分模式就是输出一个字串的所有分词，精确模式是对句子的一个概率最佳分词，而搜索引擎模式提供了精确模式的再分词，将长词再次拆分为短词。效果大抵如下： # encoding=utf-8 import jieba seg_list = jieba.cut(我...

fxp 2019-07-24 18:16 评论0 收藏0
分词，难在哪里？科普+解决方案！

摘要：分词的算法中文分词有难度，不过也有成熟的解决方案。例如通过人民日报训练的分词系统，在网络玄幻小说上，分词的效果就不会好。三的优点是开源的，号称是中，最好的中文分词组件。 showImg(https://segmentfault.com/img/remote/1460000016359704?w=1350&h=900); 题图：by Lucas Davies 一、前言分词，我想是大多数...

Steven 2019-07-30 17:48 评论0 收藏0
Python第三方库jieba库与中文分词全面详解

　　Python在工作中的应用还是比较的广泛的，市场上面对于这类人才开出的薪资还是比较的高的。那么，如何使用第三方库jieba库与中文分词进行一个分解呢？下面小编就给大家详细的做出一个解答。　　一、什么是jieba库　　jieba是优秀的中文分词第三方库，由于中文文本之间每个汉字都是连续书写的，我们需要通过特定的手段来获得其中的每个词组，这种手段叫做分词，我们可以通过jieba库来完成这个过程。　...

89542767 2022-11-05 11:41 评论0 收藏0
python 实现中文分词统计

摘要：利用我们集成的目前世界上规模最大的人工分词和词性标注中文语料库约含万字训练而成，模型标注能力强大。据说是最好的中文分词组件，支持等多种语言。总是看到别人用Python搞各种统计，前端菜鸟的我也来尝试了一把。有各种语义分析库在，一切好像并不是很复杂。不过Python刚开始看，估计代码有点丑。一、两种中文分词开发包 thulac (http://thulac.thunlp.org/)...

Honwhy 2019-07-30 14:52 评论0 收藏0