- 浏览: 571429 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (253)
- java (84)
- python (22)
- 设计模式 (12)
- 数据结构和算法 (7)
- ibatis (1)
- 数据挖掘 (2)
- 集体智慧读书笔记 (1)
- ubuntu (4)
- lucene (11)
- 算法 第4版 (11)
- apache mina (16)
- memcached (1)
- android (9)
- netty (6)
- mongodb (2)
- maven (2)
- openfire (2)
- 服务端 (21)
- 产品 (0)
- apache (1)
- 选择 (2)
- 构架WEB高性能站点 (7)
- redis (8)
- 诗词歌赋 (3)
- 源代码阅读 (5)
- 前端 (1)
- javascript (3)
- guice (1)
- 分布式 (5)
- 总结-2014 (4)
- jvm (1)
最新评论
-
liu_jiaqiang:
写的挺好
maven多项目管理 -
H972900846:
我想知道哪里整的,如果是自己写的,那有点牛呀如果是抄的请说明出 ...
SSL身份认证原理 -
春天好:
博主写的很好,赞一个,多谢分享 *(^-^*)分享一个免费好用 ...
定向网站爬虫---初级例子 -
fenglingabc:
经过测试,parameterType="java.u ...
mybatis获取主键和存储过程返回值 -
jyghqpkl:
[u][/u] ...
Cookie的secure 属性
转载原文:http://hxraid.iteye.com/blog/667134
中文分词一直都是中文自然语言处理领域的基础研究。目前,网络上流行的很多中文分词软件都可以在付出较少的代价的同时,具备较高的正确率。而且不少中文分词软件支持Lucene扩展。但不管实现如何,目前而言的分词系统绝大多数都是基于中文词典的匹配算法。
在这里我想介绍一下中文分词的一个最基础算法:最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有两种:一种正向最大匹配,一种逆向最大匹配。
● 算法思想
正向最大匹配算法:从左到右将待分词文本中的几个连续字符与词表匹配,如果匹配上,则切分出一个词。但这里有一个问题:要做到最大匹配,并不是第一次匹配到就可以切分的 。我们来举个例子:
待分词文本: content[]={"中","华","民","族","从","此","站","起","来","了","。"}
词表: dict[]={"中华", "中华民族" , "从此","站起来"}
(1) 从content[1]开始,当扫描到content[2]的时候,发现"中华"已经在词表dict[]中了。但还不能切分出来,因为我们不知道后面的词语能不能组成更长的词(最大匹配)。
(2) 继续扫描content[3],发现"中华民"并不是dict[]中的词。但是我们还不能确定是否前面找到的"中华"已经是最大的词了。因为"中华民"是dict[2]的前缀。
(3) 扫描content[4],发现"中华民族"是dict[]中的词。继续扫描下去:
(4) 当扫描content[5]的时候,发现"中华民族从"并不是词表中的词,也不是词的前缀。因此可以切分出前面最大的词——"中华民族"。
由此可见,最大匹配出的词必须保证下一个扫描不是词表中的词或词的前缀才可以结束。
● 算法实现
词表的内存表示: 很显然,匹配过程中是需要找词前缀的,因此我们不能将词表简单的存储为Hash结构。在这里我们考虑一种高效的字符串前缀处理结构——Trie树《Trie Tree 串集合查找 》。这种结构使得查找每一个词的时间复杂度为O(word.length),而且可以很方便的判断是否匹配成功或匹配到了字符串的前缀。
下图是我们建立的Trie结构词典的部分,(词语例子:"中华","中华名族","中间","感召","感召力","感受")。
(1) 每个结点都是词语中的一个汉字。
(2) 结点中的指针指向了该汉字在某一个词中的下一个汉字。这些指针存放在以汉字为key的hash结构中。
(3) 结点中的"#"表示当前结点中的汉字是从根结点到该汉字结点所组成的词的最后一个字。
TrieNode源代码如下:
- import java.util.HashMap;
- /**
- * 构建内存词典的Trie树结点
- *
- * @author single(宋乐)
- * @version 1.01, 10/11/2009
- */
- public class TrieNode {
- /**结点关键字,其值为中文词中的一个字*/
- public char key=(char)0;
- /**如果该字在词语的末尾,则bound=true*/
- public boolean bound=false;
- /**指向下一个结点的指针结构,用来存放当前字在词中的下一个字的位置*/
- public HashMap<Character,TrieNode> childs=new HashMap<Character,TrieNode>();
- public TrieNode(){
- }
- public TrieNode(char k){
- this.key=k;
- }
- }
这套分词代码的优点是:
(1) 分词效率高。纯内存分词速度大约240.6ms/M,算上IO读取时间平均1.6s/M。测试环境:Pentium(R) 4 CPU 3.06GHZ、1G内存。
(2) 传统的最大匹配算法需要实现确定一个切分的最大长度maxLen。如果maxLen过大,则大大影响分词效率。而且超过maxLen的词语将无法分出来。但本算法不需要设置maxLen。只要词表中有的词,不管多长,都能够切分。
(3) 对非汉字的未登录词具备一定的切分能力。比如英文单词[happy, steven],产品型号[Nokia-7320],网址[http://www.sina.com]等。
缺点也很明显:
(1) 暂时无词性标注功能,对中文汉字的未登录词无法识别,比如某个人名。
(2) 内存占用稍大,目前词表为86725个词。如果继续扩展词表,很有可能内存Trie树将非常庞大。
代码的进一步优化方案:
(1) 想在内存占用空间上降低代价。实际上Trie树主要的空间消耗在每个结点的指针HashMap上。我使用的是JDK中的HashMap,其加载因子为 loadFactor= 0.75,初始化空间大小为DEFAULT_INITIAL_CAPACITY= 16。每次存储数据量超过 loadFactor* DEFAULT_INITIAL_CAPACITY的时候,整个Map空间将翻倍。 因此会照成一定的空间浪费。
但目前还没有想到很好的办法,即能够随机定位到下一个结点的指针,又降低Hash结构的空间代价?
下面是我实现的基于Trie词典结构的正向最大匹配算法的源代码包和分词词表,可供大家学习下载。但绝对不允许任何商业性质的传播,违者必究。
发表评论
-
protobuf-dt插件
2015-03-24 13:16 1368protobuf-dt: 安装前先安装xtext 可 ... -
java循环标签
2015-03-20 16:13 563今天看 源码的时候 看到 一个小语法 参考: ... -
java程序性能优化 --阅读
2014-10-14 17:56 670闲着,真实无聊; 发现一本好书《java程序性能优 ... -
jetty invalid entry CRC问题
2014-08-04 11:42 15321: http://stackoverflow.com/qu ... -
guice注入
2014-05-24 12:13 9398Google Guice3.0: http://code. ... -
eclipse快捷键
2014-05-21 16:01 5331: clrl+alt+r : 最常用,快速定位到文件 2 ... -
java clone
2014-05-16 17:04 490转:http://www.blogjava.net/ora ... -
ThreadLocal
2014-05-13 18:39 731简单介绍一下ThreadLocal的原理:1.Thread ... -
hession
2014-04-30 12:33 656一、首先先说Hessian是什么? Hessian:he ... -
冒泡和快速排序java
2014-04-19 18:01 7141: 冒泡最简单一种: /** * 算法效率o ... -
java生产者和消费者模型三种实现
2014-04-19 17:51 13351: 生产者和消费者的问题,生产者生产产品到缓冲区,消费者 ... -
单例模式
2014-03-14 16:06 712今天看到群里,关于单例模式的多线程下的安全问题: 1:最 ... -
freemarker的使用
2014-02-28 16:42 7971:freemarker eclipse插件安装方法:ht ... -
java 引用类型和内存泄露
2013-11-21 17:48 553http://blog.csdn.net/luoshenfu ... -
java泛型
2013-11-07 13:52 401Class<T>在实例化的时候,T要替换成具体 ... -
filter执行顺序
2013-10-12 11:16 1097多个筛选器的运行顺序取决于下列规则: 将 filt ... -
spring rmi远程调用
2013-09-09 11:48 11451:以前用jmi发布服务,实现分布式的一种方式,远程调用, ... -
spring mvc返回204状态码
2013-07-24 09:27 38801:204是没内容 不跳转的 代表请求成功的意思 ... -
editplus去掉多余空行
2013-07-19 21:05 6961: ^[ \t]*\n 用正则表达式替换 -
spring3 aop 使用详细
2013-06-06 11:10 01:目标:拦截所有的@Controller中的方法 ...
相关推荐
运用正向最大匹配算法进行分析,同时也实现了逆向最大匹配,内有分词词典。
MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配算法。 本程序还可以从我的github上面下载:https://github.com/Zehua-Zeng/Maximum-Matching-Algorithm
本程序是北京师范大学学生根据一个中文字库对所给的文章进行分词。...采用的算法是正向最大匹配算法和反向最大匹配算法。主要实现屏幕分词和文件分词两项功能。因为对毕业设计有所帮助,所以我要分高一点哈~勿怪偶~
使用正向最大匹配FMM分词 以及逆向最大匹配BMM分词 但不是同时使用
Java实现分词(正向最大匹配和逆向最大匹配)两种方法实现
分词匹配算法:正向最大匹配和反向最大匹配
中文分词一直都是中文自然语言处理领域的基础研究。目前,网络上流行的很多中文分词软件都可以在付出较少的代价的同时...MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配算法。
python正向最大匹配分词和逆向最大匹配分词完整的源代码分享,运行使用后对相关技术人员很有分享价值,为开发人员节省开发时间和提高开发思路是很不错的选择
这是我自己写的最经典的分词算法:正向最大匹配算法 ,有兴趣的朋友可以拿去看看
简单的最大正向匹配分词方法,用c++开发而成,自己可以手动的添加词典资源
读取词表,按照最大正向匹配法给中文分词。然后么,大家都懂的。只是一个课程练习。大家不要太当真
perl 写的正向最大匹配分词模块。 # #正向最大分词 #eg: my $seg = new Segmenter($list); # my $list_arrref = $seg->segment($line); #
中文分词应用很广泛,网上也有很多开源项目,下面这篇文章主要给大家介绍了关于java中文分词之正向最大匹配法的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考借鉴,下面随着小编来一起学习学习吧。
Python3.8 包含字典词库的txt文件,只需在代码中自行输入文件位置即可使用 利用Python爬虫爬取文本资料后进行中文分词
在正向最大匹配的基础上增加一个交集型歧义字段处理模块一次来提高分词效率
MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了反向最大匹配算法。 本程序还可以从我的github上面下载:https://github.com/Zehua-Zeng/Reverse-Maximum-Matching-Algorithm
在一个已经语料库的基础上,进行词频统计,然后根据统计的词用正向和反向最大匹配算法进行中文分词。
用C#开发的基于正向和逆向最大匹配的分词程序。
中文分词词典 适合最大正向匹配算法使用 共计548389条词语
处理中文地址的分词和匹配 采用混合分词算法进行中文地址分词 在中文地址分词基础上采用Double Levenshetin算法进行中文地址相似度进行地址匹配