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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

一个很难的字符串问题

阅读更多关于《一个很难的字符串问题》

有 n 个 RegEx (正则表达式),标号从 0 到 n-1,n 可能很大 (比如说100万)。

问题:给定一个字符串,返回能 match 这个字符串的所有正则表达式标号。 继续阅读

m 分查找

阅读更多关于《m 分查找》

一个比较产生两个决策结果,二-决策的计算机硬件实现更高效。

我们可以想象给一个 array, 一个 key, 在某台 god machine 上有一个操作:cmp-multi  array, key, n, m

继续阅读

Name lookup take place before access control

阅读更多关于《Name lookup take place before access control》

Yes, "1." is a floating point number.

hash_strmap & gold_hash_map update

阅读更多关于《hash_strmap & gold_hash_map update》

hash_strmap

在不增加任何额外成本的情况下,string pool 中每个 string 消耗的内存,平均情况下,减少了一个字节。太不值一提。 继续阅读

How do I disable video thumbnails in Windows 7?

阅读更多关于《How do I disable video thumbnails in Windows 7?》

How do I disable video thumbnails in Windows 7!

禁用 视频 缩略图 windows 7 继续阅读

linux kernel 中的二叉树搜索 与 stl 相应物的对比

阅读更多关于《linux kernel 中的二叉树搜索 与 stl 相应物的对比》

Linux kernel 中也使用并实现了红黑树,但是查找算法没有自己实现,而是希望使用者去实现。如果只是实现一个精确查找的函数,这很简单,几乎每个人都能写出正确的代码: 继续阅读

C++ Question: using

阅读更多关于《C++ Question: using》

下面这段代码,运行结果会如何呢?

  • A. B::f
  • B. #1 编译错
  • C. #2 编译错
  • D. #3 编译错

C++ 2-phase lookup

阅读更多关于《C++ 2-phase lookup》

This 2-phase look up of g++ (gnu C++) seems not inconsistency: builtin types are not treat equivalent with user defined type. 继续阅读

小技巧,大智慧:%n of sscanf

阅读更多关于《小技巧,大智慧:%n of sscanf》

scanf 系列中有个函数 sscanf,可能有人用过,它的普通用法,我就不讲了,可以参考这里:man 3 sscanf

gnu c 实现了 C 标准的 format specify 的 %n,它的含义是返回从该次 XXscanf 调用开始到此读了多少个字节,我们可以利用这一点,来实现不需要内存分配的%s继续阅读

忽悠,也是一种学问

阅读更多关于《忽悠,也是一种学问》

我看了一下我最近几个月的博客浏览记录,发现这篇的访问量最高。然而这篇文章里面提到的东西虽然有我这么多年编程生涯中的一些总结,但总体上没有太多实在的东西,缺乏可操作性继续阅读