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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

简单的代码生成器创建领域语言

阅读更多关于《简单的代码生成器创建领域语言》

有一类问题,代码模板相同,但有少部分地方不同,一般可以写一个复杂的程序,使用不同的选项,完成不同的任务。或者,把公共的部分抽象成一个代码库,然后在不同程序中引用。但是,如果公共的部分很少,并且比较“专用”,或者因为其它原因,比较难以部署。怎么办?

实际上,有另一种完全不同的编程模式来实现:代码生成器。unix世界中最知名的代码生成器莫过于lex和yacc了。但是,不比每个代码生成器都那么复杂,比如这个代码生成器就非常简单,它只是简单地转换行记录:

 

可以象awk一样写程序:

 

我当初写这个生成器的原因是发现非常简单的 awk 程序也比 C 慢 40 倍,以为这是本质上的性能差距,后来才发现不是

 

对这个简单的程序,使用awk更方便更安全,也不比C慢,但是一旦碰到其它类似问题而 awk 解决不了,这种模式就可以派上用场了。

LC_ALL=en_US.UTF-8 让 awk 慢了 40 倍!

阅读更多关于《LC_ALL=en_US.UTF-8 让 awk 慢了 40 倍!》

  无意中发现,在一台服务器上,非常简单的awk程序,比C的等价物要慢40倍,感觉有点不太正常,还以为的确是awk太慢。不得其解,到另一台服务上试了一下,相同的 awk 程序,相同的测试数据,这台服务器的速度与C相当,也就是说,同样是awk,两台机器速度差了 40倍,而两台机器配置基本相当。非常困惑,找了两小时的原因,终于发现gawk手册里面有一段话:

For other single-character record separators, using ‘LC_ALL=C’will give you much better performance when reading records. Otherwise,gawk has to make
several function calls, per inputcharacter to find the record terminator.

再看两台机器的 locale,结果发现,慢的机器上:

[root@slow-server]# locale
LANG=en_US.UTF-8
LC_XXXX=en_US.UTF-8


LC_ALL=en_US.UTF-8

快的机器上:

[root@fast-server]# locale
LANG=en_US
LC_XXXX=en_US


LC_ALL=   <空>

马上试验,将slow-server的locale改掉:

export LC_ALL=C

速度马上快了40倍,与fast-server相当。

 

这应该是awk实现上的一个缺陷,即便是对utf8,也不应该慢这么多,如果缓冲合适,最多慢2~3倍就可以了,为什么非要gawk has to make several function calls,
per inputcharacter

count, sum, avg by range in log(n) time

阅读更多关于《count, sum, avg by range in log(n) time》

考虑一下这样一个查询:

select count(*), sum(tax), avg(weight)

  from pepole

where id >= ${minid} && id < ${maxid};

 

怎样才能实现更小的时间复杂度?

 

一般情况下,最简单的方法就是遍历这个区间。但是这需要O(logn +m)的时间复杂度,其中m是区间长度,n是总记录数。

 

实际上,可以略增一点存储代价,对该查询实现O(logn)的时间复杂度。我以前写过一篇文章
,可以对count(*)实现logn复杂度:

  count(*, minid, maxid) = rank(maxid) – rank(minid)

其中,rank(id) 表示该记录在整个表中的序号(排序名词)。这很容易理解。

 

如果要计算sum(x)或avg(x),需要扩张一下,在每个结点中存储一个隐藏值,用来表示该以结点为根的子树的sum(x)值,那么,插入/删除/修改的代价也是O(logn),计算sum(x),avg(x)的代价也是O(logn)。

 

 sum(x, minid, maxid) = node(maxid).hidesumx – node(minid).hidesumx

 avg(x, minid, maxid) = sum(x)/count(*, minid, maxid)

 

BekeleyDB中,可以实现 count(*) 的log(n)时间复杂度,因为它提供了类似rank()函数的功能,使用btree表,建表时提供DB_RECNUM标志。查询时,使用DBC::get,用DB_GET_RECNO flag:

 

MapReduce应该做更少的事情

阅读更多关于《MapReduce应该做更少的事情》

MapReduce 做的事情太多了。相比 unix 思想,它更多的是提供了一种策略(Policy),而非一种机制(Machanism)。

对于并行计算,如果我仅仅需要一种机制,暂且把这种机制叫做S,那么S只需要提供: 继续阅读

字符串基数排序

阅读更多关于《字符串基数排序》

  对字符串使用基数排序,以前,我一直觉得:因为字符串的长度不一,无法使用基数排序。前两天因为有需要,忽然想通了!即便长短不一,也可以使用链式基数排序!

  首先,将字符串长度当作最低有效位,因为基数排序是从最低有效位开始排的,就先用分配-收集算法对长度做一趟。对字符串中的具体某一位字符进行排序相比,算法是一样的,只是写法稍有不同。要将排序结果的lenRadix指针保存起来,后面要用。

  接下来,从lenRadix中取字符串最长的那个sublist,对该sublist排序,然后将这一趟的结果first保存起来,连接到长度次短的那个sublist之后,然后对这两个链接起来的列表进行一趟分配-收集。如此,直到最高有效位。

  所有的工作就做完了,根据此算法,对所有待排序字符串中的每个字符,均需要一次且仅一次访问!另外,还需要
O((radix+1)*max_str_len)的时间复杂度用于扫描链接表,(radix+1)是因为还有一个strlen链接表。所以,总的时间复
杂度是O(n+(radix+1)*max_str_len),其中N是所有字符串的总字符数。

  在排序过程中,可以插入一个codetab,来实现不同的排序准则(例如忽略大小写),如果提供了wchar_t codetab,就按 wchar_t 排序,如果wchar_t codetab 非 NULL,就按转换了的 wchar_t 排序。

  如果对unicode排序,最好指定一个codetab,把radix变小,不然的话,时间复杂度就太大了!

  经过测试,在大约20000~30000个字符串的情况下,比std::sort快5~7倍。数据规模再增大,至5,000,000个字符串时,比std::sort大概快1.8~2.5倍!

 

代码:

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.cpp

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.h

 

测试(bench mark)代码:

http://code.google.com/p/febird/source/browse/trunk/febird/codelite/RadixSort/main.cpp

MultipleInputs/MultipleOutpus

阅读更多关于《MultipleInputs/MultipleOutpus》

仔细看了一下 Hadoop.MapReduce 的代码,发现了两个新类:MultipleInputs/MultipleOutpus,再仔细看它们的详细文档,的确实现了我想要的功能继续阅读

地下军工厂大造“山寨”武器

阅读更多关于《地下军工厂大造“山寨”武器》

很多所谓互联网高科技,与这山寨军工厂有何异?

 

本报特约记者 章鲁生 《 青年参考 》( 2011年05月20日   21 版)

一家地下军工厂

一名反对派人员身背改造后的AK-47冲锋枪,在米苏拉塔市街头巡逻。

利比亚反对派和政府军的武装冲突已持续了两个多月,据美国《纽约时报》报道,反对派武装的武器装备可谓五花八门,拆卸下来的机载机关枪、世界大战时期的“古董枪”甚至牛排刀等,均被派上用场。但即使如此,武器依然短缺。

为了让更多的志愿者拥有武器,在反对派武装控制的利比亚西部城市米苏拉塔,一些地下军工厂(或许叫“地下作坊”更合适)开足马力,因陋就简地为反对派制造各种“山寨”武器。

“古董枪”没子弹,不如一块石头

迄今为止,利比亚政府军已围攻西部城市米苏拉塔长达8个星期。对反对派来说,米苏拉塔具有重大的战略意义——这是他们在利比亚西部占领的惟一一座城市。为了保住这块根据地,反对派动用了一切可以动用的“资源”。单从装备上讲,在米苏拉塔街头见到的武器,足以让人眼花缭乱。

最显眼的当属PKT机关枪。这种安装在苏联坦克上的重型机关枪没有枪托,没有准星,也没有手动扳机,全靠坦克车内的人遥控操纵。米苏拉塔的反对派成员只好扛着这种笨重的机关枪。

还有意大利的卡尔卡诺卡宾枪,这种枪或许是两次世界大战期间意大利对利比亚实行殖民统治时期留下的老古董,由于太过老旧,甚至没有配套的子弹可供使用。即使如此,《纽约时报》的记者奇弗斯仍在米苏拉塔街头见到4个反对派成员端着这种枪。

反对派手中的“古董枪”还有法国军队几十年前装备的MAT-49冲锋枪。和卡尔卡诺卡宾枪的情况一样,这种枪也没有配套的子弹。记者奇弗斯因此戏称,拿着一把MAT-49,还不如拿一块石头。

武器杂乱、“古董枪”多的现象,说明反对派武装武器匮乏。

31岁的菲克里·伊塔尤里曾在一辆配备了机关枪的卡车上战斗,后来机关枪和卡车一起被炸毁,他的武器只剩下一把很大的牛排刀,但伊塔尤里信心十足。“好在我还有这个……”他挥舞着那把有锯齿状刀锋的牛排刀,“我想用这把刀扎进卡扎菲的心脏!”

反对派表示,很多人志愿加入他们的组织,但枪支短缺影响了战斗力。

也有一些志愿者带着武器加入。在利比亚东部,一些志愿者花至少2000美元购买AK-47冲锋枪。这些人因此受到关注——等他们在战斗中倒下,就去捡他们的枪。

开足马力制造“山寨”武器

因为武器短缺,政府军围城后不久,米苏拉塔一些由反对派控制的地下工厂便开足马力,因陋就简地制造各种“山寨”武器。

米苏拉塔前线最常见的是加装了钢板装甲、车后载着机关枪的四门民用卡车。这些枪——如前文提到的PKT机关枪——多为冷战时期生产,本来安装在飞机或坦克上,现在反对派把它们安装在民用卡车上。很显然,这些因地制宜的武器都是地下工厂的“作品”。

为防止政府军的奸细搞破坏,反对派把这些地下工厂视为机密,甚少向外界透露。记者奇弗斯软磨硬泡了3天,才于5月2日获准到其中的两家工厂采访,条件是不得向外透露它们的具体地点,也不准拍工厂门口的照片,以免政府军“按图索骥”。

在奇弗斯看来,地下工厂制造的一些“山寨”武器很耗资源,但实用价值“存在疑问”。不过反对派对此不以为然,在他们看来,“只要能把卡扎菲的军队击退,任何花费都是值得的”。

总体来说,地下工厂加强了反对派的力量。此前,一些加入反对派武装的人只能拿着刀甚至石块走上前线,现在他们可以在后方的工厂里挥舞着榔头、举着电焊枪、操纵着车床,让更多反对派战士拥有“货真价实”的武器。

“如果我们一开始就有足够的武器,我也不会在这里了,我会和两个儿子一起在前线战斗,把卡扎菲的人赶跑。”在奇弗斯采访的一家地下工厂里,电焊工艾哈姆德·舍基说。

说话间,外面有炮声传来,震耳欲聋,但艾哈姆德仍动作熟练地把一块装甲钢板焊在一辆卡车上,仿佛没有听到爆炸声。

根本没工夫统计产量

记者奇弗斯看到,艾哈姆德身边堆放着他当天要完成的任务:4辆民用皮卡、产自不同国家的机关枪,还有一堆钢板。他得把这些机关枪安装到皮卡上,并把钢板在车上加固。机关枪太大太长?没关系,用钢锯锯掉多余的部分即可。

在工厂的另一个角落,30岁的奥马尔·艾尔·萨基尔正对着一挺.50口径(12.7毫米)的机关枪发呆,因为这挺机关枪没有扳机。

枪身上的标志显示,这是一挺比利时生产的M3M机载重型机关枪,但萨基尔并不清楚这些。沉思了一会儿,萨基尔终于想出该在哪里给这挺机关枪安装扳机。他制造出一个粗糙的扳机装了上去,一挺机关枪就这样“复活”了。它将被固定在皮卡上,成为夺命利器。

在这家工厂里,除了艾哈姆德和萨基尔,还有两组工人。一组正在锻造武器的旋转座,另一组在把钢板焊到皮卡上。工人们说,在天黑之前,这些皮卡将摇身变为他们的“装甲车队”。

这些即将变身为“装甲车”的皮卡,通常被从头到尾漆成黑色,车尾灯和方向灯也被摘掉。这样一来,政府军很难发现它们的行踪。

当被问及生产了多少辆此类“装甲车”时,这家工厂的车间主管巴希尔·扎尔加尼表示,“不太清楚”。

“太忙了,我们根本没工夫统计产量。”扎尔加尼说。

记者奇弗斯根据在米苏拉塔街头以及前线的所见所闻,认为此类“山寨装甲车”的数量“至少有100辆,很可能在200辆以上”。

生产军火的工人“自学成才”

“山寨装甲车”是反对派地下工厂的“主打产品”之一。奇弗斯曾在利比亚首都的黎波里街道上看到一种被称为“henzab”的武器,也出自反对派的地下军工厂。“henzab”是当地人的俗称,指的是一种铁器。这种铁家伙的大小跟一个棒球差不多,有五六厘米长的刺,若不小心踩上去,鞋底将被轻松刺穿。

与政府军在的黎波里激战时,反对派武装在政府军必经的道路上放了很多“henzab”,迫使他们缩在包围圈里被动挨打,许多政府军士兵被这种铁家伙扎伤了脚,政府军许多车辆的轮胎也被扎破。

在另一家地下工厂里,奇弗斯看到一名工人正在往RPG-7单兵火箭筒的火箭弹里装填炸药。RPG-7是利比亚反对派武装主要的“重武器”之一,能穿透坦克装甲。为了打击躲在建筑物中的政府军,反对派军械师阿里·拉马丹·埃尔加拉贝对这种武器进行了改造。他在火箭弹上加装了较厚的铝套筒,火箭弹击中混凝土墙壁爆炸后,会产生很多碎片,从而杀伤建筑物中的政府军。

“这种火箭弹,我每天能生产30到40枚。”埃尔加拉贝告诉奇弗斯。

和这家工厂的其他工人一样,埃尔加拉贝之前并无生产军火的任何经验,属于“自学成才”。

埃尔加拉贝改造的这种火箭弹,装填的炸药大部分来自军火零售商。为了获取更多炸药,他把缴获的一些炸弹拆开,取出炸药,装填到RPG-7的火箭弹中。让奇弗斯心悸的是,埃尔加拉贝用一个金属工具,而非木勺或木片,从炸弹中舀出炸药。试想一下,如果金属工具与炸弹壳摩擦产生火花……

反对派呼吁北约提供武器援助

美国有武器专家认为,增加弹体的长度与重量将降低RPG-7火箭弹攻击的准确性,尤其是在没有光学瞄准镜的情况下。

记者奇弗斯把这种改造后的弹体照片发给美国一名武器专家,专家看后回信说:“虽然(加装厚铝套筒的想法)很有创新精神,但我认为这样会使火箭弹前部变重,在飞行过程中急速下坠,无法击中目标。”看到工人用金属工具舀出炸药的照片后,这位武器专家告诫奇弗斯:“任何参观者都要避开这种场面。”

这些地下工厂的工人清楚,在不具备任何武器知识的情况下做这些事情是很危险的,但他们“别无选择”,因为每天都会有大量信息从前线传来,要求他们改进某些武器,“时间不等人”。

工人们表示,在“边摸索边实践”的过程中,他们学到了不少武器知识,“每周都有提高”。

一家地下工厂的车间主管巴希尔·扎尔加尼说:“每个人晚上回家都会苦苦思索,怎样才能做得更好?我们必须既快又好地完成工作,因为我们的城市正在遭受攻击,没有太多时间让我们慢慢研究。”

不过,即使开足马力,这些地下工厂的军火产量也无法满足巨大的战场消耗。5月9日,反对派呼吁北约尽快提供先进武器,以扭转不利局面。

5月11日,反对派控制了米苏拉塔的机场,美国国防部援助反对派的首批物资于当日“空降”,包括1万份即食口粮、医疗器械、帐篷、制服、靴子和防弹衣,但没有美制军火。看来,反对派的地下工厂还得努力提高产量。

rdtsc 备忘

阅读更多关于《rdtsc 备忘》

继续阅读

内嵌变长数据结构范例——trbstrmap

阅读更多关于《内嵌变长数据结构范例——trbstrmap》

 

 

以前的这篇文章介绍了嵌入的变长数据结构(embeded

 

本文介绍一个使用这种思想实现的通用strmap容器,相当于:

std::map<std::string, Mapped>

 

实现上使用了我以前写的线索红黑树——相比标准map的实现,节省了一半的结点存储开销,而平均查找时间只付出很小的额外开销,并且没有代码膨胀问题。

 

使用

大多数情况下

trbstrmap<MappedType[, Compare]> // Compare是可选的,allocator 总在类范围,可以修改:

trbstrmap<MappedType[, Compare]>::s_vtab.alloc = ….;

 

为了节省空间,trbstrmap使用一个字节存储strkey_length,因此,strlen(strkey)不可超过255,允许长度为0key。最大长度255基本上可以应对绝大多数情况。

key作为变长字段,有一个原因很重要:key一旦插入,就不可改变!因此,整个结点的memblock也就不需要重新分配,可以修改的只有mapped_data

作为一个比较:如果把key作为一个固定长度的结构,而mapped_data作为变长内嵌数据,当需要修改mapped_data时,就需要重新分配该结点,还需要修改该结点的父节点指向该结点的指针,并且,会破坏“node容器的iterator只有在删除该node以后才失效”的语义!

一旦用在多线程环境中,问题就会变得很复杂,因为修改了父节点。就不能仅lock需要修改数据的那个结点,而是需要lock整个tree,使用数据库的术语,就是一下子从记录锁变成了表锁,本来按key查找时,因为key没改变,就不需要加锁,而这样搞,查找时就需要对整个表加锁,严重影响并发性!

注意事项:

1.         trbstrmap::iterator::value_type trbstrmap::value_type都是 mapped_type/Value*iter也是mapped_type;而不是std::mappair<Key,Value>

2.         trbstrmap::key(iter)获得iter对应的key

3.         trbstrmap::klen(iter)获得key_length,当然,strlen(trbstrmap::key(iter))也可以获得key_length,但需要一些时间开销;另外,当key_content中存在/0时,klen就是不可缺少的了(后面将详细介绍这种情况)

4.         再次强调,key_cstr_length最大长度不可超过255,但这个长度不包括末尾的 /0

 

示例代码:

         typedef febird::trbstrmap<int, &trb_compare_tev_inline_cstr_nocase> smap_t;

         smap_t smap, smap2;

 

         smap[“1”] = 0;

         smap[“2”] = 1;

         smap[“3”] = 1;

         smap[“4”] = 2;

         smap[“1”]++;

         smap[“4”] += 2;

         smap.insert(“5”, 5);

         assert(!smap.insert(“5”, 6).second);

         // str长度不可超过255

         smap[“aabbccddeeffgghhiijjkk=====================================”] = 10;

 

         for (typename SMT::iterator i = smap.begin(); i != smap.end(); ++i)

         {

                   printf(“smap[%s]=%d, klen=%d/n”, smap_t::key(i), *i, smap_t::klen(i));

         }

 

 

在简单的情况下,使用trbstrmap,std::map可以节省50%~70%的内存。使用的方便程度,基本上没差别。

 

数据结构

Mapped Data 是模板参数,可以是任意struct/class,当然也可以内嵌指针,也可以是复杂对象,没有任何限制。

 

 trbstrmap Node Structure

复杂情形:任意字符串,字符串中可以包含/0

trbstrmap允许加入内容中存在/0的字符串,这种应用比较罕见,但是仍然允许,只是必须遵循以下注意事项:

1.         在这种情况下,需要传入key_content_length参数:
trbstrmap.probe(key,key_content_length)
trbstrmap.insert(key,key_content_length, val)
key_content_length
是整个key_content长度,包括末尾的/0——如果有的话

2.         或者,传入std::string
trbstrmap[std::string(…)] = val;
equal to: trbstrmap.probe(s.c_str(), s.size()+1) = val;

3.         trbstrmap.insert(key, klen, val)

4.         这种情况下,应用一般需要传入一个自定义的Compare

5.         trbstrmap::klen(iter)在任何情况下,返回的都是key_content_length – 1
不管末尾有没有/0

6.         自定义函数需要获取key_content_length时,应该如下:

int

trb_compare_custom ( const struct trb_vtab* TRB_restrict vtab,

                                          const struct trb_tree* TRB_restrict tree,

                                          const void* TRB_restrict x,

                                          const void* TRB_restrict y)

{

     size_t lx = ((unsigned char*)x)[-1] + 1;

     size_t ly = ((unsigned char*)y)[-1] + 1;

int ret = memcmp(x, y, lx<ly?lx:ly); // 仅示例,不一定非用memcmp

     return 0 == ret ? lx – ly : ret;

}

7.         当给trbstrmap::find/lower_bound/equal_range多传入一个key_content_length时,这些函数会将keykey_content_length打包(这些都在库内部完成),应用须知这会有稍微多一些的开销。

必须这么做,因为compare函数需要找到key_content_length,除此之外,别无他法。

8.         貌似很复杂,但始终坚持剃刀原理:在绝大多数情况下,也就是字符串是cstr,末尾包含/0时,函数的行为符合传统惯例并且高效;在罕见情况下也可用,只是效率有一点下降,使用难度也大一些。

9.         当情况复杂时,记住:只要你明确传入了长度,这个长度就是你真实数据的长度

 

测试代码:

MapReduce做了多余的事情

阅读更多关于《MapReduce做了多余的事情》

本文假定读者已了解MapReduce

先说 Map

Map阶段一般做三件事情:

继续阅读