摘要：我來(lái)到北京清華大學(xué)對(duì)應(yīng)的狀態(tài)應(yīng)該為其實(shí)和的區(qū)別就是對(duì)未成功切分的部分，沒(méi)有使用進(jìn)行分詞。

結(jié)巴分詞是一個(gè)受大家喜愛(ài)的分詞庫(kù)，源碼地址為github，今天我們就跟進(jìn)源碼，看一下結(jié)巴分詞的原理

    def cut(self, sentence, cut_all=False, HMM=True):
        """
        The main function that segments an entire sentence that contains
        Chinese characters into separated words.

        Parameter:
            - sentence: The str(unicode) to be segmented.
            - cut_all: Model type. True for full pattern, False for accurate pattern.
            - HMM: Whether to use the Hidden Markov Model.
        """

使用結(jié)巴分詞的時(shí)候，有三種模式，這三種模式的進(jìn)入條件分別為：

        if cut_all:
            cut_block = self.__cut_all
        elif HMM:
            cut_block = self.__cut_DAG
        else:
            cut_block = self.__cut_DAG_NO_HMM

首先我們看一下這三種模式

__cut_all:

原句：我來(lái)到北京清華大學(xué)　結(jié)果：我/ 來(lái)到/ 北京/ 清華/ 清華大學(xué)/ 華大/ 大學(xué)

原句：他來(lái)到了網(wǎng)易杭研大廈　結(jié)果：他/ 來(lái)到/ 了/ 網(wǎng)易/ 杭/ 研/ 大廈

__cut_DAG:

原句：我來(lái)到北京清華大學(xué)　結(jié)果:我/ 來(lái)到/ 北京/ 清華大學(xué)

原句：他來(lái)到了網(wǎng)易杭研大廈 結(jié)果：他/ 來(lái)到/ 了/ 網(wǎng)易/ 杭研/ 大廈

__cut_DAG_NO_HMM:

原句：我來(lái)到北京清華大學(xué)　結(jié)果:我/ 來(lái)到/ 北京/ 清華大學(xué)

原句：他來(lái)到了網(wǎng)易杭研大廈 結(jié)果：他/ 來(lái)到/ 了/ 網(wǎng)易/ 杭/ 研/ 大廈

下面我們就來(lái)分析一下這三種模式：
這三種模式有一個(gè)共同點(diǎn)，第一步都是先構(gòu)造DAG，也就是構(gòu)造有向無(wú)環(huán)圖。
源碼如下：

    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

如果sentence是"我來(lái)到北京清華大學(xué)‘，那么DAG為

{0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}

直觀上來(lái)看，DAG[5]=[5,6,8]的意思就是，以’清‘開(kāi)頭的話(huà)，分別以5、6、8結(jié)束時(shí)，可以是一個(gè)詞語(yǔ)，即’清‘、’清華‘、’清華大學(xué)‘
get_DAG方法中，最重要的也就是self.FREQ了，它是怎么來(lái)的呢？

其實(shí)就是通過(guò)jieba目錄下，dict.txt文件來(lái)產(chǎn)生的self.FREQ,方法如下：
dict.txt共有349046行，每一行格式為：

一 217830 m
一一 1670 m
一一二 11 m
一一例 3 m
一一分 8 m
一一列舉 34 i

第一部分為詞語(yǔ)，第二部分為該詞出現(xiàn)的頻率，第三部分為該詞的詞性。
以讀取’一一列舉‘為例子，首先執(zhí)行self.FREQ["一一列舉"]=34，然后會(huì)檢查’一‘、’一一‘、’一一列‘、’一一列舉‘之前是否在self.FREQ中存儲(chǔ)過(guò)，如果之前存儲(chǔ)過(guò)，則跳過(guò)，否則執(zhí)行self.FREQ["一"]=0，self.FREQ["一一"]=0，self.FREQ["一一列"]=0
所以self.FREQ中不止存儲(chǔ)了正常的詞語(yǔ)和它出現(xiàn)的次數(shù)，同時(shí)也存儲(chǔ)了所有詞語(yǔ)的前綴，并將前綴出現(xiàn)的次數(shù)設(shè)置為0,以和正常詞語(yǔ)區(qū)別開(kāi)。

好了，現(xiàn)在DAG這部分我們介紹完了，然后我們分開(kāi)來(lái)介紹一下這三種模式：

源碼如下：

    def __cut_all(self, sentence):
        dag = self.get_DAG(sentence)
        old_j = -1
        for k, L in iteritems(dag):
            if len(L) == 1 and k > old_j:
                yield sentence[k:L[0] + 1]
                old_j = L[0]
            else:
                for j in L:
                    if j > k:
                        yield sentence[k:j + 1]
                        old_j = j

這個(gè)具體的遍歷方式我們就不細(xì)說(shuō)了，大家自行看源碼吧

    def __cut_DAG(self, sentence):
        DAG = self.get_DAG(sentence)
        route = {}
        self.calc(sentence, DAG, route)
        ......

首先我們先看一下self.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])

這里使用了一個(gè)技巧，也就是log(a) + log(b) = log(ab)，從而巧妙的避過(guò)了乘法，也就避免了溢出的風(fēng)險(xiǎn)。
其實(shí)calc函數(shù)就是實(shí)現(xiàn)了vertibi算法，不了解vertibi算法的同學(xué)自行百度吧。

然后再貼上整個(gè)__cut_DAG的源碼：

    def __cut_DAG(self, sentence):
        DAG = self.get_DAG(sentence)
        route = {}
        self.calc(sentence, DAG, route)
        x = 0
        buf = ""
        N = len(sentence)
        while x < N:
            y = route[x][1] + 1
            l_word = sentence[x:y]
            if y - x == 1:
                buf += l_word
            else:
                if buf:
                    if len(buf) == 1:
                        yield buf
                        buf = ""
                    else:
                        if not self.FREQ.get(buf):
                            recognized = finalseg.cut(buf)
                            for t in recognized:
                                yield t
                        else:
                            for elem in buf:
                                yield elem
                        buf = ""
                yield l_word
            x = y

        if buf:
            if len(buf) == 1:
                yield buf
            elif not self.FREQ.get(buf):
                recognized = finalseg.cut(buf)
                for t in recognized:
                    yield t
            else:
                for elem in buf:
                    yield elem

其中，重點(diǎn)關(guān)注這一部分

                        if not self.FREQ.get(buf):
                            recognized = finalseg.cut(buf)
                            for t in recognized:
                                yield t

什么時(shí)候會(huì)進(jìn)入finalseg.cut(buf)呢？實(shí)際上，就是當(dāng)遇到一些dict.txt中沒(méi)出現(xiàn)的詞的時(shí)候，才會(huì)進(jìn)入這個(gè)函數(shù)：
在這個(gè)函數(shù)中，就是使用HMM的方法，對(duì)這些未識(shí)別成功的詞進(jìn)行標(biāo)注，然后我們來(lái)介紹一下項(xiàng)目中相關(guān)的內(nèi)容：

其中，prob_start.py存儲(chǔ)的是HMM的起始狀態(tài)相關(guān)的信息，文件中的數(shù)字都經(jīng)過(guò)log處理過(guò)：

P={"B": -0.26268660809250016,
 "E": -3.14e+100,
 "M": -3.14e+100,
 "S": -1.4652633398537678}

B代表begin，E代表end，M代表middle，S代表single。所以在開(kāi)始時(shí)，HMM的狀態(tài)只可能是S或者B，而E和M為負(fù)無(wú)窮
prob_trans.py存儲(chǔ)的是狀態(tài)轉(zhuǎn)移矩陣：

P={"B": {"E": -0.510825623765990, "M": -0.916290731874155},
 "E": {"B": -0.5897149736854513, "S": -0.8085250474669937},
 "M": {"E": -0.33344856811948514, "M": -1.2603623820268226},
 "S": {"B": -0.7211965654669841, "S": -0.6658631448798212}}

prob_emit.py中存儲(chǔ)的是在該狀態(tài)下出現(xiàn)該漢字的概率，例如p("劉"|S)=-0.916

P={"B": {"u4e00": -3.6544978750449433,
       "u4e01": -8.125041941842026,
       "u4e03": -7.817392401429855,
       "u4e07": -6.3096425804013165,
       "u4e08": -8.866689067453933,
       "u4e09": -5.932085850549891,
       "u4e0a": -5.739552583325728,
       "u4e0b": -5.997089097239644,
       "u4e0d": -4.274262055936421,
       "u4e0e": -8.355569307500769,
       ......

通過(guò)這種方式，也就可以進(jìn)行分詞了。
‘我/ 來(lái)到/ 北京/ 清華大學(xué)’對(duì)應(yīng)的狀態(tài)應(yīng)該為"SBEBEBMME"

其實(shí)__cut_DAG_NO_HMM和__cut_DAG的區(qū)別就是：對(duì)vertibi未成功切分的部分，__cut_DAG_NO_HMM沒(méi)有使用HMM進(jìn)行分詞。源碼如下：

    def __cut_DAG_NO_HMM(self, sentence):
        DAG = self.get_DAG(sentence)
        route = {}
        self.calc(sentence, DAG, route)
        x = 0
        N = len(sentence)
        buf = ""
        while x < N:
            y = route[x][1] + 1
            l_word = sentence[x:y]
            if re_eng.match(l_word) and len(l_word) == 1:
                buf += l_word
                x = y
            else:
                if buf:
                    yield buf
                    buf = ""
                yield l_word
                x = y
        if buf:
            yield buf
            buf = ""