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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

缓存与平行数组在 hash_strmap 和 gold_hash_map 中的应用

阅读更多关于《缓存与平行数组在 hash_strmap 和 gold_hash_map 中的应用》

2007 年我写过一篇关于平行数组与CPU缓存文章,最近,我在 hash_strmap 和 gold_hash_map 中应用了这种设计思想,有这么几个字段可以使用平行数组: 继续阅读

gold_hash_map vs google sparse map by google’s time_hash_map.cc

阅读更多关于《gold_hash_map vs google sparse map by google’s time_hash_map.cc》

这个列表由我写的一个 perl 程序抓取 time_hash_map 的结果生成。time_hash_map 是 google 自己实现的 hash table 中的一个性能测试程序,我在其中加入了针对 gold_hash_map 的测试,没有其它任何改动。实现原理:缓存与平行数组在…… 继续阅读

hash_strmap 最新性能数据

阅读更多关于《hash_strmap 最新性能数据》

QPS  达到了35,644,397,测试机器就是普通 PC:CPU 3G Hz,内存 2G。

总计500,000 条数据,keylen=32 byte,迭代20次, 总查询次数 10,000,000 次, 耗时 0.280549 秒 继续阅读

gold_hash_map design

阅读更多关于《gold_hash_map design》

前一段时间写了个 hash_strmap, 效果不错,其中的一些设计思想可以扩展。于是,昨天到今天两天写了一个通用的 hash_map, 起了个名字叫gold_hash_map继续阅读

gold_hash_map bench mark with google sparse hash

阅读更多关于《gold_hash_map bench mark with google sparse hash》

This is the testing result with google sparse hash’s bench mark (time_hash_map.cc in google sparse hash’s tar ball)
The only modify to time_hash_map.cc is added the test for gold_hash_map (see diff below) 继续阅读

莫比乌斯带

阅读更多关于《莫比乌斯带》

在学校里,我学到的第一门编程语言,是 Mathematica,严格讲 Mathematica 也许不算是一门编程语言,但它的确很有趣。那个时候(1998年),Mathematica 还只是 1.2 (或者1.4,具体记不清了)了。学校机房的电脑也很慢,但是从那开始,我开始可以将自己的一些想象变成视觉,莫比乌斯带的方程式就是这样想象出来的: 继续阅读

Hadoop.MapReduce.简介

阅读更多关于《Hadoop.MapReduce.简介》

本文是2009年9月为公司内部培训写得的一篇简介。 继续阅读

hash_strmap 为什么那么快

阅读更多关于《hash_strmap 为什么那么快》

测试结果(普通PC,CPU 3G HZ,内存 2G)

  • 单核达到了每秒 30,000,000 次查询,string 长度是 32 字节,这个速度比 unordered_map 快10 倍,比 std::map 快40 倍。
  • iteration 的速度, 比 std::map 快 180 倍以上, 比 unordered_map 快 150 倍。

继续阅读

reverse_iterator

阅读更多关于《reverse_iterator》

stl 容器大都有 reverse_iterator, 用法跟 iterator 一样。然而,可能很少有人考虑过它的实现。

首先, reverse_iterator 大都由 std::reverse_iterator 包装 iterator 生成,如此,同样的遍历循环, 继续阅读

is_trivially_destructible replaced has_trivial_destructor

阅读更多关于《is_trivially_destructible replaced has_trivial_destructor》

C++11 中的 type_traits, 改变了一些约定成俗的名字:

我们经常使用的 has_trivial_destructor, 变成了 is_trivially_destructible, 现在已有不少编译器实现了 has_trivial_destructor, (std, std::tr1). 继续阅读