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

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

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

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

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

6、entHashMap、ConcurrentHashMap$Node、ConcurrentHashMap$Node、Trie$TrieNode和Character，手動執行GC多次，發現Trie$TrieNode的實例數一直保持不變，說明427452個詞經過Trie處理后的節點數為603141。很明顯地可以看到，這里Trie的實現不夠好，選用ConcurrentHashMap占用的內存相當大，那么我們如何來改進呢？把ConcurrentHashMap替換為HashMap可以嗎？HashSet不是也基于HashMap嗎？看看把ConcurrentHashMap替換為HashMap后的效果，如下圖所

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

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

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