搜索引擎之中文分词实现（java版）

因为语言中的大部分词属于低频词，所以稀疏问题肯定存在。而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模型建立完毕。

<!--[if !supportLists]-->            3、  <!--[endif]-->全切分实现
 

切词一般有最大匹配法（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．

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