中文分詞一直都是中文自然語言處理領(lǐng)域的基礎(chǔ)研究。目前，網(wǎng)絡(luò)上流行的很多中文分詞軟件都可以在付出較少的代價的同時，具備較高的正確率。而且不少中文分詞軟件支持Lucene擴(kuò)展。但不管實(shí)現(xiàn)如何，目前而言的分詞系統(tǒng)絕大多數(shù)都是基于中文詞典的匹配算法。

?

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

?

● 算法思想

?

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

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

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

(1) 從content[1]開始，當(dāng)掃描到content[2]的時候，發(fā)現(xiàn)"中華"已經(jīng)在詞表dict[]中了。但還不能切分出來，因?yàn)槲覀儾恢篮竺娴脑~語能不能組成更長的詞(最大匹配)。

(2) 繼續(xù)掃描content[3]，發(fā)現(xiàn)"中華民"并不是dict[]中的詞。但是我們還不能確定是否前面找到的"中華"已經(jīng)是最大的詞了。因?yàn)?中華民"是dict[2]的前綴。

(3) 掃描content[4]，發(fā)現(xiàn)"中華民族"是dict[]中的詞。繼續(xù)掃描下去：

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

?

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

?

?

● 算法實(shí)現(xiàn)

?

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

?

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

??????????

(1) 每個結(jié)點(diǎn)都是詞語中的一個漢字。

(2) 結(jié)點(diǎn)中的指針指向了該漢字在某一個詞中的下一個漢字。這些指針存放在以漢字為key的hash結(jié)構(gòu)中。

(3) 結(jié)點(diǎn)中的"#"表示當(dāng)前結(jié)點(diǎn)中的漢字是從根結(jié)點(diǎn)到該漢字結(jié)點(diǎn)所組成的詞的最后一個字。

?

TrieNode源代碼如下：

    import java.util.HashMap;
/**
 * 構(gòu)建內(nèi)存詞典的Trie樹結(jié)點(diǎn)
 * 
 * @author single(宋樂)
 * @version 1.01, 10/11/2009
 */
public class TrieNode {

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

  

?

這套分詞代碼的優(yōu)點(diǎn)是：

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

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

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

?

缺點(diǎn)也很明顯：

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

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

?

代碼的進(jìn)一步優(yōu)化方案：

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

?

????? 但目前還沒有想到很好的辦法，即能夠隨機(jī)定位到下一個結(jié)點(diǎn)的指針，又降低Hash結(jié)構(gòu)的空間代價？

?

?

下面是我實(shí)現(xiàn)的基于Trie詞典結(jié)構(gòu)的正向最大匹配算法的源代碼包和分詞詞表，可供大家學(xué)習(xí)下載。但絕對不允許任何商業(yè)性質(zhì)的傳播，違者必究。

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