文档章节

中文分词算法 之 词典机制性能优化与测试

杨尚川
 杨尚川
发布于 2014/03/28 21:42
字数 916
阅读 1139
收藏 10

在之前的两篇博文中文分词算法 之 基于词典的正向最大匹配算法中文分词算法 之 基于词典的逆向最大匹配算法中,我们对分词实现词典实现都做了优化,本文对词典实现做进一步优化,并和之前的多个实现做一个对比,使用的词典下载地址,使用的测试文本下载地址

 

优化TrieV3的关键在于把虚拟根节点(/)的子节点(词表首字母)提升为多个相互独立的根节点,并对这些根节点建立索引。优化的依据是根节点(词表首字母)的数量庞大,索引查找的速度远远超过二分查找

 

下面看看进一步优化后的TrieV4和之前的TrieV3的对比:



    /**
     * 获取字符对应的根节点
     * 如果节点不存在
     * 则增加根节点后返回新增的节点
     * @param character 字符
     * @return 字符对应的根节点
     */
    private TrieNode getRootNodeIfNotExistThenCreate(char character){
        TrieNode trieNode = getRootNode(character);
        if(trieNode == null){
            trieNode = new TrieNode(character);
            addRootNode(trieNode);
        }
        return trieNode;
    }
    /**
     * 新增一个根节点
     * @param rootNode 根节点
     */
    private void addRootNode(TrieNode rootNode){
        //计算节点的存储索引
        int index = rootNode.getCharacter()%INDEX_LENGTH;
        //检查索引是否和其他节点冲突
        TrieNode existTrieNode = ROOT_NODES_INDEX[index];
        if(existTrieNode != null){
            //有冲突,将冲突节点附加到当前节点之后
            rootNode.setSibling(existTrieNode);
        }
        //新增的节点总是在最前
        ROOT_NODES_INDEX[index] = rootNode;
    }
    /**
     * 获取字符对应的根节点
     * 如果不存在,则返回NULL
     * @param character 字符
     * @return 字符对应的根节点
     */
    private TrieNode getRootNode(char character){
        //计算节点的存储索引
        int index = character%INDEX_LENGTH;
        TrieNode trieNode = ROOT_NODES_INDEX[index];
        while(trieNode != null && character != trieNode.getCharacter()){
            //如果节点和其他节点冲突,则需要链式查找
            trieNode = trieNode.getSibling();
        }
        return trieNode;
    }

 

 不同的字符可能会映射到同一个数组索引(映射冲突),所以需要给TrieNode增加一个引用sibling,当冲突发生的时候,可利用该引用将多个冲突元素链接起来,这样,在一个数组索引中就能存储多个TrieNode。如果冲突大量发生,不但会浪费已经分配的数组空间,而且会引起查找性能的下降,好在这里根节点的每个字符都不一样,冲突发生的情况非常少。我们看看词数目为427451的词典文件的冲突情况:

 

冲突次数为:1 的元素个数:2746
冲突次数为:2 的元素个数:1
冲突次数:2748
总槽数:12000
用槽数:9024
使用率:75.2%
剩槽数:2976

 

 

 



 


 

将词典文件和测试文本解压到当前目录下,使用下面的命令进行测试需要注意的是,这里的-Xmx参数指定的值是相应的词典实现所需要的最小的堆空间,如果再小就无法完成分词

 

nohup java -Ddic.class=org.apdplat.word.dictionary.impl.TrieV4 -Xmx40m  -cp target/word-1.0.jar org.apdplat.word.SegFile &
nohup java -Ddic.class=org.apdplat.word.dictionary.impl.TrieV3 -Xmx40m  -cp target/word-1.0.jar org.apdplat.word.SegFile &
nohup java -Ddic.class=org.apdplat.word.dictionary.impl.TrieV2 -Xmx40m  -cp target/word-1.0.jar org.apdplat.word.SegFile &
nohup java -Ddic.class=org.apdplat.word.dictionary.impl.TrieV1 -Xmx120m  -cp target/word-1.0.jar org.apdplat.word.SegFile &
nohup java -Ddic.class=org.apdplat.word.dictionary.impl.Trie -Xmx200m  -cp target/word-1.0.jar org.apdplat.word.SegFile &
nohup java -Ddic.class=org.apdplat.word.dictionary.impl.HashSet -Xmx50m  -cp target/word-1.0.jar org.apdplat.word.SegFile &

 

测试结果如下:



 



 



 


 

 

代码托管于GITHUB

 

参考资料:

1、中文分词十年回顾

2、中文信息处理中的分词问题

3、汉语自动分词词典机制的实验研究

4、由字构词_中文分词新方法

5、汉语自动分词研究评述

 

NUTCH/HADOOP视频教程

© 著作权归作者所有

杨尚川

杨尚川

粉丝 1101
博文 220
码字总数 1624053
作品 12
东城
架构师
私信 提问
Java中文分词组件 - word分词

Java分布式中文分词组件 - word分词 word分词是一个Java实现的分布式的中文分词组件,提供了多种基于词典的分词算法,并利用ngram模型来消除歧义。能准确识别英文、数字,以及日期、时间等数...

杨尚川
2014/04/29
24.9K
56
中文分词算法 之 基于词典的逆向最大匹配算法

在之前的博文中介绍了基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法,并做了3次优化。 下面我们看看基于词...

杨尚川
2014/03/21
757
1
中文分词算法 之 基于词典的正向最大匹配算法

基于词典的正向最大匹配算法(最长词优先匹配),算法会根据词典文件自动调整最大长度,分词的好坏完全取决于词典。 算法流程图如下: Java实现代码如下: /** * 基于词典的正向最大匹配算法...

杨尚川
2014/03/18
1K
20
中文分词--Ansj

Ansj中文分词 这是一个ictclas的java实现.基本上重写了所有的数据结构和算法.词典是用的开源版的ictclas所提供的.并且进行了部分的人工优化 内存中中文分词每秒钟大约100万字(速度上已经超越...

ansj
2012/09/06
35.5K
2
中文分词库--IKAnalyzer

IK Analyzer 是一个开源的,基于java语言开发的轻量级的中文分词工具包。从2006年12月推出1.0版开始, IKAnalyzer已经推出了4个大版本。最初,它是以开源项目Luence为应用主体的,结合词典分...

林良益
2008/12/03
161.8K
16

没有更多内容

加载失败,请刷新页面

加载更多

Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
50分钟前
4
0
PyTorch入门笔记一

张量 引入pytorch,生成一个随机的5x3张量 >>> from __future__ import print_function>>> import torch>>> x = torch.rand(5, 3)>>> print(x)tensor([[0.5555, 0.7301, 0.5655],......

仪山湖
今天
5
0
OSChina 周二乱弹 —— 开发语言和语言开发的能一样么

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌:#今日歌曲推荐# 分享The Score的单曲《Revolution》 《Revolution》- The Score 手机党少年们想听歌,请使劲儿戳(这里) @批判派...

小小编辑
今天
2.6K
19
oracle ORA-39700: database must be opened with UPGRADE option

ORA-01092: ORACLE instance terminated. Disconnection forced ORA-00704: bootstrap process failure ORA-39700: database must be opened with UPGRADE option 进程 ID: 3650 会话 ID: 29......

Tank_shu
今天
3
0
分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部