分享
 
 
 

搜索引擎之中文分词实现(java版)

王朝java/jsp·作者佚名  2007-06-16
窄屏简体版  字體: |||超大  

搜索引擎之中文分词实现(java版)

前几天读到google研究员吴军的数学之美系列篇,颇有感触。而恰好自己前段时间做了个基于统计语言模型的中文切分系统的课程项目,于是乎,帖出来与大家共同学习。

分词技术在搜索引擎,信息提取,机器翻译等领域的重要地位与应用就不敖述了。步入正题:)

一、 项目概述

本切分系统的统计语料是用我们学校自己开放的那部分,大家可以在 这里 下载,中文字符约184万,当然这都是已切分好了的,可以用此建立一个比较小的语料库。本系统我主要分下面四个步骤完成:

1、 语料预处理

2、 建立 2-gram(统计二元模型)

3、 实现全切分

4、 评估测试

下面我分别对这四个方面一一道来。

1、 语料预处理

下载的已切分的语料都是形如“19980131-04-012-001/m 现实/n 的/u 顿悟/vn 却/d 被

/p 描/v 出/v 形/Ng 来/v 。/w ” ,有的前面还保留了日期编号,因为这些切分语料的来源是人民日报。预处理主要是按标点符号分句,句子简单定义为( 。?! : ;)这五种标点符号结尾的词串,句子首尾分别添加<BOS>和<EOS>这两个表示句子开始和结束的标记,这在2-gram建模时要用的,后面会提到。处理过程中,忽略词类信息和前面的日期信息,因为我这个切分系统不考虑词类标注。如前面这句预处理后应该为下面形式 “<BOS>现实 的 顿悟 却 被 描 出 形 来 。<EOS>” ,当然切分词之间你可以用你想用的符号标记,而不必是空格。因为考虑到所有的英文字符和数字的ASCII,我用了下面方法实现之:

out ; //输出流

in; //输入流

StringBuffer s1 = new StringBuffer(); //缓冲

char a = in.read();

while (a != -1) //判断是否已到流的终点

{

if ((a == '。' || a == '?' || a == '!' || a == ':' || a == ';' )) //一句结束

{

String s2 = new String(s1);

out.write("<BOS>"); //在句子前加 <BOS>

out.write(s2);

out.write("<EOS>"); //在句子末尾加 <EOS>

out.write('/n'); //换行

s1 = new StringBuffer();

}

else if ( a == '/')

s1 = s1.append((char)32); //分词位置空格

else if (a > 256 )

s1 = s1.append((char)a);

a = in.read();

}

out.close();

in.close();

2、 建立 2-gram模型(统计二元模型)

在这里首先简单介绍一下n-gram模型和2-gram模型。

根据语言样本估计出的概率分布P就称为语言L的语言模型。对给定的句子s = w1w2…wn,(数字,n,i都为下标,wi为句子s的一个词)。由链式规则(Chain rule),P(s) = p(w1)p(w2|w1)p(w3|w1w2)……p(wn|w1w2w3…w(n-1)) , 对p(wi|w1w2…w(i-1))而言,(w1w2…w(i-1))即为wi的历史。考虑前面n-1个词构成历史的模型即为n-gram模型。 n越大,提供的语境信息也越多,但代价就越大,且需训练语料多;n较小时,提供的信息比较少,但计算代价小,且无需太多训练语料。

令c(w1,…,wi)表示词串w1,w2…wi在训练语料中出现的次数,则由最大似然估计, P(wn|w1,…,w(n-1)) = c(w1,…,wn) / c(w1,…,w(n-1)). 同理,则2-gram为 P(wn|w(n-1)) = c(w(n-1),wn) / c(w(n-1)).

若想了解更多相关知识,大家找相关资料看看,随便把大学时的那本概率与统计课本拿出来翻翻,数学真是一个好东东:)

回归项目:) 训练语料一共有5万多个不同的词。建立2-gram统计模型时不断要把每个词在训练语料中出现频率统计出来,还要把每个词及其后面的那个词组成的2-gram在训练语料中出现频率统计出来。因为在切分时会频繁的在建立的2-gram模型中查找相关的数据,所有,存储这个2-gram模型数据的数据结构一定要能提供高效的查找。故选择hash表,它能提供常数时间的查找。Java类库里提供了HashMap类,基于数据两还不是非常大,故可直接拿来用。在存储时,每一个key值对应一个在训练语料中出现过的词语,而每一个key值对应的value值又是一个HashMap。暂且称为子hashmap.这个结构有点类似文件结构里的二级索引。 其相关代码如下:

怎么在预处理文件里把词分别读出来就不罗嗦了,方法:每读入一行,按空格分成String数组,用个正则表达式匹配下即能得到。

//此方法传入的两个词组成一个2-gram,prewd为前一个词,currwd为紧随其后的词

public static void add(String prewd , String currwd){

String key = prewd;

String curr = currwd;

boolean bb = HMap.containsKey(key); //Hmap是一个已存在的HashMap,用来存储2-gram统计模型。在这里判断 preword 是否在 主map 中

if (bb == false) { //若 主map 中无,则添加

HashMap hm = new HashMap(); //首先,新构造一个 子MAP

hm.put(key , new Integer(1)); //存储 主KEY 的频率 hm.put(curr , new Integer(1)); //存储 主KEY 后面紧接着的那个词频率

HMap.put(key,hm); //将 主KEY 和对应的 子MAP 放入 主MAP 中

}

else //若 主map 中含有该词

{

HashMap temp = (HashMap)HMap.get(key); //返回 主KEY 所对应的 子MAP ,进行值的修改

int count = ((Integer)temp.get(key)).intValue() + 1; //在 子map 中将 主key 次数加 1

temp.put(key , new Integer(count));

if (temp.containsKey(curr)) //判断 子map 中是否含有该词

{

int value = ((Integer)temp.get(curr)).intValue() + 1; temp.put(curr , new Integer(value));

}

else

temp.put(curr, new Integer(1)); //若无,则将其存入子map

HMap.put(key , temp); //子map 修改完毕 ,将其重新放入 主map

}

}

}

因为语言中的大部分词属于低频词,所以稀疏问题肯定存在。而MLE(最大似然估计)给在训练语料中没有出现的2-gram的赋给0概率。所以还得对2-gram模型进行数据平滑,以期得到更好的参数。目前平滑技术比较多,如Add-one,Add-delta,Witten-Bell,held-out留存平滑等。本系统主要采用了Add-delta和held-out两中平滑方式,下面就Add-delta平滑技术为例,对2-gram进行平滑。对2-gram模型,其平滑公式为:

P(wn|w(n-1)) = [c(w(n-1),wn) + delta ] / ( N + delta * V) ,这里去delta为0.5

其中,N:训练语料中所有的2-gram的数量

V:所有的可能的不同的2-gram的数量

平滑思路 :1.产生主hashmap的迭代器iterator,依次读key;

2.对每一个key,又读出其value,即一个子hashmap;

3.然后根据平滑公式对子map里的值进行计算修改

算法框架:

Iterator it = 主hashmap.keySet().iterator();

While(it.hasNext())

{

主key = it.next();

子hashmap = (HashMap)主hashmap.get(主key);

Iterator itr = 子hashmap.keySet().iterator();

While(itr.hasNext())

{

根据平滑公式依次计算修改

}

}

注意问题:1.因为计算得出的概率值一般都比较小,为了防止出现下溢,可对其取对数,再取反。

2.每一个主key所对应的所有没有出现过的,即频率为零的2-gram,统一用一个键值对存储在相应的子hashmap里即可。

完毕,对象序列化。使用该系统时,lazy load将其载入内存,然后可让其一直存活在内存,这会大大加快速度。

到此,2-gram模型建立完毕。

3、 全切分实现

切词一般有最大匹配法(MM、RMM),基于规则的方法,基于统计的方法。关于前两者就不罗嗦了。所谓全切分就是要根据字典得到所以可能的切分形式。歧义识别的方法主要有:基于规则的方法和基于统计的方法。这里当然是采用基于2-gram统计模型的方法了:)为了避免切分后再进行歧义分析的时间浪费。并且这里采用边切分边评价的方法,即在切分进行的同时进行评价的方法。

对一个句子进行全切分的结果,即所以可能的组合,可以形成一棵解空间树

于是,可用回溯法搜索最优解

若将所有的全切分组合先搜索出来,然后再根据2-gram选择最佳,显然会很浪费时间,因为过程中可能存在很多的重复搜索,而回溯搜索的时间复杂度为指数时间

所以,在搜索过程中要结合 剪枝,避免无效搜索,可很大提高效率

采用树的深度优先法则。可找到最优解

具体算法如下:

Stack.push(BOS) //树节点

while stack不为空

x=stack.pop()

pos:=x.Pos, w = x.w oldvalue:= x.value preword:=x.preword

if m>O then //m为首词串的个数

forj:=1 to m do

FWj为fwc的第j个元素l

if length(w+FWj) =length(c)且概率最大 then output w+FWjl且设置最新的句子最大概率值

else

posl:=pos+length(FWj)l

if probability(w+FWj,posl,newsate)>maxValue(pos1)

stack.push(x)

endif

endfor

endif

endwhile

end.

在算法实现过程中需要考虑一些诸如树节点保存,首词串处理等问题。

4.评估测试

环境:windows XP2, AMD Athlon 1800+, Memory 768m,JDK1.5

Delta平滑:随着delta的取值变小,准确率上升,0.5,0.01,0.0001

召回率: 0.9756 0.9826 0.9928

准确率: 0.9638 0.9710 0.9883

留存平滑

召回率: 0.9946

准确率: 0.9902

一般情况下,留存平滑应该还是比delta平滑更好

所有建模过程及平滑过程在1分钟内都可完成。

切分时间与效率:

n 测试语料,17455字符, (中文17287),平均句长 41个字,时间 :340ms, 平均切分速度:5.1 万/S

n 20.5万测试语料(取自笑傲江湖), 预处理后 17.46万 ,时间 110 MS,句子文本行数目 24945,平均句长 7 , 切分时间 1300MS , 平均13.46 万 / 秒

n 20.5万测试语料(取自笑傲江湖),不预处理,平均句长 239 ,切分时间40S, 平均 5000字/秒

回溯算法是时间开销为O(N!),所以在切分过程中句子长度直接决定了切分的速度,因为句子越长词越多

经过预处理,句子短,平均句长 7, 回溯短,故速度要快很多。

到此,该系统基本完成,告一段落。感觉写的挺乱的呵呵

现在在做另一个作业,做个简单搜索引擎,准备把这个东东结合在搜索引擎里面,实现切分功能:)

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有