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

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的性能表现，当然了，内存使用没有变