一、概述

分詞器的作用是將一串字符串改為“詞”的列表，下面以“大學(xué)生活”這個(gè)輸入為例進(jìn)行講解：

對(duì)“大學(xué)生活”這句話做分詞，通常來(lái)說(shuō)，一個(gè)分詞器會(huì)分三步來(lái)實(shí)現(xiàn)：

（1）找到“大學(xué)生活”這句話中的全部詞做為一個(gè)集合，即：[大、大學(xué)、大學(xué)生、學(xué)、學(xué)生、生、生活、活]

（2）在第一步中得到的集合中找到所有能組合成“大學(xué)生活”這句話的子集，即：

[大、學(xué)、生、活]

[大、學(xué)、生活]

[大、學(xué)生、活]

[大學(xué)、生、活]

[大學(xué)、生活]

[大學(xué)生、活]

（3）在第二步中產(chǎn)生的所有子集中挑選一個(gè)最有可能的作為最終的分詞結(jié)果。

為了得到第1步需要的集合，通常我們需要一個(gè)詞典。大部分的分詞器都是基于詞典去做分詞的(也就是說(shuō)也可以不基于詞典來(lái)做分詞，在此暫時(shí)不做討論)。那么現(xiàn)在假設(shè)我們有一個(gè)小詞典：[大學(xué)、大學(xué)生、學(xué)習(xí)、學(xué)習(xí)機(jī)、學(xué)生、生氣、生活、活著]。首先要在“大學(xué)生活”這句話里面匹配到這個(gè)詞典里面的全部詞，有些同學(xué)腦中可能會(huì)出現(xiàn)這種過(guò)程：

public class Demo1{
    //加載詞典中的所有詞匯
    static Set<String> dic  = new HashSet(){{
        add("大學(xué)");
        add("大學(xué)生");
        add("學(xué)習(xí)");
        add("學(xué)習(xí)機(jī)");
        add("學(xué)生");
        add("生氣");
        add("生活");
        add("活著");
    }};
    //匹配句子中詞典中存在的所有詞匯
    static List<String> getAllWordsMatched(String sentence){
        List<String> wordList = new ArrayList<>();
        for(int index = 0;index < sentence.length();index++){
            for(int offset = index+1; offset <= sentence.length();offset++){
                String sub = sentence.substring(index,offset);
                if(dic.contains(sub)){
                    wordList.add(sub);
                }
            }
        }
        return wordList;
    }
    public static void main(String[] args){
        String sentence = "大學(xué)生活";
        getAllWordsMatched(sentence).forEach(System.out::println);
    }
}

執(zhí)行這段代碼會(huì)輸出：

大學(xué)

大學(xué)生

學(xué)生

生活

似乎到這里，我們已經(jīng)完美地完成了在詞典中找到詞的任務(wù)。然而真實(shí)的分詞器的詞典往往有幾十萬(wàn)甚至幾百萬(wàn)的詞匯量，使用上面這種算法性能太低了。高效地實(shí)現(xiàn)這種匹配的算法有很多，下面簡(jiǎn)單介紹一種：

二、AC自動(dòng)機(jī)(Aho-Corasick automaton)

AC自動(dòng)機(jī)是一種常用的多模式匹配算法，基于字典樹(shù)(trie樹(shù))的數(shù)據(jù)結(jié)構(gòu)和KMP算法的失敗指針的思想來(lái)實(shí)現(xiàn)，有不錯(cuò)的性能并且實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單。

2.1、字典樹(shù)(trie樹(shù))

引用一下百度百科對(duì)于trie樹(shù)的描述：Trie樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹(shù)高。

下面一個(gè)存放了[大學(xué)、大學(xué)生、學(xué)習(xí)、學(xué)習(xí)機(jī)、學(xué)生、生氣、生活、活著]這個(gè)詞典的trie樹(shù)：

它可以看作是用每個(gè)詞第n個(gè)字做第n到第n+1層節(jié)點(diǎn)間路徑哈希值的哈希樹(shù)，每個(gè)節(jié)點(diǎn)是實(shí)際要存放的詞。

現(xiàn)在用這個(gè)樹(shù)來(lái)進(jìn)行“大學(xué)生活”的匹配。依然從“大”字開(kāi)始匹配，如下圖所示：從根節(jié)點(diǎn)開(kāi)始，沿最左邊的路徑匹配到了大字，沿著“大”節(jié)點(diǎn)可以匹配到“大學(xué)”,繼續(xù)匹配則可以匹配到“大學(xué)生”，之后字典中再?zèng)]有以“大”字開(kāi)頭的詞，至此已經(jīng)匹配到了[大學(xué)、大學(xué)生]第一輪匹配結(jié)束。

繼續(xù)匹配“學(xué)”字開(kāi)頭的詞，方法同上步，可匹配出[學(xué)生]

繼續(xù)匹配“生”和“活”字開(kāi)頭的詞，這樣“大學(xué)生活”在詞典中的詞全部被查出來(lái)。

可以看到，以匹配“大”字開(kāi)頭的詞為例，第一種匹配方式需要在詞典中查詢是否包含“大”、“大學(xué)”、“大學(xué)”、“大學(xué)生活”，共4次查詢，而使用trie樹(shù)查詢時(shí)當(dāng)找到“大學(xué)生”這個(gè)詞之后就停止了該輪匹配，減少了匹配的次數(shù)，當(dāng)要匹配的句子越長(zhǎng)，這種性能優(yōu)勢(shì)就越明顯。

2.2、失敗指針

再來(lái)看一下上面的匹配過(guò)程，在匹配“大學(xué)生”這個(gè)詞之后，由于詞典中不存在其它以“大”字開(kāi)頭的詞，本輪結(jié)束，將繼續(xù)匹配以“學(xué)”字開(kāi)頭的詞，這時(shí)，需要再回到根節(jié)點(diǎn)繼續(xù)匹配，如果這個(gè)時(shí)候“大學(xué)生”節(jié)點(diǎn)有個(gè)指針可以直指向“學(xué)生”節(jié)點(diǎn)，就可以減少一次查詢，類似地，當(dāng)匹配完“學(xué)生”之后如果“學(xué)生”節(jié)點(diǎn)有個(gè)指針可以指向“生活”節(jié)點(diǎn)，就又可以減少一次查詢。這種當(dāng)下一層節(jié)點(diǎn)無(wú)法匹配需要進(jìn)行跳轉(zhuǎn)的指針就是失敗指針，創(chuàng)建好失敗指針的樹(shù)看起來(lái)如下圖：

圖上紅色的線就是失敗指針，指向的是當(dāng)下層節(jié)點(diǎn)無(wú)法匹配時(shí)應(yīng)該跳轉(zhuǎn)到哪個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行匹配。

失敗指針的創(chuàng)建過(guò)程通常為：

1.創(chuàng)建好trie樹(shù)。

2.BFS每一個(gè)節(jié)點(diǎn)(不能使用DFS，因?yàn)槊恳粚庸?jié)點(diǎn)的失敗指針在創(chuàng)建時(shí)要確保上一層節(jié)點(diǎn)的失敗指針全部創(chuàng)建完成)。

3.根節(jié)點(diǎn)的子節(jié)點(diǎn)的失敗指針指向根節(jié)點(diǎn)。

4.其它節(jié)點(diǎn)查找其父節(jié)點(diǎn)的失敗指針指向的節(jié)點(diǎn)的子節(jié)點(diǎn)是否有和該節(jié)點(diǎn)字相同的節(jié)點(diǎn)，如果有則失敗指針指向該節(jié)點(diǎn)，如果沒(méi)有則重復(fù)剛才的過(guò)程直至找到字相同的節(jié)點(diǎn)或根節(jié)點(diǎn)。

查詢過(guò)程如下：

執(zhí)行這段代碼會(huì)輸出：

大學(xué)

大學(xué)生

學(xué)生

生活

在匹配到了詞典中所有出現(xiàn)在句子中的詞之后，繼續(xù)第二步：在得到的集合中找到所有能組合成“大學(xué)生活”這個(gè)句子的子集。但是在這個(gè)地方遇到了一個(gè)小問(wèn)題，上面查到的4個(gè)詞中僅有“大學(xué)”和“生活”這兩個(gè)詞可以組成“大學(xué)生活”這個(gè)句子，而“大學(xué)生”和“生活”則無(wú)法在匹配到的詞中找到能夠與其連接的詞匯?，F(xiàn)實(shí)情況中，詞典很難囊括所有詞匯，所以這種情況時(shí)有發(fā)生。在這里，可以額外將單個(gè)字放到匹配到的詞的集合中，這得到了一個(gè)新集合：

[大學(xué)、大學(xué)生、學(xué)生、生活]U[大、學(xué)、生、活] = [大學(xué)、大學(xué)生、學(xué)生、生活、大、學(xué)、生、活]

可以用一個(gè)有向圖來(lái)表示這個(gè)集合的分詞組合，從開(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的全部路徑就是所有分詞方式。

三、最終的分詞結(jié)果

那么在這些可能的分詞組合中，應(yīng)該選取哪一種作為最終的分詞結(jié)果呢？大部分分詞器的主要差異也體現(xiàn)在這里，有些分詞器可能有很多不同的分詞策略供使用者選擇。例如最少詞策略，就是在有向圖中選擇能夠達(dá)到結(jié)束節(jié)點(diǎn)的全部路徑中最短(經(jīng)過(guò)最少節(jié)點(diǎn))的一條。對(duì)于上面這張有向圖，最短路徑有兩條，分別是“大學(xué)，生活”與“大學(xué)生，活”最終的分詞結(jié)束就在這兩條路徑中選擇一條。這種選擇方法最為簡(jiǎn)單，性能也很高，但是準(zhǔn)確性較差。其實(shí)仔細(xì)考慮一下不難發(fā)現(xiàn)，無(wú)論使用哪種分詞策略，其目的都是想要挑選出一條最可能正確的，也就是概率最大的一種。“大學(xué)生活”分詞為[大、學(xué)、活]的概率為P(大)P(學(xué)|大)P(生|大,學(xué))P(活|大,學(xué),生)，這就是說(shuō)，想要計(jì)算其的概率，需要知道“大”的出現(xiàn)概率，“大”出現(xiàn)時(shí)“學(xué)”出現(xiàn)的概率，“大”、“學(xué)”同時(shí)出現(xiàn)時(shí)“生”的概率，“大”，“學(xué)”，“生”同時(shí)出現(xiàn)時(shí)出現(xiàn)“活”的概率。這些出現(xiàn)概率可以在一份由大量文章組成的文本庫(kù)中統(tǒng)計(jì)得出，但是問(wèn)題是，如果詞典要記錄任意N個(gè)詞出現(xiàn)時(shí)出現(xiàn)詞W的概率，一個(gè)存放M個(gè)詞匯的詞典需要存放M^N量級(jí)的關(guān)系數(shù)據(jù)，這個(gè)詞典會(huì)太大，所以通常會(huì)限制N的大小，一般來(lái)說(shuō)，N為2或者為3，計(jì)算條件概率時(shí)只考慮到它前面2到3個(gè)詞，這是基于馬爾可夫鏈做的簡(jiǎn)化。當(dāng)N為2時(shí)稱為二元模型，N為3時(shí)稱為三元模型。一個(gè)有50萬(wàn)詞的詞典的二元模型需要50萬(wàn)*50萬(wàn)條關(guān)系，這也是相當(dāng)大的一個(gè)量級(jí)，可以對(duì)其進(jìn)行壓縮或轉(zhuǎn)化為其它近似形式，這部分相對(duì)比較復(fù)雜，在此不作講解，這里使用更簡(jiǎn)單一些的形式，假設(shè)每個(gè)詞的出現(xiàn)都是獨(dú)立事件，令P(大,學(xué),生,活)=P(大)P(學(xué))P(生)P(活)。要計(jì)算這個(gè)概率，只需要知道每個(gè)詞的出現(xiàn)概率，一個(gè)詞的出現(xiàn)概率=詞出現(xiàn)的次數(shù)/文本庫(kù)中詞總量。那么將之前使用的詞典更新為[大學(xué)5、大學(xué)生4、學(xué)習(xí)6、學(xué)習(xí)機(jī)3、學(xué)生5、生氣8、生活7、活著2] 后面的數(shù)字是這些詞在文本庫(kù)中出現(xiàn)的次數(shù)，文本庫(kù)中詞的問(wèn)題就是這些詞出現(xiàn)次數(shù)之和=5+4+6+3+5+8+7+2=40

那么P(大學(xué),生活)=P(大學(xué))P(生活)=5/40*7/40

P(大學(xué)生、活)=P(大學(xué)生)P(活)=4/40*0/40 在這個(gè)地方出現(xiàn)了問(wèn)題，對(duì)于詞典里不存在的詞，它的概率是0，這將會(huì)導(dǎo)致整個(gè)乘積是0，這是不合理的，對(duì)于這種情況可以做平滑處理，簡(jiǎn)單地來(lái)說(shuō)，可以設(shè)詞典中不存在的詞的出現(xiàn)次數(shù)為1，于是P(大學(xué)生、活)=P(大學(xué)生)P(活)=4/40*1/40

最終可以挑選出一條最有可能的分詞組合。至此第三步結(jié)束。

以上就是淺談分詞器Tokenizer的詳細(xì)內(nèi)容，更多關(guān)于分詞器Tokenizer的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論