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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

持久化的 map ,使用 BerkeleyDB

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

使用前面介绍的序列化框架,可以非常简单地将Bekeley DB作为存储层,实现一个易于使用的,强类型的,持久化的map。

这个设计的的基本原则就是:模板作为一个薄的、类型安全的包装层,实现层的代码可以多个模板实例来公用,这样不但加快了编译时间,也减小了生成的代码尺寸。 继续阅读

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

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

迄今为止,我还没找到更优雅、更高效的 C++ 序列化方案,包括但不限于 boost.serialization。如果你发现了更快的,或者更易用的C++原生序列化,请告诉我…… 继续阅读

多线程 Pipeline 的改进

阅读更多关于《多线程 Pipeline 的改进》

 如果一个任务的执行分多个步骤,有些步骤慢,有些步骤快,如果在处理时间长的步骤上使用更多线程,那么因为队列的缓冲作用,在平均处理时间上,这些步骤就可以大致持平了,从而导致更大的吞吐量。

以前的 Pipeline 完全胜任这样的需求,但是,如果有一个这样的需求,考虑如下例子:
有若干篇文章(百万以上),需要对这些文章进行分析并索引,使用Pipeline,分成以下步骤:

继续阅读

爱尔兰巨角鹿的死去

阅读更多关于《爱尔兰巨角鹿的死去》
地球上曾经出现了一种鹿,叫做爱尔兰巨角鹿,毫无疑问,它有非常巨大的鹿角。
按照新达尔文注意的解释:在开始的时候,较大的鹿角使得鹿有较强的生存能力,它夺取了第一个高地。后来事情发生了一点变化,雌鹿开始喜欢鹿角巨大的雄鹿,那些鹿角稍微小点的雄鹿,大多不是因为生存不下去而灭绝了,而是因为没有雌鹿和它交配而没了后代。然后,鹿角就越来越大,以至于大得对它来说是巨大的负担,让它承受不起,但是,为了能够得到母鹿,鹿角还在不停地长大。
为什么母鹿会喜欢大得夸张以至于毫无实用性甚至是有害的鹿角呢?道金斯给出了一个非常合理的解释:固然小鹿角的雄鹿的生存能力和大鹿角的雄鹿一样强,但是,正因为鹿角已经成了一个负担,负担得起大鹿角的,当然更强壮一点。就如同背着沙袋跑步的人,和轻装跑步的人,如果跑得一样快,当然是背着沙袋的人更强壮。
于是,鹿角就成了一个纯粹形式化的竞争热点。
现在,软件越来越复杂,但是大家可以发现,更多的复杂性不是因为它提高了大家的工作效率,而是它看上去更漂亮。对大家的工作效率一样的软件,如果看上去更漂亮,它就取得了优势,于是它就更加趋向于为了漂亮而复杂。以至于我们整天骂它华而不实。在这种情况下,就是进化史上的“进化稳定”阶段,因为环境的稳定,生物没有实质性的进化。然而,环境不是永远稳定不变的,在环境的骤然变化下,就是那些华而不实的特性消亡之日,拥有那些特性的生物如果不懂得变化,就会灭绝。
这些年,桌面软件实际上就是处于这种稳定阶段,然而,这种外显的特征,其实只是基因型的极小部分的显性体现,那些没有外显出来的基因型,一直待在那里等待机会。只要机会来临,历史就将重写。

语言进化的推动力

阅读更多关于《语言进化的推动力》

 

最近又读了一些进化论。联想到当前,最有潜力和最有影响力的几种计算机语言:C/C++Java.NetD,当然其中.Net不是单一的语言,而是一个多语言的平台。其中D语言大家相对比较陌生。这里我要重点说的是C++D

先说C/C++

虽然C++C有很大的差异,但我还是要把他们放在一起,因为它们的很多共同的优缺点。先说优点:

C/C++历史悠久,有广泛的支持平台、的现有库、用户基础、性能就更不用说。但是它们有缺点,很致命,就是开发效率低。虽然使用现代C++在很大程度上改善了开发效率低下的问题。但是C++相比于C还有另外的缺点:

1.         学习难度高!以至于大家经常说,搞了5C++,不敢说熟悉C++,更不敢妄谈精通了。对于有相当功底的C++开发人员,也经常出错。

2.         编译时间长。这主要归因于对C预处理器和语法的兼容,现代C++程序,一般都使用相当大量的模板,这使得编译时间不可接受。一个简单的spirit语法分析器,仅一个源文件,在2.4G双核至强4CPU的服务器上编译,超过一分钟。更不用说使用模板无法保密源码。

3.         当前(C++0x之前)的C++,对模板元编程的语法支持非常差,boost.mpl的那一套虽然解决了问题,但是相当丑陋。

 

这几个缺点在D语言中基本上不存在,主要是因为D语言是新设计的,并且它完全抛弃了C++:“对C尽最大可能兼容!”的设计思想。虽然它没有对C做最大可能的兼容,但是它仍然可以有效地与C进行合作,这在链接层次上完成,功能上有点类似于C++上的extern “C”

 

需要思考的是,C++发展至今,经过了很多的演化,几乎在每一次重要的演化中,它新加的特性都得到了后来设计者都无法预料的发展和应用,最突出的就是,最近几年的模板元编程发挥出的巨大威力就是当初设计者完全没有预料到的。当第一份模板递归程序证明C++模板语言是一个图灵完备语言的时候,大家只是把它当作一个纯理论上的东西,从来没有想到它后来会在实际应用中有那么巨大的作用。就如同当初爱因斯坦发现时,没有预料到后来会有原子弹一样。

 

这里值得一提的是,为什么会出现这样的现象?复杂性理论告诉我们,当事物的复杂程度达到一定等级的时候,它的演化就会脱离它的设计者最初预订的目标。比如在生命诞生之初,在原生营养汤里面,有机分子终于因为某种原因随机合成了第一个有复制能力的复杂分子。在之后,一切的发展都显得那么自然而然。但是,这里有一个关键,就是在“那个东西”的复杂程度达到那个阈值之前,它的发展是非常缓慢的,甚至在达到那个阈值之前它就已经消亡了,实际上大多数情况都是这样,只有少数能越过那个门槛。

对于有生命的事物,越是有活力,越是复杂,它的变异点越多,它能产生的可能性空间就越大,从而有可能最终成功地越过门槛的概率就越高,当然它也必须有很大活力。这两点也许是相互依存的。

当然,这里的“有生命”,指的不是我们通常意义上说的生命,而是它的一个延伸。

看来,C++今日的成功,我们要归功于它的复杂。而不是单纯把它的失败归因于复杂。继续举boost.mpl的例子,因为当初C++模板的设计不是为了元编程,仅仅是为了更好地支持stl,更好地支持静态分派。因此,没有元编程中大概是最重要的一个功能:variadic template,这使得mpl.vector/mpl.map/bind/function/tuple等等的实现很难处理,需要写很多个仅仅是参数数目不同的偏特化版,这是个很繁琐无聊的工作。幸好,有人发明了boost.pp,使用最原始的C预处理来完成这个工作。结果当然是好的,boost.pp虽然比boost.mpl更丑陋,但是比起一遍遍地重复相同的代码要好得多。

从这里我们可以看到,冗余的,累赘的功能怎样发挥了它的能力。对C预处理语法的兼容一向被认为是C++最大的一个累赘,有很多人提出很多不同的惯例和方法来最大化避免使用C预处理语法,比如用inline代替带参数宏,用import(比如VC扩展允许import)代替include,用编译时常量代替宏常量等等。这些惯例和方法的确在某些方面解决了问题,规避了C++的缺陷。但是,假如C++98把预处理完全从语言中剔除,那么,在进行模板元编程时,就只能一遍又一遍地敲入重复代码,或者写出完全lisp式的代码如list<int,list<float,list<string,list<long> > > >,这比起list<int,float,string,long>如何?前者完全可以浇灭掉任何人对list的热情,而实现者要完成mpl.list,就只能重复一大堆一大堆的冗余代码,而这会浇灭实现者的热情。其结果就是,mpl仍然只停留在理论阶段,任何实际的需求都不会被发掘出来。template meta programming也只停留在理论阶段,我们现在使用template也仍然停留在“不同类对象的容器”阶段。

现在说D语言,它基本上是一个“大杂烩”式的语言,几乎所有主流语言的功能,它都实现了。它放弃了对C的语法级兼容,但是它仍然不抛弃“native code”这个设计思想,原则上它的所有语法和语义只为生成本机代码而优化。就是说,它的语法不是“为虚拟机代码而优化”,当然,理论上也可以生成虚拟机代码,但很难优化。也就是说,D语言在本质上只是一个“更好的C++”,最多,只是比“目前的C++”更好。它比C++简单,但同时也失去了C++复杂性中的变异性可能,它只能在C/C++的这个进化方向上更好。如果它想要更广泛的应用,就需要有更多变异点,在基本的设计原则上,不能和C/C++的重合太多,以防止变异的可能性空间被限制。

现在说Java/.Net,它们在本质上比较相像,都是为虚拟机而优化。而一旦有了虚拟机这个中间层,很多为本机执行而优化的可能性就失去了。我们可能在高层使用更广泛的指令集,而虚拟机这个中间层的指令集是固定的,它无法识别更高层指令集的优化。比如,我们为了优化视频解码程序,在C/C++中可以使用intrinsic,或者buildin function,它们把函数调用直接映射到CPU指令,这样,不使用汇编语言就可以使用如MMX/SSE/SSE2/3DNow等增强的指令集。而使用虚拟机,怎样实现?那就只能增加虚拟机的指令集。

WinApi 参数的层次

阅读更多关于《WinApi 参数的层次》

泛型就意味着代码膨胀?

阅读更多关于《泛型就意味着代码膨胀?》

我所了解的泛型实现,也就C++和Java,C++靠的是用代码膨胀来满足性能,Java泛型则只是一个Sugar。

现在使用C++泛型的人越来越多,生成的程序体积也越来越大。一个对10种数据和10种算子使用了泛型算法的程序,代码膨胀的最大可以达到100倍。但实际上,生成的代码“很模板”。现在的C++还没有C++0x 的 closure/auto 等功能,代码膨胀已经达到了很恐怖的程度。——比如使用了 Boost.asio 的程序尺寸就很恐怖。

现在,代码膨胀虽然已经是一个很引起大家注意的问题,但是还没有让大家足够注意。虽然有一些减少代码重复的技巧,但那只是技巧而已,对问题的映射不是很直接,有一定难度,不能得到大范围的应用。可以预见,等到C++0x出世,泛型的语法更加优美,使用更加方便,大家的积极性更高,到那时,代码膨胀可能会成为一个非常残酷的现实问题。

应该有一些途径减少代码膨胀,现代的虚拟机(例如Java虚拟机和.Net虚拟机)可以通过动态优化来提高程序性能,先在运行时解释执行ByteCode,当发现某段ByteCode的执行频率太高时将它优化成NativeCode,这是一种很好的解决方案,虽然在解释执行时增加了程序计数的开销,但这是微不足道的。静态编译语言如C++能否吸收它的优点呢?

我觉得也许可以,但是代价可能比较高。比如对同一个泛型算法实例化100次时,是否可以只生成一个内部框架,而在运行时,用到了哪个实例,再实例化那个泛型算法,也就是运行时由RuntimeEnv按需动态生成NativeCode,而不是在编译时一次生成。对于泛型类型,也类似。实际上,也许有些泛型算法的实例根本不会在执行路径上出现,但是静态编译却必须为它生成代码。

 

vista 中网上银行不能用的 bug 解决方案

阅读更多关于《vista 中网上银行不能用的 bug 解决方案》

我碰到过这个问题,一开始我把工行的网站加入“可信站点”区域后,可以用了,但是过了一段时间(安装了一些Windows更新后),又不能用了,也还是不能用网上银行,总提示“the "my" store could not be opened ”,到“可信站点”中看,工行的站点仍然在啊!不知道微软哪根筋抽了!不过现阶段,人家再抽筋,我们也必须跟着人家也抽筋,要不就别用网上银行!

这个问题困扰了好久,每次我都是使用管理员权限打开 IE 再重新粘贴网址来付款,有时候这种方法还不能用,比如在其他(非阿里巴巴旗下)网站使用支付宝付款时。

气愤之下,曾经到一个论坛大骂IE,大骂微软那帮傻.逼。但是骂也没用啊,那帮傻.逼也不会给你来解决这个问题。刚才一狠心,使用注册表监视器,终于发现了问题!也找到了解决方案,其实很简单:

删掉:HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Internet Settings/ZoneMap/Domains

再重新在 IE 安全设置中加入你的站点。——直接在安全设置中删掉再重新加入是不行的,微软的那帮傻.逼不知道那根筋抽风了!

到此结束一切痛苦!

多线程的 pipeline 设计模式

阅读更多关于《多线程的 pipeline 设计模式》

一个简单例子:有很多个html网页,网页的id、title、url、path等信息存在一个数据库表中,网页内容存储在一个磁盘阵列上。现在要把所有网页都读出来,统计其中的html标签、正文等信息,并写入另一个数据库表,怎样的设计最好呢? 继续阅读

C++ 的缺点

阅读更多关于《C++ 的缺点》

C++ 现在最时髦的用法是 template meta programming。booster 们对此非常津津乐道,我本人也是个狂热的booster。到了什么程度?不使用template 就浑身不舒服,不boost一下就感觉对不起C++。但是这种狂热带来的严重后果就是程序编译速度极慢无比,生成的执行程序尺寸超常。

曾经一个 C++ 服务器程序,代码也就10000行左右,编译出来的执行程序竟然20M!编译时间半小时!写的时候感觉不到用了多少template,但是写出来竟然得到这样的结果,不得不让人吃惊!

记得在大学的时候(2000年前后),初学习 template 时,感觉template之间的耦合有点“过于松散”,就像只要有一个螺母,再一个螺栓,就可以往一起套,而不管他们是否一个是塑料,一个是金属,大小粗细是否匹配,螺距是否匹配,所有的这一切,如果只有哪怕一点点不匹配,都会在编译错误中造成一个非常令人费解的超长消息。当初也不知道这一点早已被无数人诟病了,就写了一片文章,自作聪明地提出应该对模板参数有个类似接口声明一样的规格定义(现在C++0x 中的对应物是concept)。当初立即招致骂声一片。现在这一点已经毋庸置疑了,C++0x出世后我们就可以结束这些痛苦了。

但是,前面说的C++的那两个致命缺点,看来短期内很难克服。

编译时间,受制于文件包含这种古老的内存不够用的时代的无奈选择,就像人的阑尾,喉头,视网膜。

程序尺寸,这个缺陷在某些时候也非常致命,举个简单例子,std::sort 使用了多种排序策略,每个sort 的机器码都很大。同时,对每一种数据类型,每一种randiter每一种comparator,都会生成一个sort 的版本,这会造成非常大的代码膨胀。相比之下,C 的 qsort 就没有这种缺陷。如果我们对几十种数据,使用几十个comparator排序,std::sort 的代码尺寸比 qsort 要大几十倍。虽然它在inline方面获得了优势,但是cpucache的失效,甚至是memcache的失效,造成的性能损失要大得多。BS在TCPL中提到的消除代码膨胀的方法,在某些情况下的确有用,但是太繁琐,大约也只有库编写者会使用它。

Java现在也支持泛型,据说不存在代码膨胀问题,但它的泛型只是语法糖,对程序性能好像没有提升。

C++ 怎样平衡代码膨胀和代码性能?是否可以为 template 生成 runtime meta info,用来操纵泛型算法。或甚至使用这些meta info 来在运行时生成真正的机器码。这样甚至可以允许在运行时进行template组装,而不是完全在编译时?这又有些类似于现代虚拟机(如Java HotSpot 虚拟机)的动态优化。

扯太远了,休息下。