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

中文分词算法之基于词典的正向最大匹配算法杨尚川基于词典的正向最大匹配算法,算法会根据词典文件自动调整最大长度,分词的好坏完全取决于词典。算法流程图如下:Java实现代码如下:,简单吧,呵呵实现功能是简单,不过这里的词典中词的数目为:427452,(tryWord))来判断一个词是否在词典中,所以优化这行代码能够显著提升分词效率(不要过早优化、不要做不成熟的优化)。上面的代码是利用了JDK的Collection接口的contains方法来判断一个词是否在词典中,而这个方法的不同实现,其性能差异极大,上面的初始版本是用了ArrayList:List<String>DIC=newArrayList<>()。那么这个ArrayList的性能如何呢?还有更好性能的实现吗?通常来说,对于查找算法,在有序列表中查找比在无序列表中查找更快,分区查找比全局遍历要快。通过查看ArrayList、LinkedList、HashSet的contains方法的源代码,发现ArrayList和LinkedList采用全局遍历的方式且未利用有序列表的优势,HashSet使用了分区查找,如果hash分布均匀冲突少,则需要遍历的列表就很少甚至不需要。理论归理论,还是写个代码来测测更直观放心,测试代码如下:中文分词算法之基于词典的正向最大匹配算法杨尚川中文分词算法之基于词典的正向最大匹配算法杨尚川我们发现HashSet性能最好,比LinkedList和ArrayList快约3个数量级!这个测试结果跟前面的分析一致,LinkedList要比ArrayList慢一些,虽然他们都是全局遍历,但是LinkedList需要操作下一个数据的引用,所以会多一些操作,LinkedList因为需要保存前驱和后继引用,占用的内存也要高一些。虽然HashSet已经有不错的性能了,但是如果词典越来越大,内存占用越来越多怎么办?如果有一个数据结构,有接近HashSet性能的同时,又能对词典的数据进行压缩以减少内存占用,那就完美了。前缀树(Trie)有可能可以实现“鱼与熊掌兼得”的好事,自己实现一个Trie的数据结构,代码如下:中文分词算法之基于词典的正向最大匹配算法杨尚川修改前面的测试代码,把List<String>DIC=newArrayList<>()改为TrieDIC=newTrie(),使用Trie来做词典查找,最终的测试结果如下:中文分词算法之基于词典的正向最大匹配算法杨尚川可以发现Trie和HashSet的性能差异较小,在半个数量级以内,,如下图所示:HashSet:Trie:中文分词算法之基于词典的正向最大匹配算法杨尚川词典中词的数目为427452,HashSet是基于HashMap实现的,所以我们看到占内存最多的是HashMap$Node、char[]和String,手动执行GC多次,这三种类型的实例数一直在变化,当然都始终大于词数427452。Trie是基于ConcurrentHashMap实现的,所以我们看到占内存最多的是ConcurrentHashMap、ConcurrentHashMap$Node[]、ConcurrentHashMap$Node、Trie$TrieNode和Character,手动执行GC多次,发现Trie$TrieNode的实例数一直保持不变,说明427452个词经过Trie处理后的节点数为603141。很明显地可以看到,这里Trie的实现不够好,选用ConcurrentHashMap占用的内存相当大,那么我们如何来改进呢?把ConcurrentHashMap替换为HashMap可以吗?HashSet不是也基于HashMap吗?看看把ConcurrentHashMap替换为HashMap后的效果,如下图所示:中文分词算法之基于词典的正向最大匹配算法杨尚川内存占用虽然少了10M左右,,本来是打算使用Trie来节省内存,没想反正更加占用内存了,既然使用HashMap来实现Trie占用内存极高,那么试试使用数组的方式,如下代码所示:中文分词算法之基于词典的正向最大匹配算法杨尚川