相对于英文而言,中文在计算机处理方面有个必须要面对的问题就是中文分词,英文的单词都是空格间隔的,而中文的词语则不同,所以用程序解决中文分词,在很多自然语言处理方面都是首要进行的步骤。
其中最简单的就是最大匹配的中文分词了,比如“今天天气不错”可以分词为“今天/天气/不错”,但是面对一些有歧义的句子时却显得捉襟见肘,于是“南京市长江大桥”就会被分成“南京市长/江/大桥”而不是“南京市/长江/大桥”,于是更好的是基于统计学原理的分词,也就是说看哪种出现的频率更高。
对于一个中文字符串“a1a2a3…an”如何正确的用词语c1,c2..cm表示就是中文分词的任务,也就是说我们要去找寻P(c1c2..cm)最大的分词,按照马尔科夫链的想法就是说我们就是求P(c1)*P(c1|c2)*P(c1c2|c3)*…P(c1c2…cm-1|cm)最大。按照阿卡姆剃刀的想法我们可以假设一个最可能的实现,于是google黑板报的假设就是每个词只跟前面的词有关,于是变为求P(c1)*P(c1|c2)*P(c2|c3)*…P(cm-1|cm)最大。进一步的其实我们可以假设每个词都是相对独立的,也就是求P(c1)*P(c2)*…P(cm)最大,那么这个怎么求呢,就是用dp的方法。ok,上代码。
# -*- coding: UTF-8 -*-
import collections
d=collections.defaultdict(lambda:1)
def init(filename='SogouLabDic.dic'):
f=open(filename,'r')
total=0
while True:
line=f.readline()
if not line: break
word, freq = line.split('\t')[0:2]
total+=int(freq)+1#smooth
try:
d[word.decode('gbk')]=int(freq)+1
except:
d[word]=int(freq)+1
f.close()
d['_t_']=total
def solve(s):
l=len(s)
p=[0 for i in range(l+1)]
p[l]=1
div=[1 for i in range(l+1)]
t=[1 for i in range(l)]
for i in range(l-1,-1,-1):
for k in range(1,l-i+1):
tmp=d[s[i:i+k]]
if k>1 and tmp==1:
continue
if(d[s[i:i+k]]*p[i+k]*div[i] > p[i]*d['_t_']*div[i+k]):
p[i]=d[s[i:i+k]]*p[i+k]
div[i]=d['_t_']*div[i+k]
t[i]=k
i=0
while i
词库用到了搜狗实验室提供的不错的词库,程序还是很清晰的,值得注意的就是乘法不要直接去乘因为频率都是小于1的,乘的太多可能就会变为0就要影响整个算法了,所以我是分子分母分开存放的,话说直接用了python的原生大整数,连gcd都懒得写了啊。。。
ps:注意到如果词在字典里没有出现会导致概率乘积是0的情况,所以需要进行smooth
参考资料:
http://scturtle.is-programmer.com/posts/26648.html
http://www.matrix67.com/blog/archives/4212
http://www.google.com.hk/ggblog/googlechinablog/2006/04/blog-post_7327.html
http://mindhacks.cn/2008/09/21/the-magical-bayesian-method/
------------我是分割线--------------------
理论上用log相加的方法是最好的,于是修改了下代码,变得更简短了,只要34行哎,代码在github上
好厉害,学习了~
@ET: 呵呵,谢谢
没看出来有什么效果啊
$ python 中文分词.py
其 中 最 简 单 的 就 是 最 大 匹 配 的 中 文 分 词
这就是最后的结果么?
@leslie: 分出来的效果是
其中 最简单 的 就是 最大 匹配 的 中文 分词
你是不是字典没下载好
@isnowfy: 有可能, 我用的是精简版的词库
@leslie: 要用这个地址的字典 http://download.labs.sogou.com/dl/sogoulabdown/SogouW/SogouW.zip
– It’s disturbing to me that Honduras has been completely ignored. Does the media in any other country mention the coup or the corrupt election? Or are they trying to whitewash the fact that Latin America has seen its first coup in 20 years by claiming that a “fair election” has set things straight in Honduras and that &#;ec08d2mo2racy” is thriving?
@leslie:
你的词库是不是已经是utf8的了?要是gbk才管用
I love how IDRK aucmtatioally starts bashing Bush as if he’s the only one who hates him.How was is it bashing? What principle are you defending? What was inappropriate about the comment?You don’t know any of those things, do you?If 90% of teens are stupider than you, then the future is bleak. We had better hope that is a accurate as the other things you say.
赞,搜东西经常能路过你这里膜拜一下~~
@raya: 吼吼,欢迎来订阅rss阿
Hi,
我试了一下你的脚本,感觉很不错,现在有一个小问题一直很纠结。我对一批文件做分词,把你的脚本import进去,然后发现内存画画的往上涨。总共100M的文件(大概3000个),最后64G的内存都吃不下来,我稍微查了一下,发现占用最多的是Unicode类型,我觉得应该只有dictionary了吧,文本内容是扫一遍,最多在1G以下。我查了一下,觉得应该是没有回收,不知道是不是?怎么修改?
@Balloon: 这么吃内存的情况还真没遇到过,或许你可以先按标点符号分句,然后一句一句的调用solve来分词试一下
@isnowfy: 是一句跑一次的意思吗?我现在做的是分段落来跑的,段落也不是特别长。
@Balloon: 字典init()一次之后,以后都不会再变化了,所以不应该是字典,既然段落也不是很长就很奇怪了,init()只调用一次就可以,每个句子分别solve试试呢
@isnowfy: 刚才试了一下,只用,和。分割,但是还是出问题,内存还是往上涨。。。
@Balloon: 那你用这里的代码试一下呢 https://github.com/isnowfy/snowseg/blob/master/unigram_add_one.py ,或者会不会是你程序里用了什么全局变量导致越来越大呢
@isnowfy: 我昨晚跑了一遍,查了一下内存,就是collections.defaultdict占用最多。我把内存占用贴出来吧。
Partition of a set of 2199380 objects. Total size = 3831856296 bytes.
Index Count % Size % Cumulative % Referrers by Kind (class / dict of class)
0 2165475 98 3726882456 97 3726882456 97 collections.defaultdict
1 1766 0 101013488 3 3827895944 100 dict of module
2 10914 0 921872 0 3828817816 100 types.CodeType
3 4505 0 471416 0 3829289232 100 list
4 764 0 293304 0 3829582536 100 type
@isnowfy: 字典之前设的是全局的,后来我改了一下,改成一个返回值,然后在上层存了,solve的时候再当参数给进去
we must not rest until this criminal is in jail with all his corntspiraoocs in tow behind him. we must get the word out and send mr obama down to get his federal inmate number, and a nice cold cell with his cell mate bubba whos lookin for a new wife. pay backs are a bitch ms o .
@isnowfy: 这个代码没问题!什么原因啊。。。
@Balloon: PS 问一下博主这个算法是哪儿的啊?
@Balloon: 一种理解是这是分词里“求概率最大”的算法,一种是理解成hmm的1-gram算法
We stumbled over here coming from a different web page and thought I might as well check things out. I like what I see so i am just following you. Look forward to looking into your web page reedytpela.
@Balloon: 有些理解不能了,难道collections.defaultdict的实现有什么内存泄漏的问题吗,总之那个代码能用就好。。。
着手中文分词,不知如何下手,多谢啦