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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

boost 这帮人也超级不靠谱

阅读更多关于《boost 这帮人也超级不靠谱》

刚才开始用 boost::range,就查看了了一下 boost 源码,发现 boost-1.50 一个 bug,觉得应该在新版中已经修改了,下载了最新的 1.54 版,进去一看,bug 仍然在! 继续阅读

把自动机用作 Key-Value 存储

阅读更多关于《把自动机用作 Key-Value 存储》

这篇文档只关心 有穷状态自动机 ,不讲具体的算法,对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库,怎样使用自动机 API 访问 KV 数据库…… 继续阅读

原地排序-更简洁的算法

阅读更多关于《原地排序-更简洁的算法》

在我以前的这篇