中文分詞一直都是中文自然語言處理領域的基礎研究。目前，網絡上流行的很多中文分詞軟件都可以在付出較少的代價的同時，具備較高的正確率。而且不少中文分詞軟件支持Lucene擴展。但不管實現如何，目前而言的分詞系統絕大多數都是基于中文詞典的匹配算法。

?

在這里我想介紹一下中文分詞的一個最基礎算法： 最大匹配算法 (Maximum Matching，以下簡稱MM算法) 。MM算法有兩種：一種正向最大匹配，一種逆向最大匹配。

?

● 算法思想

?

正向最大匹配算法：從左到右將待分詞文本中的幾個連續字符與詞表匹配，如果匹配上，則切分出一個詞。但這里有一個問題：要做到最大匹配，并不是第一次匹配到就可以切分的 。我們來舉個例子：

?????????? 待分詞文本：?? content[]={"中"，"華"，"民"，"族"，"從"，"此"，"站"，"起"，"來"，"了"，"。"}

?????????? 詞表：?? dict[]={"中華"， "中華民族" ， "從此"，"站起來"}

(1) 從content[1]開始，當掃描到content[2]的時候，發現"中華"已經在詞表dict[]中了。但還不能切分出來，因為我們不知道后面的詞語能不能組成更長的詞(最大匹配)。

(2) 繼續掃描content[3]，發現"中華民"并不是dict[]中的詞。但是我們還不能確定是否前面找到的"中華"已經是最大的詞了。因為"中華民"是dict[2]的前綴。

(3) 掃描content[4]，發現"中華民族"是dict[]中的詞。繼續掃描下去：

(4) 當掃描content[5]的時候，發現"中華民族從"并不是詞表中的詞，也不是詞的前綴。因此可以切分出前面最大的詞——"中華民族"。

?

由此可見，最大匹配出的詞必須保證下一個掃描不是詞表中的詞或詞的前綴才可以結束。

?

?

● 算法實現

?

詞表的內存表示： 很顯然，匹配過程中是需要找詞前綴的，因此我們不能將詞表簡單的存儲為Hash結構。在這里我們考慮一種高效的字符串前綴處理結構——Trie樹《 Trie Tree 串集合查找 》。這種結構使得查找每一個詞的時間復雜度為O(word.length)，而且可以很方便的判斷是否匹配成功或匹配到了字符串的前綴。

?

下圖是我們建立的Trie結構詞典的部分，(詞語例子："中華"，"中華名族"，"中間"，"感召"，"感召力"，"感受")。

??????????

(1) 每個結點都是詞語中的一個漢字。

(2) 結點中的指針指向了該漢字在某一個詞中的下一個漢字。這些指針存放在以漢字為key的hash結構中。

(3) 結點中的"#"表示當前結點中的漢字是從根結點到該漢字結點所組成的詞的最后一個字。

?

TrieNode源代碼如下：

    import java.util.HashMap;
/**
 * 構建內存詞典的Trie樹結點
 * 
 * @author single(宋樂)
 * @version 1.01, 10/11/2009
 */
public class TrieNode {

	/**結點關鍵字，其值為中文詞中的一個字*/
	public char key=(char)0;
	/**如果該字在詞語的末尾，則bound=true*/
	public boolean bound=false;
	/**指向下一個結點的指針結構，用來存放當前字在詞中的下一個字的位置*/
	public HashMap<Character,TrieNode> childs=new HashMap<Character,TrieNode>();
	
	public TrieNode(){
	}
	
	public TrieNode(char k){
		this.key=k;
	}
}

  

?

這套分詞代碼的優點是：

(1) 分詞效率高。純內存分詞速度大約240.6ms/M，算上IO讀取時間平均1.6s/M。測試環境：Pentium(R)? 4 CPU? 3.06GHZ、1G內存。

(2) 傳統的最大匹配算法需要實現確定一個切分的最大長度maxLen。如果maxLen過大，則大大影響分詞效率。而且超過maxLen的詞語將無法分出來。但本算法不需要設置maxLen。只要詞表中有的詞，不管多長，都能夠切分。

(3) 對非漢字的未登錄詞具備一定的切分能力。比如英文單詞[happy, steven]，產品型號[Nokia-7320]，網址[http://www.sina.com]等。

?

缺點也很明顯：

(1) 暫時無詞性標注功能，對中文漢字的未登錄詞無法識別，比如某個人名。

(2) 內存占用稍大，目前詞表為86725個詞。如果繼續擴展詞表，很有可能內存Trie樹將非常龐大。

?

代碼的進一步優化方案：

(1) 想在內存占用空間上降低代價。實際上Trie樹主要的空間消耗在每個結點的指針HashMap上。 我使用的是JDK中的HashMap，其加載因子為 loadFactor= 0.75，初始化空間大小為DEFAULT_INITIAL_CAPACITY= 16。每次存儲數據量超過 loadFactor* DEFAULT_INITIAL_CAPACITY的時候，整個Map空間將翻倍。 因此會照成一定的空間浪費。

?

????? 但目前還沒有想到很好的辦法，即能夠隨機定位到下一個結點的指針，又降低Hash結構的空間代價？

?

?

下面是我實現的基于Trie詞典結構的正向最大匹配算法的源代碼包和分詞詞表，可供大家學習下載。但絕對不允許任何商業性質的傳播，違者必究。

【分詞】正向最大匹配中文分詞算法