中文分詞算法 之 基于詞典的正向最大匹配算法

1、中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川基于詞典的正向最大匹配算法，算法會(huì)根據(jù)詞典文件自動(dòng)調(diào)整最大長(zhǎng)度，分詞的好壞完全取決于詞典。算法流程圖如下：Java實(shí)現(xiàn)代碼如下：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川詞典文件下載地址dic.rar，簡(jiǎn)單吧，呵呵實(shí)現(xiàn)功能是簡(jiǎn)單，不過這里的詞典中詞的數(shù)目為：427452，我們需要頻繁執(zhí)行DIC.contains(tryWord)來判斷一個(gè)詞是否在詞典中，所以優(yōu)化這行代碼能夠顯著提升分詞效率（不要過早優(yōu)化、不要做不成熟的優(yōu)化）。上面的代碼是利用了JDK的Collection接口的co

2、ntains方法來判斷一個(gè)詞是否在詞典中，而這個(gè)方法的不同實(shí)現(xiàn)，其性能差異極大，上面的初始版本是用了ArrayList：List<String> DIC = new ArrayList<>()。那么這個(gè)ArrayList的性能如何呢？還有更好性能的實(shí)現(xiàn)嗎？通常來說，對(duì)于查找算法，在有序列表中查找比在無序列表中查找更快，分區(qū)查找比全局遍歷要快。通過查看ArrayList、LinkedList、HashSet的contains方法的源代碼，發(fā)現(xiàn)ArrayList和LinkedList采用全局遍歷的方式且未利用有序列表的優(yōu)勢(shì)，HashSet使用了分區(qū)查找，如果hash分布均勻

3、沖突少，則需要遍歷的列表就很少甚至不需要。理論歸理論，還是寫個(gè)代碼來測(cè)測(cè)更直觀放心，測(cè)試代碼如下：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川我們發(fā)現(xiàn)HashSet性能最好，比LinkedList和ArrayList快約3個(gè)數(shù)量級(jí)！這個(gè)測(cè)試結(jié)果跟前面的分析一致，LinkedList要比ArrayList慢一些，雖然他們都是全局遍歷，但是LinkedList需要操作下一個(gè)數(shù)據(jù)的引用，所以會(huì)多一些操作，LinkedList因?yàn)樾枰４媲膀?qū)和后繼引用，占用的內(nèi)存也要高一些。雖然HashSet已經(jīng)有不錯(cuò)的性能了，但是如果詞典越來越大，內(nèi)存占用

4、越來越多怎么辦？如果有一個(gè)數(shù)據(jù)結(jié)構(gòu)，有接近HashSet性能的同時(shí)，又能對(duì)詞典的數(shù)據(jù)進(jìn)行壓縮以減少內(nèi)存占用，那就完美了。前綴樹（Trie）有可能可以實(shí)現(xiàn)“魚與熊掌兼得”的好事，自己實(shí)現(xiàn)一個(gè)Trie的數(shù)據(jù)結(jié)構(gòu)，代碼如下：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川修改前面的測(cè)試代碼，把List<String> DIC = new ArrayList<>()改為Trie DIC = new Trie()，使用Trie來做詞典查找，最終的測(cè)試結(jié)果如下：中文分詞算法

5、之 基于詞典的正向最大匹配算法 楊尚川可以發(fā)現(xiàn)Trie和HashSet的性能差異較小，在半個(gè)數(shù)量級(jí)以內(nèi)，通過jvisualvm驚奇地發(fā)現(xiàn)Trie占用的內(nèi)存比HashSet的大約2.6倍，如下圖所示：HashSet:Trie:中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川詞典中詞的數(shù)目為427452，HashSet是基于HashMap實(shí)現(xiàn)的，所以我們看到占內(nèi)存最多的是HashMap$Node、char和String，手動(dòng)執(zhí)行GC多次，這三種類型的實(shí)例數(shù)一直在變化，當(dāng)然都始終大于詞數(shù)427452。Trie是基于ConcurrentHashMap實(shí)現(xiàn)的，所以我們看到占內(nèi)存最多的是Concurr

6、entHashMap、ConcurrentHashMap$Node、ConcurrentHashMap$Node、Trie$TrieNode和Character，手動(dòng)執(zhí)行GC多次，發(fā)現(xiàn)Trie$TrieNode的實(shí)例數(shù)一直保持不變，說明427452個(gè)詞經(jīng)過Trie處理后的節(jié)點(diǎn)數(shù)為603141。很明顯地可以看到，這里Trie的實(shí)現(xiàn)不夠好，選用ConcurrentHashMap占用的內(nèi)存相當(dāng)大，那么我們?nèi)绾蝸砀倪M(jìn)呢？把ConcurrentHashMap替換為HashMap可以嗎？HashSet不是也基于HashMap嗎？看看把ConcurrentHashMap替換為HashMap后的效果，如下圖所

7、示：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川內(nèi)存占用雖然少了10M左右，但仍然是HashSet的約2.4倍，本來是打算使用Trie來節(jié)省內(nèi)存，沒想反正更加占用內(nèi)存了，既然使用HashMap來實(shí)現(xiàn)Trie占用內(nèi)存極高，那么試試使用數(shù)組的方式，如下代碼所示：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川內(nèi)存占用情況如下圖所示：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川現(xiàn)在內(nèi)存占用只有HashSet方式的80%了，內(nèi)存問題總算是解決了，進(jìn)一步分析，如果詞典夠大，詞典中有

8、共同前綴的詞足夠多，節(jié)省的內(nèi)存空間一定非常客觀。那么性能呢？看如下重新測(cè)試的數(shù)據(jù)：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川總結(jié)一下，ArrayList和LinkedList方式實(shí)在太慢，跟最快的HashSet比將近慢約3個(gè)數(shù)量級(jí)，果斷拋棄。Trie比HashSet慢約半個(gè)數(shù)量級(jí)，內(nèi)存占用多約2.6倍，改進(jìn)的TrieV1比Trie稍微節(jié)省一點(diǎn)內(nèi)存約10%，速度差不多。進(jìn)一步改進(jìn)的TrieV2比Trie大大節(jié)省內(nèi)存，只有HashSet的80%，不過速度比HashSet慢約1.5個(gè)數(shù)量級(jí)。TrieV2實(shí)現(xiàn)了節(jié)省內(nèi)存的目標(biāo)，節(jié)省了約70%，但是速度也慢了，慢了約10倍，可以對(duì)TrieV2做

9、進(jìn)一步優(yōu)化，TrieNode的數(shù)組children采用有序數(shù)組，采用二分查找來加速。下面看看TrieV3的實(shí)現(xiàn)：使用了一個(gè)新的方法insert來加入數(shù)組元素，從無到有構(gòu)建有序數(shù)組，把新的元素插入到已有的有序數(shù)組中，insert的代碼如下：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川有了有序數(shù)組，在搜索的時(shí)候就可以利用有序數(shù)組的優(yōu)勢(shì)，重構(gòu)搜索方法getChild：中文分詞算法 之 基于詞典的正向最大匹配算法 楊尚川數(shù)組中的元素是TrieNode，所以需要自定義TrieNode的比較方法：好了，一個(gè)基于有序數(shù)組的二分搜索的性能提升重構(gòu)就完成了，良好的單元測(cè)試是重構(gòu)的安全防護(hù)網(wǎng)，沒有單元測(cè)試的重構(gòu)就猶如高空走鋼索卻沒有防護(hù)墊一樣危險(xiǎn)，同時(shí)，不過早優(yōu)化，不做不成熟的優(yōu)化是我們應(yīng)該謹(jǐn)記的原則，要根據(jù)應(yīng)用的具體場(chǎng)景在算法的時(shí)空中做權(quán)衡。OK，看看TrieV3的性能表現(xiàn)，當(dāng)然了，內(nèi)存使用沒有變