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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

关于变量名的一点感想

阅读更多关于《关于变量名的一点感想》

变量的命名规则,一般有这么几种:

1. 骆驼规则,如 Windows Api 的命名规则(CreateFile/GetDiskFreeSpaceEx),Java 类名的规则 

2. 首单词小写,如Java方法名(readByte)

3. 下划线分隔单词,如C++标准库(lower_bound/equal_range)

4. 全部小写,无分隔,如unix(posix)的很多函数名(getpagesize),但这类大部分使用所写(mmap/sysconf)

5. 骆驼规则再加下划线,ACE使用这种规则(ACE_Event_Handler )

6. C 宏名命名规则,一般是全部大写,再加下划线(BOOST_CURRENT_FUNCTION/BOOST_STATIC_CONSTANT)

7. Windows 中使用一个变种,全部大写,类别前缀加下划线,再加单词连写(WM_ACTIVATETOPLEVEL)

8. 全部大写,无分隔,如Windows中的结构名

 

这几种规则,我个人认为最坏的是【8】,然后是【7】,全部大写不加单词分隔很难辨别(单词界线)。【3】在名称比较短时还行,这类名称一般也的确比较短。

这几种命名规则,我个人觉得都不太好,主要是在视觉是感觉不好,以下就举一些反例(最被大家看好的):

【1】. GlobalAllocReadFile,单词的分界在视觉上感觉不舒服,主要是以f/l/d/作为分界时,和下一个单词的首字母大写有些混淆,【2】的缺点跟【1】一样。

【3】. 下划线分隔,有时略显啰嗦,如getpage,就比get_page,来得简明舒服一些

 

最便捷、最强大、速度最快的C++序列化框架【二】

阅读更多关于《最便捷、最强大、速度最快的C++序列化框架【二】》

目前该框架(DataIO)仅支持二进制。想起序列化支持只需要两个宏 DATA_IO_LOAD_SAVE / DATA_IO_LOAD_SAVE_V,对象成员基本上用“&”连接起来,这样,可以写一个简单的语法分析器,在序列化宏中将成员序列化表达转化成字符串, 继续阅读

Coroutine真的可以大幅提高效率吗?

阅读更多关于《Coroutine真的可以大幅提高效率吗?》

 这段时间一直想用Coroutine来实现我的rpc中异步调用的分派。看了很多Coroutine的资料,感觉它比起线程切换,就是少了个内核调用,少了自动激活,以及一些内和支持的线程状态(errno,tls等)。在处理器状态的存储/恢复,堆栈的切换等方面的开销都是一样的。在x86这样的体系结构下,处理器的状态(寄存器状态)很少,就那么几个寄存器,存储/恢复起来很快。但是,象MIPS,甚至Itanium这样的体系结构,他们的寄存器很多,Itanium甚至有128个64位的寄存器,这样,光寄存器状态就要1024byte!存储/恢复的开销很大。

有时也想,在没有Coroutine的普通函数调用中(不需要切换堆栈),编译器可以使用一些寄存器分配算法,来有效利用寄存器。如果在语言支持的Coroutine中,是否可以通过类似的方式减轻Coroutine切换开销?

使用C++模板实现不需要IDL的RPC【二】

阅读更多关于《使用C++模板实现不需要IDL的RPC【二】》

严格讲,是不需要专用的 IDL 语言,传统 RPC 的 IDL 语言 相应的部分 在这里全部是 C++ 语言本身,也可以把它称作 IDL,是由几个宏实现的: 继续阅读

process–>thread–>coroutine

阅读更多关于《process–>thread–>coroutine》

在现实世界中,基本是是按着这样的顺序演化:process–>thread–>coroutine/fiber

其实是一个context切换开销从大到小的演化,process切换开销最大,需要切换地址空间,所有的CPU状态,所有其他资源

thread切换只需要切换CPU状态,当然是大部分的CPU状态,而coroutine切换,只需要切换很少的CPU状态,而且全部都在用户地址空间运行,不需要到内核空间。

当然,切换coroutine的开销还是比一次函数调用大很多,其实函数调用也是一个cpu状态的切换,不过这个状态要少得多,在x86 windows 上,甚至不必保存所有的寄存器状态(EAX/ECX/EDX在函数调用之间就不用保证,EAX保存返回值),有些调用甚至通过寄存器传递参数……比起coroutine,太微不足道了。

coroutine其实也可以看成是一个保留了以前调用状态(另一个堆栈帧)的函数调用,在寄存器很多的系统上(如Itanium),切换寄存器状态的开销还是比较大的,如果哪一天大家又开始嫌coroutine也太慢,那怎么办?

about boost::shared_ptr

阅读更多关于《about boost::shared_ptr》

boost::shared_ptr 对象中,有两个成员一个是对象 ptr,一个是引用计数类的指针,由于某种原因,我希望把 shared_ptr 放入一个指针大小的地方,却无法实现,只能用 intrusive_ptr,但是牵涉到的类又太多,改起来不现实,仔细想一下,其实 shared_ptr 完全可以只有一个指针大小,只要把对象指针放到引用计数类中就可以了,为什么shared_ptr作者不这么干?是他没想到?我觉得不太可能。或者只是为了减少一次内存访问?我觉得也不太可能。这到底有什么更深层次的原因?

原来Fiber就是Coroutine

阅读更多关于《原来Fiber就是Coroutine》

  前段时间自作聪明的还以为自己发现了一个完美的解决异步IO的方法,还真太把自己当回事了。人家已经早有这个办法了,还有个学名,叫做Coroutine,在异步IO中的应用也已经非常多了,我真是太孤陋寡闻了。

老外真严谨

阅读更多关于《老外真严谨》

刚才看coroutine,在这个页面

 

感觉最有意思的是这一段话:

(The header file is MIT-licensed, so you can use it in anything you like without restriction. If you do find something the MIT licence doesn’t permit you to do, mail me, and I’ll probably give you explicit permission to do it anyway.)

异步通讯中使用纤程(Fiber/UserSpaceThread)

阅读更多关于《异步通讯中使用纤程(Fiber/UserSpaceThread)》

在异步通讯中,一般使用一个线程来select/poll/epoll,收到信号后,解码消息头,或者整个消息,然后将相应的fd交给其他线程处理。这看上去的确是个很好的办法,但是…… 继续阅读

持久化的多键映射,使用BerkeleyDB

阅读更多关于《持久化的多键映射,使用BerkeleyDB》

如前介绍,相当于 std::map<Key1,std::map<Key2,Data> >,但接口也不完全相同,这里只贴代码: 继续阅读