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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

文章简介最多240个字符

阅读更多关于《文章简介最多240个字符》

忽然以前文章中有个笔误, 打算修改一下, 修改好了, 提交, 结果被提示:

文章简介最多240个字符, 你已经有输入了247个!

可我无论如何找不到 "文章简介" 的输入框! 难道是 IE Only 的?

HashMap<string, …> 能有多快

阅读更多关于《HashMap<string, …> 能有多快》

看到很多使用 map<string, ….> 的代码, 也有一些使用了 unordered_map<string, …> 或者 hash_map<string, …>, 当然, hash_map 不是标准的, unordered_map 也只在 boost, tr1 和 c++0x 中可用. 从代码的简洁性和可移植性上讲, 标准的 std::map 是首选. 继续阅读

怎样让C++函数重载时连返回值类型也加入重载决议?

阅读更多关于《怎样让C++函数重载时连返回值类型也加入重载决议?》

众所周知,C++函数重载时返回值是不参与重载决议的, 也就是说: 继续阅读

Large Number of Coroutine is possible: Split Stacks in GCC

阅读更多关于《Large Number of Coroutine is possible: Split Stacks in GCC》

本文来源:http://gcc.gnu.org/wiki/SplitStacks

注:GCC4.6 已经支持 -split-stack 选项。Why Fiber/Coroutine?  可参考我的相关文章:异步通讯中使用纤程(Fiber/UserSpaceThread) 继续阅读

排列的分解

阅读更多关于《排列的分解》

离散数学里面大家都学过群,群里面有种很基本并且很重要的叫做置换群,置换群的元素本质上就是一个排列(英文 permutation group, 直译过来应该是排列群)。大家应该都学过当初要把 (4 1 5 2 3) 分解成 (1 4 2)(3 5),这个叫做群的 k-cycle 分解,也就是说,一个排列(置换群的一个元素)可以 继续阅读

穷举搜索

阅读更多关于《穷举搜索》

对于一些困难的问题,我们只能穷举(brut force)搜索,是的,我们知道“穷举搜索”这个词,可是,具体怎么穷举呢?

很多问题可以归结到图的搜索,对于图的搜索,大家应该都知道 DFS 和 BFS, 继续阅读

第一个博弈程序

阅读更多关于《第一个博弈程序》

甲乙两人在玩一个游戏:一堆小石子,共n个,每次每人可以从中取1个,或2个,或4个,甲先开始,最后取的那个人输(不管他去1个,还是2个,还是4个)。

但是呢,甲乙两个人都是智力超群的天才,他们总会使用对自己有利的策略。 继续阅读

合并两个有序序列

阅读更多关于《合并两个有序序列》

经典写法

合并两个有序序列,太简单了吧?还有专门讨论的必要吗?

这是一个最简单的 Merge 版本: 继续阅读

Great Windows 7

阅读更多关于《Great Windows 7》

Windows 7,打开“下载”文件夹,里面也就几十个文件……

它非常“友好”地在地址栏部分显示一个进度条,等到进度条100%,右边文件夹内容部分变成非空白——文件显示出来,我可以去拉泡屎,再回来也不迟,我没有拉肚子,我便秘! 继续阅读

枚举变量扩展-2

阅读更多关于《枚举变量扩展-2》

前一篇文章里,可能有人注意到了:扩展结果中会出现同一变量的不同实例,如果我们要增加一个限制,扩展结果中每个变量都必须引用相同的实例,该怎么做?