在之前的两篇博文中文分词算法 之 基于词典的正向最大匹配算法和中文分词算法 之 基于词典的逆向最大匹配算法中,我们对分词实现和词典实现都做了优化,本文对词典实现做进一步优化,并和之前的多个实现做一个对比,使用的词典下载地址,使用的测试文本下载地址。
优化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 &
测试结果如下:
参考资料:
1、中文分词十年回顾
相关推荐
3、中文分词算法 之 词典机制性能优化与测试 4、中文分词算法 之 基于词典的正向最小匹配算法 5、中文分词算法 之 基于词典的逆向最小匹配算法 5、Java开源项目cws_evaluation:中文分词器分词效果评估
最近在研究中文分词,非常好用的论文,很详细,透彻。免费供给大家。
但不管实现如何,目前而言的分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本...
:分析了中文分词词典的机制,提出了一种改进的整词分词字典结构,并针对机械分词算法的特点,将其与概率算法相结 合,探讨了一种中文自动分词概率算法。采用哈希及二分法对词典进行分词匹配。实验表明,该算法具有...
结合当前中文分词技术在中丈信息处理等领域的广泛应用,分析了中丈分词技术的重要性,对三类 基本分词算法进行了介绍并讨论了各自的特.点,提出了中文分词技术面临的难题及汁其未来的展望。
基于词典的中文分词,精确度较高,非常那个方便
目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配...
自选文档集进行KNN分词测试 C++类库实现 其中有基本词典和敏感词词典 对应不同的权值
1、颗粒度越大越好:用于进行语义分析的文本分词,要求分词结果的颗粒度越大,即单词的字数越多,所能表示的含义越确切,如:“公安局长”可以...则“公安局长”的分词结果最好(当然前提是所使用的词典中有这个词)
基于二级Hash的快速最长匹配分词算法,殷鹏程,谭献海,中文分词是中文信息处理的基础,在海量的中文信息处理中,分词速度至关重要。本文根据中文单词的特点,通过分析现有词典分词算法
最初,它是以开源项目Luence 为应用主体的,结合词典分词和文法分析算法的中文分词组件。 从 3.0 版本开始,IK 发展为面向 Java 的公用分词组件,独立于 Lucene 项目,同时提供了对 Lucene 的默认优化实现。 在 2012...
一个简单的中文分词算法,可用于网游脏词过滤、搜索引擎文档解析、自然语言处理等需要中文分词的场合 洋文单词以空格天然分词,相比较而言因为一句中文是由连贯的字组成的,分词就麻烦一些。最困难的情况是对二义性...
分别使用了正向最大匹配算法和KNN算法。分词速度平均153295词/秒,189100字符/秒。文本分类使用tf-idf计算单词权重进行特征选择,我测试时选择前100个特征词,根据k的不同取值,分类的准确度平均为75%。
词典与词频统计相结合的中文分词的研究,岳中原,,本文采用了统计和词典相结合的复合分词方法,在多个方面进行了改进。首先是在统计方面,通过对第一次分词结果中碎片的统计,识别
里面包含完整代码,有词典,解压后是vs2017的工程文件,可直接运用测试。
词典的加载 最大匹配算法 中文分词算法的实现
NULL 博文链接:https://show-your-sister.iteye.com/blog/277286
目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了反向最大匹配...
本文构造出一种适应中英文信息处理的Lucene语言分析器,该分析器的核心模块——分词器所使用的分词算法是一种基于词典的中文分词算法,该算法具体实现上采用了基于词前缀哈希技术来进行逐字匹配,采用基于规则统计...