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

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

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

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

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

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

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

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

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

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