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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

奇简软件名字的故事

阅读更多关于《奇简软件名字的故事》

奇简软件,“奇简”谐音“旗舰”,“那艘最顶级的船”就是圣经中的“诺亚方舟”了,英文名: Noah’s Ark ,可以简称 nark。 继续阅读

支持 并、交、差 的正则表达式引擎

阅读更多关于《支持 并、交、差 的正则表达式引擎》

先强调一点,在我的引擎中,所有正则表达式的语法结构,包括 补 都是在编译时完成的,对匹配性能无任何影响,切记!…… 现在可以开始了:

正则表达式,描述的是正则语言, 学过形式语言与自动机理论的人应该都知道,正则语言在运算下都是封闭的;但是,根据 Wikipedia 的描述,到目前为止,还没有任何一个已知的正则流派(Flavor)将纳入正则语法。理论与实践之间竟然隔着这么巨大的鸿沟!

并: A  ||  B 能匹配 A 或者能匹配 B 这三种操作都可以编译为 DFA,
从而非常高效地执行匹配
交: A && B 能匹配 A 并且能匹配 B
差: &! B 能匹配 A 但不能匹配 B,即从 A 中排除 B

继续阅读

nark 序列化与 C++14 的新特性

阅读更多关于《nark 序列化与 C++14 的新特性》

nark C++ 序列化库 尽管 性能优异,但是C++14以前,在某些情况下想要完全发挥性能优势,需要额外声明 DATA_IO_DUMP_RAW_MEM

只是因为受制于 C++ 的语法限制,无法实现自动推导所有的 Dumpable 对象——可以 memcpy 的对象: 继续阅读

发现 gcc bug: error: non-static data member declared ‘auto’

阅读更多关于《发现 gcc bug: error: non-static data member declared ‘auto’》

在使用 C++14 的新特性改进 febird dataio 序列化库时(参见: febird 序列化与 C++14 的新特性),发现了一个 gcc 的 bug,可以抽象出精简代码如下: 继续阅读

C++ 实现容器时,写 iterator 很烦

阅读更多关于《C++ 实现容器时,写 iterator 很烦》

实现一个 C++ 容器时,都要提供 iterator, const_iterator, 一般情况下 iterator 和 const_iterator 几乎完全一样,不一样的地方仅在于: 继续阅读

用自动机表达嵌套的数据

阅读更多关于《用自动机表达嵌套的数据》

嵌套数据的典型就是文件系统的目录层次,XML,JSON 等,它们都有专门的存储方式。不过,如果用自动机来存储,更是恰到好处,在这种应用场景中,使用 这篇文章 中提到的 map2:将路径的每层目录用分隔符隔开,比如/ 分隔继续阅读

一个模式识别问题

阅读更多关于《一个模式识别问题》

任意两个字符串 s, t,如果能找到一种替换方式,对 t 中的每个字符 a ,用 s 中的一个字符 b 替换,最后得到一个字符串 t’,如果 t’ 与 s 相同,用符号计作 s->t;如果 s->tt->s,我们称 s 与 t 等价。

例如,下面 4 个字符串就是(互相)等价的: 继续阅读

使用 MapReduce 创建超大巨型自动机

阅读更多关于《使用 MapReduce 创建超大巨型自动机》

一直以来,自动机的创建程序(adfa_build/dawg_build/kvbin_build 等)性能虽然尚可,以最常用的 adfa_build 来说,根据不同的输入文本,平均吞度量能达到每秒钟 5~20M 。这个速度看上去还不错,至少比竞品要快了许多,但是,如果有非常大的数据 继续阅读

binary tree walk

阅读更多关于《binary tree walk》

简单,优美,的代码,你能看出来哪些是二叉树的后序、前序、中序遍历吗?你还知道二叉树有什么遍历方法? 继续阅读

sse4.2 的字符串操作指令

阅读更多关于《sse4.2 的字符串操作指令》

前段时间实现了基于 Succinct Data Structure 的自动机,这种自动机(内存)存储方式将状态转移的 label 单独存储起来,从而,查找 label 就是一个在 byte 数组中查找 byte 的操作,并且,绝大多数情况下,需要查找的这个 byte 数组都非常短(状态的平均转移(label)数一般情况下大约是 2 )。 继续阅读