前几天读到google研究员吴军的数学之美系列篇颇有感触而恰好自己前段时间做了个基于统计语言模型的中文切分系统的课程项目于是乎帖出来与大家共同学习
分词技术在搜索引擎信息提取机器翻译等领域的重要地位与应用就不敖述了步入正题）
一 项目概述
本切分系统的统计语料是用我们学校自己开放的那部分大家可以在 这里 下载中文字符约万当然这都是已切分好了的可以用此建立一个比较小的语料库本系统我主要分下面四个步骤完成
语料预处理
建立 gram（统计二元模型）
实现全切分
评估测试
下面我分别对这四个方面一一道来
语料预处理
下载的已切分的语料都是形如/m 现实/n 的/u 顿悟/vn 却/d 被/p 描/v 出/v 形/Ng 来/v /w 有的前面还保留了日期编号因为这些切分语料的来源是人民日报预处理主要是按标点符号分句句子简单定义为（ ？！ ）这五种标点符号结尾的词串句子首尾分别添加<BOS>和<EOS>这两个表示句子开始和结束的标记这在gram建模时要用的后面会提到处理过程中忽略词类信息和前面的日期信息因为我这个切分系统不考虑词类标注如前面这句预处理后应该为下面形式 <BOS>现实 的 顿悟 却 被 描 出 形 来 <EOS> 当然切分词之间你可以用你想用的符号标记而不必是空格因为考虑到所有的英文字符和数字的ASCII我用了下面方法实现之
out ; //输出流
in; //输入流
StringBuffer s = new StringBuffer(); //缓沖
char a = inread();
while (a != ) //判断是否已到流的终点
{
if ((a == || a == ？ || a == ！ || a == || a == )) //一句结束
{
String s = new String(s);
outwrite(<BOS>); //在句子前加 <BOS>
outwrite(s);
outwrite(<EOS>); //在句子末尾加 <EOS>
outwrite(/n); //换行
s = new StringBuffer();
}
else if ( a == /)
s = sappend((char)); //分词位置空格
else if (a > )
s = sappend((char)a);
a = inread();
}
outclose();
inclose();
建立 gram模型（统计二元模型）
在这里首先简单介绍一下ngram模型和gram模型
根据语言样本估计出的概率分布P就称为语言L的语言模型对给定的句子s = ww…wn（数字ni都为下标wi为句子s的一个词）由链式规则（Chain rule）P(s) = p(w)p(w|w)p(w|ww)……p(wn|www…w(n)) 对p(wi|ww…w(i))而言(ww…w(i))即为wi的历史考虑前面n个词构成历史的模型即为ngram模型 n越大提供的语境信息也越多但代价就越大且需训练语料多n较小时提供的信息比较少但计算代价小且无需太多训练语料
令c(w…wi)表示词串ww…wi在训练语料中出现的次数则由最大似然估计 P(wn|w…w(n)) = c(w…wn) / c(w…w(n)) 同理则gram为 P(wn|w(n)) = c(w(n)wn) / c(w(n))
若想了解更多相关知识大家找相关资料看看随便把大学时的那本概率与统计课本拿出来翻翻数学真是一个好东东）
回归项目） 训练语料一共有万多个不同的词建立gram统计模型时不断要把每个词在训练语料中出现频率统计出来还要把每个词及其后面的那个词组成的gram在训练语料中出现频率统计出来因为在切分时会频繁的在建立的gram模型中查找相关的数据所有存储这个gram模型数据的数据结构一定要能提供高效的查找故选择hash表它能提供常数时间的查找Java类库里提供了HashMap类基于数据两还不是非常大故可直接拿来用在存储时每一个key值对应一个在训练语料中出现过的词语而每一个key值对应的value值又是一个HashMap暂且称为子hashmap这个结构有点类似文件结构里的二级索引 其相关代码如下
怎么在预处理文件里把词分别读出来就不罗嗦了方法每读入一行按空格分成String数组用个正则表达式匹配下即能得到
//此方法传入的两个词组成一个gramprewd为前一个词currwd为紧随其后的词
public static void add(String prewd String currwd){
String key = prewd;
String curr = currwd;
boolean bb = ntainsKey(key);
//Hmap是一个已存在的HashMap用来存储gram统计模型在这里判断 preword 是否在 主map 中
if (bb == false) { //若 主map 中无则添加
HashMap hm = new HashMap(); //首先新构造一个 子MAP
hmput(key new Integer()); //存储 主KEY 的频率
hmput(curr new Integer()); //存储 主KEY 后面紧接着的那个词频率
HMapput(keyhm); //将 主KEY 和对应的 子MAP 放入 主MAP 中
}
else //若 主map 中含有该词
{
HashMap temp = (HashMap)HMapget(key); //返回 主KEY 所对应的 子MAP 进行值的修改
int count = ((Integer)tempget(key))intValue() + ; //在 子map 中将 主key 次数加
tempput(key new Integer(count));
if (ntainsKey(curr)) //判断 子map 中是否含有该词
{
int value = ((Integer)tempget(curr))intValue() + ;
tempput(curr new Integer(value));
}
else
tempput(curr new Integer()); //若无则将其存入子map
HMapput(key temp); //子map 修改完毕 将其重新放入 主map
}
}
}
因为语言中的大部分词属于低频词所以稀疏问题肯定存在而MLE（最大似然估计）给在训练语料中没有出现的gram的赋给概率所以还得对gram模型进行数据平滑以期得到更好的参数目前平滑技术比较多如AddoneAdddeltaWittenBellheldout留存平滑等本系统主要采用了Adddelta和heldout两中平滑方式下面就Adddelta平滑技术为例对gram进行平滑对gram模型其平滑公式为
P(wn|w(n)) = [c(w(n)wn) + delta ] / ( N + delta * V)
这里去delta为
其中N训练语料中所有的gram的数量
V所有的可能的不同的gram的数量
平滑思路 产生主hashmap的迭代器iterator依次读key;
对每一个key又读出其value即一个子hashmap;
然后根据平滑公式对子map里的值进行计算修改
算法框架
Iterator it = 主hashmapkeySet(erator();
While(ithasNext())
{
主key = itnext();
子hashmap = (HashMap)主hashmapget(主key);
Iterator itr = 子hashmapkeySet(erator();
While(itrhasNext())
{
根据平滑公式依次计算修改
}
}
注意问题因为计算得出的概率值一般都比较小为了防止出现下溢可对其取对数再取反
每一个主key所对应的所有没有出现过的即频率为零的gram统一用一个键值对存储在相应的子hashmap里即可
完毕对象序列化使用该系统时lazy load将其载入内存然后可让其一直存活在内存这会大大加快速度
到此gram模型建立完毕
全切分实现
切词一般有最大匹配法（MMRMM）基于规则的方法基于统计的方法关于前两者就不罗嗦了所谓全切分就是要根据字典得到所以可能的切分形式歧义识别的方法主要有基于规则的方法和基于统计的方法这里当然是采用基于gram统计模型的方法了）为了避免切分后再进行歧义分析的时间浪费并且这里采用边切分边评价的方法即在切分进行的同时进行评价的方法
对一个句子进行全切分的结果即所以可能的组合可以形成一棵解空间树
于是可用回溯法搜索最优解
若将所有的全切分组合先搜索出来然后再根据gram选择最佳显然会很浪费时间因为过程中可能存在很多的重复搜索而回溯搜索的时间复杂度为指数时间
所以在搜索过程中要结合 剪枝避免无效搜索可很大提高效率
采用树的深度优先法则可找到最优解
具体算法如下
Stackpush(BOS) //树节点
while stack不为空
x=stackpop()
pos=x．Pos w = xw oldvalue= xvalue preword=xpreword
if m>O then //m为首词串的个数
forj= 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+FWjposlnewsate)>maxValue(pos)
stackpush(x)
endif
endfor
endif
endwhile
end．
在算法实现过程中需要考虑一些诸如树节点保存
首词串处理等问题
评估测试
环境windows XP AMD Athlon + Memory mJDK
Delta平滑随着delta的取值变小准确率上升
召回率
准确率
留存平滑
召回率
准确率
一般情况下
留存平滑应该还是比delta平滑更好
所有建模过程及平滑过程在分钟内都可完成
切分时间与效率
n 测试语料字符 （中文）平均句长 个字时间 ms 平均切分速度 万/S
n 万测试语料（取自笑傲江湖） 预处理后 万 时间 MS句子文本行数目 平均句长 切分时间 MS 平均 万 / 秒
n 万测试语料（取自笑傲江湖）不预处理平均句长 切分时间S 平均 字/秒
回溯算法是时间开销为O(N!)所以在切分过程中句子长度直接决定了切分的速度因为句子越长词越多
经过预处理句子短平均句长 回溯短故速度要快很多
到此该系统基本完成告一段落感觉写的挺乱的呵呵
现在在做另一个作业做个简单搜索引擎准备把这个东东结合在搜索引擎里面实现切分功能
