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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

popcount & google.sparsegroup

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

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

google.sparsegroup 可以更好

阅读更多关于《google.sparsegroup 可以更好》

sparsegroup 是 google.sparseXXXX (sparsehashmap)系列中最底层的一个数据结构,sparseXXX 的互相依赖如下: 继续阅读

google.tcmalloc 要点

阅读更多关于《google.tcmalloc 要点》

线程缓存(thread cache)

加锁(locking)

加锁的开销是比较大的(cpu要同步 cache),一般要几十个时钟周期,特别是 cpu 较多的时候,锁冲突概率大大增加。 继续阅读

这样反贪如何?

阅读更多关于《这样反贪如何?》

类似于囚徒困境,立这样一条法律:行贿者保留自己向受贿者行贿的证据,事后告发该受贿者;对于该告发行为,法律严惩该受贿者,而该行贿者不受任何处罚继续阅读

google.sparsetable 实现细节

阅读更多关于《google.sparsetable 实现细节》

与现有的一些“标准”实现不同,sparsehashtable 使用二次探测法,而不是链接,来解决hash冲突。sparsetable 就更奇特了,它是一个两级结构,第一级使用直接索引法,而第二级使用的是顺序查找
继续阅读

gcc 4.5

阅读更多关于《gcc 4.5》

只拣一些有用的:
The -fshow-column option is now on by default. This means error messages now have a column associated with them. 继续阅读

终于可以优雅的捕获 shell heredoc 内容了

阅读更多关于《终于可以优雅的捕获 shell heredoc 内容了》

看下面的示例: 继续阅读

shell heredoc 微妙之处

阅读更多关于《shell heredoc 微妙之处》

here doc 的一般用法是:

[cmd] <<word
here-document
delimiter

继续阅读

通过管道向 hadoop put 文件

阅读更多关于《通过管道向 hadoop put 文件》

使用 hadoop file shell 可以方便地向 hdfs put 文件,但是,该 shell 不支持从管道读取数据并放到 hdfs 文件中。它仅支持这样的 put 命令: 继续阅读

shell 中验证管道是否正确执行

阅读更多关于《shell 中验证管道是否正确执行》

象这样的 shell 代码:  prog1 | prog2 | prog3 | prog4

$? 只能得到最后一个命令的返回值,该 如何检查整个命令是否全部正确执行?

有一个数组变量PIPESTATUS,保存了最近一个管道命令中所有子命令的返回值

该返回值与 $? 一样,每次命令都会改写它,因此,要保存它就必须马上!

用以下代码可以检查管道命令: