注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Allen小笔记

有时会忘记努力...

 
 
 

日志

 
 

单词拼写检查器 (C++版)  

2010-01-27 14:35:56|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                     C/C++  单词拼写检查  boost  googlesparsehash
    原文出处在这里:怎样写一个拼写检查器
    上面那文章通俗易懂,推荐一读。本着:动脑与动手相结合的态度,才有我这篇文章。
    首先,关键公式:
      P(h | D) = P(h) * P(D | h) / P(D)
    单词拼写检查依赖的就是贝叶斯公式。说通俗点,就是假如,用户想输入alley,结果一不小心输入了allem。那么就要算出P(XXX|allem)的概率,那么P(XXX|allem)中概率最大的就是用户最想要的,概率最大可能是P(alley|allem),也可能是别的,比如P(allen|allem)。当然,P(XXX|allem)取最大值的时候也仅仅是可能,因为这是概率,即用户完全有可能想输入一个很不常用的单词。你无从知晓。
    那么P(XXX|allem)要怎么计算呢,我们可以算P(XXX)*P(allem|XXX)/P(allem). P(XXX)很容易计算出来,我们只要统计出单词出现的概率即可(叫做训练模型)。P(allem|XXX)有点困难,这个表达式的意思是:XXX推导出allem的概率。我代码采用了简单的算法,就是改变allem单词最少就能产生正确单词的优先。假如allem是正确的单词则allem最优先.
   Okay,大致的原理说完了。介绍一下,这次我写的代码。
    这段代码,核心的是采用boost的Regex库来parser出big.txt(里面几乎全是英文单词)里面的英文单词。googlesparsehash的hashmap这个容器,加上MS的Hash_Compare()来计算hash值。将Parser出来的单词放入Hashmap,并统计出每个单词的出现频率。
   okay,看结果:输入allem,输出alley。
   

   其实,我写这么个小程序,大概花了有3天时间。原因是:我不熟悉boost,不熟悉googlesparsehash,正则表达式也还差点功力。
  而且,有一个错误,把我当时都搞懵啦~报的是运行时错误。
  结果,我这google 的doc上看到这么一句话:dense_hash_map requires you call set_empty_key() immediately after constructing the hash-map, and before calling any other dense_hash_map method. (This is the largest difference between thedense_hash_map API and other hash-map APIs. See implementation.html for why this is necessary.)   
  诶...不好好,读文档的结果啊.
   想要源代码的,Email:bloodysofiya@163.com

  更新:   
之前写的代码,仅仅是跑在debug模式下,而我一换到release模式下,尽然free()函数报错。当时,就觉得很奇怪,这种问题通常是因为debug模式会多分派些内存给变量(比如调用malloc()函数),而release模式下则不像debug模式,所以这个错误理论上就是内存溢出,所以找来找去,终于发现了错误的地方,多使用了5byte内存,改正后就行了.

 更新:
      之前的代码,是单线程的,所以训练模型是比较花费时间的一个过程。我改用boost::thread库来做多线程。
     Visual studio 的debug版和release版的速度相差了将近600倍,原本只要400ms却花费了4分多钟。在debug的时候,程序不响应,导致我以为出了问题....结果正确的。汗...说来也巧,找这个问题的时候,我在医院打点滴,做事就慢,一会儿写代码,一会儿看看药水,4分钟一会儿就过了,结果反而发现了问题。
    代码可以从这里下载了:http://code.google.com/p/spellingcorrector/
  
  评论这张
 
阅读(1416)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017