我们已使用 terark.com 进行商业化运营

多音字 搜索词纠错: 匹配简拼(汉字数≥5时才有效)  单字的拼音来自:这里(最全的多音字)...     

当搜索词中有错别字时,搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音,用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略,但是,当输错的字是多音字,特别是有多个这样的错误输入时,所有的搜索引擎都尽量绕开这个问题,或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合,在极端情况下会导致指数爆炸! 例如美团的实现(枚举多音字全排列)

基于自动机的算法可以完美解决这个指数爆炸问题

  • 这是自动机应用的又一个绝佳范例,作为演示,这个页面只收录了 800万搜索词+词频,数据也不太干净
  • 该算法全部在内存中运行,使用了 293M 内存,这个数据量,如果用传统方法暴力实现,并且达到这个性能,需要 几十G 的内存
  • 暴力方法是 Query 越长越可怕,该算法则是 Query 越长,优势越大
  • 纠错耗时仅供参考(单核虚拟云主机: Xeon E5-2430 2.20GHz + RAM:1.5G),如果你看到搜索耗时过长,很可能是mmap数据被swap到了硬盘上,再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分,就自动提示出整个Query,例如用户输入举头望,就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词,使用我的算法也可以高效解决(还没做演示页面)

是个软件都想强奸用户

阅读更多关于《是个软件都想强奸用户》

Windows 7 资源管理器反应超慢已经很久了,刚刚这个问题被我彻底解决。使用 Autoruns 查看 Explorer 页,删掉所有可疑的王八蛋继续阅读

一个变态C/C++面试题的变态解法

阅读更多关于《一个变态C/C++面试题的变态解法》

这是源自某论坛的一个问题,原帖如下(#########分隔) 继续阅读

服务器超时管理问题

阅读更多关于《服务器超时管理问题》
  1. 有一个最多能处理N个客户连接的服务器,活跃的连接总是少数;
  2. 为了能够处理更多的连接,需要对每个连接都增加一个超时机制,当总连接数达到N时,某个连接一旦超时,有新的连接请求时,就把超时的关掉,并处理新连接; 继续阅读

使用 std::map 查找 IP 范围

阅读更多关于《使用 std::map 查找 IP 范围》

给定这样一个问题:

有一组从IP范围到地理位置信息的数据,不同地点的IP范围没有重叠,实现从单个IP地址查到相应的地理位置。 继续阅读

对数复杂度的聚集算法

阅读更多关于《对数复杂度的聚集算法》

SQL 有5个标准聚集函数:SUM, AVG, MIN, MAX, COUNT, 一般情况下,这几个函数的时间复杂度至少都是O(n), n是结果集的尺寸。然而,给定表:

继续阅读

解决amule脱机下载问题

阅读更多关于《解决amule脱机下载问题》

新买的廉价路由器,可以脱机下载,但只内置了bt,没有内置amule。先自己装了amule,router上的falsh太小,装不下那么多软件,就装到移动硬盘上,格式化成ext3。 继续阅读

read/write&mmap&aio

阅读更多关于《read/write&mmap&aio》

read/ReadFile 系统调用默认有预读
write/WriteFile 默认是异步写
mmap 使用缺页中断,实现预读/异步写比较困难
aio 对磁盘调度做特殊优化,在随机访问较多时,理论上性能最好(如果操作系统真正实现了aio) 继续阅读

随机数生成算法

阅读更多关于《随机数生成算法》

本文来源: http://www.zhihu.com/question/22818104
见到这个随机数生成算法好几次了,乍看有点鸡肋本来用Math.random()就可以的事。想不清楚为什么他要用9301,49297,233280这三个数字? 继续阅读

C陷阱:判断宏是否等于一个常数

阅读更多关于《C陷阱:判断宏是否等于一个常数》

下面这段代码有啥错误?

 

 

当 ULONG_MAX 未定义时,被判断为假!多么危险的一个陷阱!

增加以下验证即可查错:

 

这个 bug 耗费了我两个小时!

 

popcount & google.sparsegroup

阅读更多关于《popcount & google.sparsegroup》

ubuntu+gcc4.3 ,尝试修改 google.sparsetable 中的 sparsegroup,修改完成,不启用 -mpopcnt,sparsetable_unittest 和 hashtable_unittest 都通过了。启用-mpopcnt以后,发现硬件不支持,报非法指令错误,公司的电脑太烂了! 继续阅读