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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

wordpress 速度很慢的问题解决了

阅读更多关于《wordpress 速度很慢的问题解决了》

因为 googleapis.com 被墙奸了,把 wordpress 目录下面所有文件中的 googleapi 全部替换成 useso 就 OK 了

cygwin 中 dll 路径

阅读更多关于《cygwin 中 dll 路径》

cygwin 中 dll 路径不是用 LD_LIBRARY_PATH 指定,而是 PATH,坑爹!
更坑爹的是, cygwin 中的 ldd 如果找不到某个 dll,竟然不报错,直接不显示那个 dll 文件!cygcheck 找不到依赖的 dll 时倒是会报错。

使用 自动机 解决 拼音输入法 中的 多音字 组合爆炸

阅读更多关于《使用 自动机 解决 拼音输入法 中的 多音字 组合爆炸》

背景

为了保证输入效率,我们需要有一个从 词条拼音 到 词条汉字 的映射表,比如,拼音序列 ZiDongJi 对应的词条是 自动机 , 自冻鸡 ;从而,逻辑上讲,这是一个 map<string,list<string> >继续阅读

Koening Lookup

阅读更多关于《Koening Lookup》

也就是 C++ 函数名字的两阶段查找,模板实例化之前和实例化之后

C++每个类对象都有一个名字空间,而非类对象,比如 int, char, long, char*….,没有关联的名字空间。 继续阅读

搜索引擎关键字智能提示的一种实现(原网页的备份)

阅读更多关于《搜索引擎关键字智能提示的一种实现(原网页的备份)》

美团原网页:

http://tech.meituan.com/pinyin-suggest.html

对比我们的纠错算法,美团的这个算法正好是一个反面教材,它集中展现了互联网时代糙快猛的核心价值观,以下是它的原文备份:


问题背景

搜索关键字智能提示是一个搜索应用的标配,主要作用是避免用户输入错误的搜索词,并将用户引导到相应的关键词上,以提升用户搜索体验。 继续阅读

多正则表达式匹配 (Multiple Regular Expression Matching) 中的动态 DFA 算法

阅读更多关于《多正则表达式匹配 (Multiple Regular Expression Matching) 中的动态 DFA 算法》

前一段时间,在将 多正则表达式匹配工具 用于数十万任意的正则表达式时,以前一直担心的问题终于出现了:NFA 转化 DFA 时的指数爆炸,那样的 DFA 根本创建不出来,因为那些正则表达式之间有不可预料的各种交集! 继续阅读

规则引擎建库工具

阅读更多关于《规则引擎建库工具》

这个工具使用了一个非常高效的算法,用来匹配多个高级正则表达式。经过预处理,仅用 O(n) 的时间复杂度,就可以识别出一个输入字符串(长度为n)能匹配哪些(可能是多个)正则表达式。算法的详细内容可参见:

继续阅读

有多个初始状态的 DFA

阅读更多关于《有多个初始状态的 DFA》

最近做了一项工作:允许一个 DFA 有多个起始状态(可以称作根: root)。引入这个概念有很多好处,主要体现在 DFA Union 中,这个操作通过 NFA 到 DFA 的转化来完成,算法思想很简单: 继续阅读

gcc 4.7.3 的一个 c++11 bug

阅读更多关于《gcc 4.7.3 的一个 c++11 bug》

昨天一个朋友 checkout 了我的 febird 代码,编译时出现了一个诡异的错误。经过仔细勘察,他的 g++ 版本是 4.7.3,而我测试过的 g++4.7.2,g++4.8.2均无问题。 继续阅读

多正则表达式匹配(Multiple Regular Expression Matching)

阅读更多关于《多正则表达式匹配(Multiple Regular Expression Matching)》

目前 febird 中的自动机库已支持正则表达式,并且,支持的是多正则表达式匹配: 继续阅读