- 关 键 词：
- windows xp
- 搜索引擎
- 数据结构
- word
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); 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模型建立完毕。
收藏 http://www.qqread.com/java/2007/06/v317390.html
更多内容请看SQL Server 索引和查询专题、Java环境安装配置、Java编程开发手册专题，或进入讨论组讨论。
相关专题
- SQL Server 索引和查询专题 (3324篇文章)
- Java环境安装配置 (5658篇文章)
- Java编程开发手册 (8309篇文章)
- 搜索引擎 (547篇文章)
- Java网络及通讯编程 (667篇文章)
- 开发框架：深入了解 Struts Validator (3次浏览)
- Java中的通信机制及与C/C API的集成 (1次浏览)
- 用Hibernate实现领域对象的自定义字段 (1次浏览)
- 精通Hibernate之映射继承关系（一） (0次浏览)
- 精通Hibernate之映射继承关系（二） (0次浏览)
- 美国计算机教授语出惊人：Java对学生有害 (0次浏览)
- JDK 6 JRE 6 Update 4 (0次浏览)
- 三步教你改善Java代码质量 (0次浏览)
- Java语言入门 简述Java语言回收机制 (0次浏览)
- 2008年Java开发者最迫切的五个期望 (0次浏览)
