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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

DFA的实现

阅读更多关于《DFA的实现》

在工业界,DFA的有效实现一直是一个问题,龙书中提到了一种使用四个数组的通用DFA实现,在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现,双数组的仅能用于实现Trie。并且它们的创建速度慢,难以理解,内存占用也比较多,状态id的值域范围稀疏。

继续阅读

Context 终于进 boost 了

阅读更多关于《Context 终于进 boost 了》

Version  1.51.0

New Libraries: Context 继续阅读

自动机的一些算法和应用

阅读更多关于《自动机的一些算法和应用》

几个月前实现了一个自动相关的算法,在一个比较乐观的测试中,将一个2.3G的url集合压缩到了27M,同时,key查找的时间复杂度是O(strlen(key))。当然,还有其它一些自动机相关的算法的优化实现,比如Aho-Corasick多模匹配。 继续阅读

自动机的思维导图

阅读更多关于《自动机的思维导图》
自动机有很多用途,不光是编译器会用到,众所周知的还有正则表达式。其他,简单的如字符串搜索,存储等,复杂点的如模型验证,定理证明…… 继续阅读

避免应用程序抢夺焦点窗口

阅读更多关于《避免应用程序抢夺焦点窗口》

最近老碰到当前窗口被抢焦点,却不知道是哪个程序抢了焦点,找到了这一篇文章: 继续阅读

实现了一个压缩算法,在数据高度压缩的前提下,还可以快速查找 key

阅读更多关于《实现了一个压缩算法,在数据高度压缩的前提下,还可以快速查找 key》

最近写了一个算法,可用于 (key,value) 存储,key 当然是 string 类型。

用一个 2.3G 的 url 集合做测试,如果不计 value 占用的空间,key 集合的存储空间可以被压缩70倍!压缩后整个数据结构仅占31M内存!压缩率比 bzip2 还要高。 继续阅读

原地排序与链表翻转

阅读更多关于《原地排序与链表翻转》

有个长度为 n 的 (key,val) 数组 a,其中 key 是 int 类型,并且其值在 [0, n) 之间(前闭后开,包括 0 不包括 n),该数组按 key 是乱序的,但没有重复 key。

题目要求:对 a 原地按 key 排序,可以使用常数个临时变量,不允许使用其它额外空间,时间复杂度必须是O(n) 继续阅读

C++ 中让对象的拷贝成为 显式 的

阅读更多关于《C++ 中让对象的拷贝成为 显式 的》

C++中对象的拷贝一般使用拷贝构造函数,从而对象的拷贝大多是隐式的,使用拷贝构造函数的隐式拷贝很方便,但是编译器无法识别不必要的拷贝,虽然我们人类可以识别这些不必要的拷贝,比如在写函数原型时,忘了加&,就会引发一个这样的非必要拷贝。 继续阅读

C++11: 使用 lambda 创建模板类 的 对象

阅读更多关于《C++11: 使用 lambda 创建模板类 的 对象》

C++ 中 lambda 可以直接传递给模板函数如 std::sort, 但无法传给模板类如 std::map,但是,使用一点小技巧,可以使用 lambda 创建模板类的对象,省了很多麻烦的 coding。这里给出一个示例: 继续阅读

Recursive Lambda in C++

阅读更多关于《Recursive Lambda in C++》

C++ 标准委员会真是太死板了,既然给 C++ 增加了 lambda,就真的按部就班地套用 lambda 的标准定义,也不加个 lambda的自引用机制。找了半天,除了那些学院派的足以把99%的人搞晕的 Fix Point + Y combinator,一个最实用的解决方案就是把 lambda bind 到 std::function<…>. 继续阅读