692      小米  小米手環

中文分詞算法

1.1.1

盡管最大匹配法分詞是常用的解決的方案，但是無疑它存在很多明顯的缺陷，這些缺陷也限製了最大匹配法在大型搜索係統中的使用頻率。最大匹配法的問題有以下幾點：

一、長度限製

由於最大匹配法必須首先設定一個匹配詞長的初始值，這個長度限製是最大匹配法在效率與詞長之間的一種妥協。我們來看一下以下兩種情況：

（1）詞長過短，長詞就會被切錯。例如當詞長被設成5時，也就意味著它隻能分出長度為5以下詞，例如當這個詞為“中華人民共和國”長度為7的詞時，我們隻能取出其中的5個字去詞庫裏匹配，例如“中華人民共”，顯然詞庫裏是不可能有這樣的詞存在的。因此我們無法下確的劃分出“中華人民共和國”這樣的詞長大於5的詞。

（2）詞長過長，效率就比較低。也許有人會認為既然5個字無法滿足我們的分詞要求，何不將詞長加大，例如加到10或者100，畢竟這個世界超過100個字長的詞還是很少見的，我們的詞長問題不就解決了？然而當詞長過長時，我們卻要付出另一方麵的代價：效率。效率是分詞算法、甚至是整個算法理論體係的關鍵，畢竟算法書裏所有的高深的查詢或排序算法都是從效率出發的，否則任何笨辦法都可以解決分詞效率低的問題。設想到我們把字長設成100個詞時，我們必須將詞從100開始一直往下匹配直到找到要查的字為止，而我們大多數詞的字長卻隻有兩三個字，這意味著前97次的匹配算法是徒勞的。

因此我們必須要在詞長與效率之間進行妥協，既要求分詞盡量準確，又要求我們的詞長不能太長。盡管我們可能找到這樣一個比較優化的字長值使兩者都達到比較滿足的狀態，但是畢竟不管我們怎麼設定，總會有些太長詞分出來，或者帶來效率問題。

二、效率低

效率低是最大匹配法分詞必然會來的問題。即使我們可以將字長設成相當短，例如5（注意，我們不能再縮短字長了，畢竟字長為5以上的詞太多了，我們不能犧牲分詞的準確），然而當我們的大數詞長為2時，至少有3次的匹配算法是浪費掉的。回想一下算法書裏提到的最簡單的字符匹配與KMP算法之間天差地別的效率，我們知道通過某種方法，這些浪費的掉的匹配時間是可以補回來的。

三、掩蓋分詞歧義

中文是如此複雜的語言，它的表達方式如此之多，語法文法如此精妙，機械的電腦是很難理解這麼複雜的語言，因此它必然會帶來歧意性，以下是兩個簡單的例子：

A.“有意見分歧” （正向最大匹配和逆向最大匹配結果不同）
有意/ 見/ 分歧/

有/ 意見/ 分歧/
B.“結合成分子時” （正向最大匹配和逆向最大匹配結果相同）
結合/ 成分/ 子時/由於詞的歧義性使我們在使用最大匹配法分詞會產生錯誤的結果，而且使用正向分詞與逆向分詞往往會產生截然不同的結果。盡管使用回溯法或計算計算詞的使用頻率，可以使出現歧義的可能性減少，但是我們知道，這樣的結果是不可避免的，因為中文的變化實在太多了。

四、最大匹配的並不一定是想要的分詞方式

最大匹配法基於的理念是找到最大的匹配詞，但有的時候除了最大匹配詞外，我們也可能隻需要這個詞的一部分。例如“感冒解毒膠囊”是一個完整的詞，按照最大匹配法我們無法對它進行拆分了，這樣我們輸入“感冒”的時候就根本搜不到我們需要的詞。這是我們需要的嗎？做為生產這種藥的廠商，它肯定希望用戶輸入“感冒”甚至“解毒”，我們都能查到對應的內容。

1.2

1.2.1

基於對分詞算法的理解和對最大匹配法分詞的分析，我們知道我們必須提出不同的解決方案，使分詞算法的效率、分詞的長度限製甚至歧義處理上得到提高。因此我們提出了如下的設計目標：

一、 高效

中文分詞算法必須要高效，畢竟效率對於搜索引擎的重要性是不言而喻的。而且我們麵對的是海量的數據，而不是一篇幾百字或幾千字的文章，效率的差別的影響可能會使最後運行效率差幾個小時甚至幾天。因此我希望我們設計的算法一定要比最大匹配法高，畢竟我們已經常看到最大匹配法的很多次匹配都是浪費在無用功上了，肯定有辦法把這些浪費的時間節省回來。

二、無長度限製

最大匹配法的長度限製真是很討厭的事，我們很難找到詞長與效率的之間的平衡。為什麼我們需要長度的限製？為什麼我們不能設計出任何詞長的詞（隻要詞庫中存在）都可以分出來？

三、歧義包容

我們相信長度限製的問題總是可以解決的，因為雖然長度限製這個問題很難，但是它是有規律可循的，它是嚴謹的科學。但是當我們碰到中文歧義時，我知道不管我們怎麼努力，它仍然是不可能徹底解決的。因為中文實在太博大精深了，即使有極強的人工智能和機器學習功能，這樣的錯誤仍然是難以避免。既然無法避免？我們為什麼不換一個角度去考慮？我們為什麼不可以將出現歧義的各種可能性都包含進去，作為分詞的參考。例如上述的“有意見分歧”的兩種分詞方法：

有意/ 見/ 分歧/

有/ 意見/ 分歧/

為什麼我們不能把這樣兩種結果都拿來分詞呢？畢竟分詞的目的是為了搜索，而不是為了教小孩讀出。如果把兩種分詞的可能性都告訴搜索引擎，搜索引擎會很高興的，因為這下不管是“有意”還是“意見”，它都可以搜到了。這就是我提出來另一個目標：歧義包容。

1.2.2 —

雖然我們的目標已經確定下來了，但是要想出一個更好的算法卻是非常難的事。畢竟算法需要的是靈感與突發奇想，這與係統的架構設計和麵向對象的設計與編者編碼剛好是相反的，象設計模式或重構這樣的東西我們需要的實踐、總結、再實踐。而算法需要的卻是當我們在山重水複疑無路的時候會換個角度思考。

但是分詞算法的突破口在哪裏呢？我們必須要有一個詞庫，我們必須將全文中的詞與詞庫去匹配，這一切都是不可避免的。

真正要改善是就是我們的匹配過程，我們要減少匹配過程中的浪費，我們要解決匹配中的詞長限製。但是我們有什麼辦法呢？每次的匹配我們必須要去詞庫中查找一次。怎麼改善這樣的做法？

我們總是把優化的思路定格在更好的匹配算法，更好地處理詞條和全文。但是真正束縛我們的卻是詞庫！是基於關係數據庫的詞庫，我們需要的對詞庫的改造，我們要讓我們的詞庫更適合用於匹配與分詞！

這是幾十年來關係數據庫帶給我們的思維：我們查找的詞是數據庫的某條記錄，通過表格與關係代數，我們總能找到這個詞。但是正是關係數據庫的這種思維束縛著我們，關係數據庫讓我們的數據結構及關聯表達得清楚又簡單，並使某些查詢的效率變得很高。但是這不適用於中文分詞，有的時候退到幾十年前流行的數據庫模型也許更適合。這就是層次數據庫。

我們要做的是將關係數據庫的詞按字打散，並存放到層次數據庫中。以下就是一個示例：

紅色的字表示樹上麵的字串是可以單獨組成一個詞的，例如“感冒”它本身是詞庫裏可以找到的詞，所有紅色的表示的是終止符。而黃色則表示樹上麵的字串是無法單獨成詞的，例如“感冒解”是不存在的詞。

真的很奇妙，詞庫經過這樣的改裝後，所有的匹配的思維都變掉了。任何一個句子都會打散成單字去與樹狀結構的單字去匹配，詞的長度變成了樹的高度，每一次的匹配變成了樹的遍曆，而這種遍曆的效率竟然都是線性的！

1.2.3

有了以上的中文詞庫後，我們分詞算法設計就水到渠成的。首先我們來看一下分詞的步驟：

（1）首先將要分的全文按標點符號打散成一個一個的句子。這算是預處理的一個步驟，目的是讓我們處理的句子短，效率更高。畢竟中間有標點符號的詞是不存在的。（注：真正實現時我們是基於lucene的SimpleAnalyzer來做的，因為SimpleAnalyzer本身就是為了將全文打散成句子，因此我們沒必要耗費體力去實現這一步）。

（2）我們開始將要處理的句子在樹狀結構中遍曆，如果找到匹配的就繼續，如果遇到紅色的終止符，我們就發現這個詞是一個完整的詞了，這樣我們就可以把這個詞作為一個一個分詞了。

（3）從分詞後的下一字開始繼續做步驟2這樣的遍曆，如此循環往複就將詞分完了。

可以看到，我們字符匹配效率幾乎是線性的！我們所要做的隻是取出每一個字去樹上找到相應的匹配，每次的匹配代價都是O(1)（如果詞庫用Hash表的話），這樣匹配下來的時間複雜度就是字符串本身的長度！對於一個長度為n的字符串來說，它的分詞複雜度是O(n)。而最大匹配的平均複雜度是O(n²)。

當然我們這裏沒有考慮歧義包容與分支處理等情況，但即使加上這些我們複雜度仍然是有限的。

1.2.4

一、建立詞庫

有了改裝詞庫的基本思想後，建立詞庫的步驟變得很簡單，但是仍然會有好多的細節需要注意。

首先是詞庫的保存格式。現在最常用的保存數據的方式當然是關係數據庫，其次是文件係統中的二進製文件。顯然關係數據庫對於我們並不適用，而自定義的二進製文件則實現起來比較困難，而且讀寫的效率也會有問題。因為我們想到了最簡單的方法是利用java的serialization的功能，把整個內存中的樹狀結構直接序列化成磁盤的文本文件是最方便的！而且讀寫的效率也會相當的高。

第二個問題是樹的父子節點的導航。我們的樹並不是一顆二叉樹，父親的子節點會有好多！尤其是第一層，我們會把詞庫中所有的首字都取出來作為根節點的子節點，這意味著如果首字有4000個的話，根節點就有4000個兒子。當然隨著樹層數的增多，節點的兒子數也會減少，畢竟以“感冒”開頭的詞在整個詞庫也隻有四十多個，而以“感冒清”開頭的詞則隻有兩三個了。這意味著如果設計得不合理，我們樹的匹配遍曆過程並不完全是線性的。最壞的查找算法是O(N)（N代表兒子數）。當然如果我們建詞庫時將兒子有序排列，再按照二分查找的方法，則我們的複雜度會減到O(lgN)，這樣的複雜度已經可以接受了。但是還有更簡單又更快的存儲方式，為什麼不使用呢？那就是HashMap，畢竟在HashMap裏查找東西時它的效率幾乎是線性的，而且實現起來要比二分查詢簡單得多。當然用HashMap要付出存儲空間變大的代價，但這樣的代價來換取速度與簡單性也是的。

第三個問題是找到有終結符的字後，我們必須要將它建成一個完整的詞。這時我們必須能從字個往上回溯，直到找到根結點。因此我們在每個節點裏都保存了父節點的指針。

有了以上的設計思想，我們就動手建立了我們的詞庫，詞庫的來源是中醫藥數據庫的詞匯表，因為我們應用一直是圍繞中醫藥的。我們找到了兩個最重要的表，這兩個表幾乎包含了中醫藥的全部詞庫：

一體化語言係統詞庫 92112個詞

疾病大全、症狀、證候 20879個詞

最後生成的詞庫是java serialization的一個文件，文件的大小是16M 。當然這跟我們采用HashMap存放父子關聯有關，也跟java的對象所占空間有關，雖然將詞庫按這種方式存放實際上也對詞庫進行了壓縮（以“感”開頭的字有數十個，關係數據庫裏就要保存數十個，但我們在詞庫隻保存了一個“感”）。但文件仍然偏大，因此用oracle將這兩個表導出後生成的文件大小是4M。不過這個大小仍然是可以接受的，畢竟效率才是關鍵。

二、 分詞查詢

雖然剛才對分詞算法進行了描述，但實際上實現的時候我們還會碰到很多問題。

1、分支處理。

這是分詞算法時歧義包容所必然碰到的問題。為了歧義包容，我們采用了與最大分詞法完全不同的理念，我們的理念是將詞庫中存在詞全部收入囊中！而且會發生重疊。例如“感冒解毒膠囊”，由於詞庫裏存在“感冒”、“解毒”和“感冒解毒膠囊”這三個詞，因此在分詞的時候，我們會分別分出這三個詞，這樣用戶無論輸入“感冒”、“解毒”或“感冒解毒膠囊”搜索引擎都會找到相應的結果。

因此當遇到分支時，我們會分解成兩條路線！例如當我們匹配到“感冒”的“冒”時，我們會發現一個終止符，代表“感冒”是一個完整的字，將它收錄到分詞中。接下來我們會分成兩支，一支是繼續往下走，匹配樹的下一層，因為“冒”不是樹的葉子，往下走可能會碰到更大的匹配詞，例如“感冒解毒膠囊”。而另一支則從根開始，直接用“解”去匹配樹的第一層節點，最後發現了“解毒”也是其中的一個詞。

2、動態規劃法

分支雖然使我們可以消除很多的歧義，但是顯然它會帶來副作用：導致分詞的複雜度變大。如果一個句子很長時，分詞的變化也許會呈指數級的增長，從一開始的兩個分支變成四個、八個甚至更多。我們會發現很多句子雖然會有很多分支，但是這些分支又經常會匯聚到一個點，變成一個分支。例如：“感冒解毒膠囊可以治感冒”，我們在分詞的時候可能會出現“感冒”，“解毒”，“感冒解毒”，“感冒解毒膠囊”等多個分支，但是當我們到達“囊”這個點的時候，所有的分支又會匯集到一起，因為大家接下來要處理的都是“可以治感冒”這個字符串。如果有辦法讓我們在匯聚以後隻處理一個分支，那麼算法的時間複雜度就不會象原來想象的那麼壞。

而這剛好是動態規劃法發揮威力的時候，動態規劃要解決的問題是Overlapping sub-problem。它的處理方法就是將所有的子問題記錄在公有的變量裏（這裏指的是類變量，它相對於某個method來說是公有變量，而不是真的全局變量）。當我遇到的子問題已經被處理過一次了，就直接跳過。這樣節約的結果可以使算法複雜度得到質的改變，當然由於中文的變化多端，我們無法精確估計使用動態規劃法後算法複雜度得到了多大的提高。

實際上的動態規劃法的實現起來比說起來反而簡單，我們隻是簡單地放了一個HashSet來存放已經分詞過的位置：

然後判斷的函數也相當的簡單：

最後在分詞的遞歸函數中加入這一句判斷：

當這個位置已經被處理過了就直接返回了。

3、詞庫預load

在使用基於詞庫的方法時，我們必須要麵臨的一個問題是：必要將詞庫讀到內存中，而這通常會耗費很長的時間，幸運的是這樣的工作我們隻需要做一次，當我們將詞庫load進來以後，所有的工作都會在內存中進行，分詞的速度會得到極速提升。我們選擇的詞庫預load時機是我們第一次進行分詞時，這相當於lazy load，隻有用到的時候我們才去初始化。

講完算法，我們來看看分詞部分的實現代碼，實際上這部分的內容實現起來遠比想中簡單。在處理的過程中，我們對給每個句子（實際是lucene裏用SimpleAnalyzer分詞後的一個個Token）都新建一個ChineseSplitter，這是更加麵向對象的做法，使我們處理起來更加方便簡潔，因為我們會發現如果用一個Singleton的ChineseSplitter時，它的變量無法共享會導致整個Splitter裏的遞歸方法跟上一堆的參數，容易出錯，而且無法調試。代碼如下：

代碼簡單明了，隻是做了詞庫預load的工作後就將實際的分詞工作交給了ChineseSplitter。

ChineseSplitter的核心功能實際上將句子中詞典中能找到的詞放到一個隊列中，這中隊列裏提供了分詞以後的所有詞的信息：

下麵是分詞的核心算法：

它是一個遞歸的過程，初始時我們調用的參數裏pos為0，這樣它就會一級一級遞歸下去並將所有可能的分詞放入到tokenQueue裏。

1.2.5

1、實驗1——短文分詞

在第一個實驗中我們選了一篇2000字的文章（是關於中醫藥的專業論文）。然後用三種Analyzer對它進行處理，以下是實驗結果：

我們沒有找到最大匹配法分詞可用的開源代碼，因此隻能用SimpleAnalyzer和StandardAnalyzer與之比較。這兩種算法事實上是根本沒有去查詞庫的，因此也不會按任何語義去分詞，SimpleAnalyzer隻是簡單地將文章按標點符號隔開成句子，而StandardAnalyzer則隻是簡單地將文章的中文字分成一個一個的單字。結果確實讓人驚訝，當詞庫preload以後，我們的分詞速度竟然遠超不需要查任何詞庫的StandardAnalyzer算法！

2、實驗2——建索引

這是將分詞算法應用到我們的索引係統後的效果比較，我們的數據源是來自中醫藥數據庫的幾十張表，一共有九十萬條記錄：

由於建索引時數據庫的查詢操作會耗費很多的時間，因此兩者的差別不是太明顯，但結果至少說明了我們的分詞效率確實是很高。

最後更新：2017-04-02 00:06:28

  上一篇： [.NET 基於角色安全性驗證] 之五：跨應用程序進行 Forms 身份驗證

  下一篇： “多態”一個需要注意的問題