前几天读到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，我用了下面方法实现之：

根据语言样本估计出的概率分布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数组，用个正则表达式匹配下即能得到。

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

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

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

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

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

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

具体算法如下：

 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

 所有建模过程及平滑过程在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, 回溯短，故速度要快很多。

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

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