ML基礎——讓人腦殼疼的中文分詞算法

在前文當中，我們介紹了搜尋引擎的大致原理。有錯過或者不熟悉的同學，可以點擊下方的連結回顧一下前文的內容。

在介紹爬虫部分的時候，我們知道，爬蟲在爬取到網頁的內容之後，會先進行一些處理。首先要做的就是過濾掉HTML當中的各種標籤信息，只保留最原生的網頁內容。之後，程序會對這些文本內容提取關鍵詞。

今天我們就來講講關鍵詞提取當中最重要的一個部分——中文分詞。

在世界上眾多的語言當中，中文算是比較特殊的一種。許多語言自帶分詞信息，比如英文，機器學習寫作machine learning。machine和learning之間自帶一個空格作為分隔。但是中文不是這樣，漢字之間沒有任何分隔符。意味著程序沒有辦法直接對文本進行分割。

那麼我們怎麼知道「機器學習」這四個字應該分割成機器和學習而不是機和器學習或者是機器學和習呢？

這就需要中文分詞算法。

目前常用的分詞算法主要分為兩大類，一種是基於詞表的規則分詞算法。另一種則是在機器學習以及深度學習興起之後流行起來的統計分詞算法。我們先從比較容易理解的規則分詞算法開始講起。

規則分詞算法的核心是詞表，我們維護一個儘可能大的詞表， 當中儘可能多的包含各種中文的詞語。在切分語句的時候，我們將句子當中的每個短語都去詞表當中檢索。如果能夠檢索到，說明這的確是一個詞語，則進行切分，否則則不切分。

這個很好理解對吧，我們繼續往下。

但是我們切分語句的時候，其實有兩種順序，既可以正向切分，也可以反向切分。根據切分方向的不同，產生了兩種比較類似的算法。

  正向最大匹配算法  

正向最大匹配算法的思路非常簡單，我們每次儘量找儘可能長的詞語。假設中文的詞庫當中最長的詞語長度是n個字，那麼我們每次從文本的前n個字開始查找詞表， 如果找到了，那麼顯然這n個字就是一個單獨的單詞。如果沒找到，那麼縮減一位，查找前n-1個字，如此循環往復，直到在詞表當中找到單詞為止。

這時候， 我們從匹配結束的位置繼續往下，一直到整個句子分詞完畢。整個過程非常簡單，理論上來說我們人類閱讀句子的時候，就是按照這個順序。但是這個算法並不是完美的，當中隱藏著問題。

舉個最經典的例子，假設當前的句子是「南京市長江大橋」。假設我們詞庫當中單詞的最長長度是5，那麼我們第一次切分的結果是「南京市長江」，詞表當中並沒有這個詞，於是會切分「南京市長」，詞表當中的確有這個詞，那麼整個句子就會切分成「南京市長」和「江大橋」這兩個部分。如果「江大橋」不被當做人名，那麼會繼續切分成「江」和「大橋」。

這顯然是不對的，會發生這個問題的原因也很簡單，因為中文當中存在歧義。尤其是摻雜人名的時候，因為人名數不勝數，不可能都包容在詞表當中。如果真的包容了，也會很有問題。

  逆向最大匹配算法  

為了解決正向匹配算法當中的問題，人們又想出了逆向最大匹配算法。思路和正向匹配幾乎一模一樣，僅僅將切分的順序從前面開始改成了從後面開始而已。

每次我們獲取句子當中最後n個字，進行詞表匹配。如果沒有匹配中，那麼去掉這n個字當中的第一個字，將後面的n-1個字繼續匹配。直到能匹配上為止。

在實際應用當中，正相匹配的錯誤率約為1/169，而逆向匹配的錯誤率為1/245，顯然逆向匹配要更好一些。這也是有原因的，因為漢語當中偏正短語較多，詞語的重心往往落在後面，比如之前的」南京市長江大橋「如果按照逆向匹配，就很容易識別出」南京市「和」長江大橋「了。

當然和正向匹配一樣，逆向匹配也不是完美的，同樣存在許多反例。

  雙向最大匹配  

雙向最大匹配的原理也很簡單，就是將正向和負向結合起來。互相各取所長，因為這兩種算法的切分思路剛好相反，從邏輯上來看是存在互補的可能的。

實際上也的確如此，根據研究顯示，約有90%的中文句子，正向和逆向的切分結果是完全匹配並且正確的。大約有9%的句子是兩個算法結果不一致，並且是有一種是正確的。只有1%不到的句子，兩個算法的結果都錯誤的。

算法的思路也很簡單，就是將正向匹配和逆向匹配的結果進行對比。如果一致，那麼直接就認為是正確答案，如果不一致，則選擇其中切分出來單詞數量較少的。

比如前文當中」南京市長江大橋「兩種切分結果分別是」南京「，「市長」，「江」，「大橋」和「南京市」，「長江大橋」，那麼算法會選擇後者。

  統計分詞算法  

基於統計的分詞算法也不難理解，我們用統計學中出現的概率來代表分詞方案的正確性。

假設句子是T，一種分詞方案是。那麼

顯然，我們要計算出當中所有的條件概率是不可能的，因為參數空間太大，數據過於稀疏。

不過好在我們可以進行化簡，理論上來說當前句子某個位置會出現什麼單詞，可能和其他所有單詞都有關係。但是我們可以簡化這個關係，我們可以簡單認為每個單詞之和之前出現的兩個詞語有關。

也就是說，

這樣樣本空間大大減少，我們枚舉可能存在的分詞情況，通過統計的方法找到其中出現概率最大的值即可。

  深度學習分詞算法  

在深度學習普及了之後， 市面上出現了許多種基於深度學習的中文分詞算法。本文選擇其中最簡單的一種作為介紹。

目前常用的模型是BiLSTM，即雙向的LSTM模型。LSTM模型的好處是可以學到時間序列的信息，在文本當中，能夠學習到上下文直接詞語的內在聯繫。BiLSTM是雙向LSTM模型，既考慮了句子的正序，也考慮了句子的逆序，有些類似於前文當中說的雙向最大匹配算法。

模型的輸入是一個句子當中所有漢字向量化的集合，有點類似於Word2vec的做法(這裡看不懂的同學可以跳過，後面會有專門介紹Word2vec的文章)，以及每個字的類別。每個字的類別一共有四種，分別是s(single)，即單字成詞，b(begin)，某個詞語的開始，m(middle)，某個詞語的中間部分和e(end)，即每個詞語的結尾。

預測的時候，模型一樣讀入每個字對應的embedding，模型的預測結果是每個字屬於每個類別的概率。最後，根據模型的預測結果，對整個文本完成分詞。和之前幾種算法相比，這種算法的準確率更高，但是它也有自己的問題。最大的問題是非常依賴人工標註的結果，想要模型有好的結果，需要的訓練樣本量非常大，因此帶來的人力成本很高。中文分詞是非常小的一個點，但是卻至關重要，凡事和文本有關的領域都離不開它。好在絕大多數情況下，我們並不需要自己手動實現分詞算法，因為如今市面上已經有了許多免費開源的分詞引擎，像是著名的庖丁、jieba等等。不過儘管如此，深入了解其中的算法原理，依然很有必要。如果覺得文章有所幫助，請轉發或者點擊下方的「在看」，你們的支持是我最好的回報。