一、概述

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

對“大學(xué)生活”這句話做分詞，通常來說，一個分詞器會分三步來實現(xiàn)：

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

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

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

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

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

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

[大學(xué)、生活]

[大學(xué)生、活]

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

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

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í)行這段代碼會輸出：

大學(xué)

大學(xué)生

學(xué)生

生活

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

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

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

2.1、字典樹(trie樹)

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

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

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

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

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

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

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

2.2、失敗指針

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

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

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

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

2.BFS每一個節(jié)點(不能使用DFS，因為每一層節(jié)點的失敗指針在創(chuàng)建時要確保上一層節(jié)點的失敗指針全部創(chuàng)建完成)。

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

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

查詢過程如下：

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

大學(xué)

大學(xué)生

學(xué)生

生活

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

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

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

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

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

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

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

最新評論