jieba分词原理-DAG(NO HMM)，jieba分词原理

jieba分词原理-DAG(NO HMM)，jieba分词原理

最近公司在做一个推荐系统,让我给论坛上的帖子找关键字,当时给我说让我用jieba分词,我周末回去看了看,感觉不错,还学习了一下具体的原理

首先,通过正则表达式,将文章内容切分,形成一个句子数组,这个比较好理解

然后构造出句子的有向无环图(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)#如果可以成词就加入到DAG中
                i += 1
                frag = sentence[k:i + 1]
            if not tmplist:
                tmplist.append(k)#如果找不到词语,就将自己加入DAG
            DAG[k] = tmplist
        return 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((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                              logtotal + route[x + 1][0], x) for x in DAG[idx])

如上图,蓝色圈中的部分,括号右边代表了成词的位置,比如2,括号的右边是4,说明2-4这个词的成词概率高,我们就切成'海淀区'

切分的过程是这样的

这样,我们就能得到:0/1/2-4/5/6/7/8-10

具体为:我/从/海淀区/搬/到/了/朝阳区

到此为止整个过程就结束了

不过,官方默认算法还有个hmm,这次先不说了,请听下回分解