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

来源：CSDN 作者： 出处：巧巧读书 2007-06-18 进入讨论组

• 关 键 词：
• windows xp
• google
• 搜索引擎
• 数据结构
• word

上一页 1 2 3 

            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, 回溯短，故速度要快很多。

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

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

专题:http://www.qqread.com/java/2007/06/v317390.html 更多内容请看SQL Server 索引和查询专题、Java环境安装配置、Java编程开发手册专题，或进入讨论组讨论。

上一页 1 2 3 

【收藏此文】【大 中 小】【打印】【关闭】

较早的文章：Java IDE鱼龙混杂，我们该如何选择呢？

较新的文章：用Hibernate3.1实现XML和数据库的同步