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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

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,保存了最近一个管道命令中所有子命令的返回值

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

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

my PipelineProcessor

阅读更多关于《my PipelineProcessor》

刚看到,intel tbb::pipeline 实现的功能,和我以前实现的一个pipeline : febird::thread::PipelineProcessor
,介绍:

1. 多线程的 pipeline 设计模式

2. 多线程 Pipeline 的改进

 

几乎就是同一个东西:多线程流水线执行,按次序,stage划分……

可惜啊,它只在我的几个程序中用过,现在有了tbb,它还没来得及壮大就得夭折了。

 

聊以自慰:

    1. 英雄所见略同

    2. 这个轮子很有价值

    3. 发明轮子之前,先多看看

    4. 多看看,碰到问题就免得发明轮子