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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

boost 这帮人也超级不靠谱

阅读更多关于《boost 这帮人也超级不靠谱》

刚才开始用 boost::range,就查看了了一下 boost 源码,发现 boost-1.50 一个 bug,觉得应该在新版中已经修改了,下载了最新的 1.54 版,进去一看,bug 仍然在! 继续阅读

把自动机用作 Key-Value 存储

阅读更多关于《把自动机用作 Key-Value 存储》

这篇文档只关心 有穷状态自动机 ,不讲具体的算法,对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库,怎样使用自动机 API 访问 KV 数据库…… 继续阅读

原地排序-更简洁的算法

阅读更多关于《原地排序-更简洁的算法》

在我以前的这篇文章中:原地排序与链表翻转

解决这个问题是先把链表翻转,然后再循环左移,原理是清楚了,可是稍显繁琐。今天得知该问题的另一个解法: 继续阅读

字符串匹配中的图论

阅读更多关于《字符串匹配中的图论》

有一个字符串由多个变量拼接而成: “$x1$x2$x3$x4$x5$x6…” ,这个列表可以一直延伸到 $x10000,而每个变量都至少有一种可能的取值,为了简化问题,每个变量不会再引用别的变量。问题是:给定一个字符串T,判断这个字符串是否能由上面这个 “$x1$x2$x3$x4$x5$x6…” 生成。

继续阅读

李德刚刚来到部队,提出…希望有个中国女战士陪他睡觉

阅读更多关于《李德刚刚来到部队,提出…希望有个中国女战士陪他睡觉》

《一生紧随毛:回忆我的父亲…陈士榘》里记载,“李德刚刚来到部队,提出…希望有个中国女战士陪他睡觉。”
康…说:“当时女同志都不愿意嫁给一个不会说中国话的外国人,所以一直找不到合适的对象。”后来找到个“大个子,长得不错的前童养媳。”萧月华1910年8月出生于广东大埔县一个农民家庭。
继续阅读

避免临时对象的字符串加法

阅读更多关于《避免临时对象的字符串加法》

之前我有一篇文章《 C++中让对象的拷贝成为 显式 的》,使用类似的技巧,可以避免字符串加法中的临时对象,也许是因为惰性,这个想法一直没有诉诸实现,今天有空把它写了出来。 继续阅读

gold_hash_idx 完成了

阅读更多关于《gold_hash_idx 完成了》

用在 onfly minimal acyclic DFA construction 上,速度提高了大约28%,内存对每个State节约了4个字节。

以后有空再努力一下,把 gold_hash_idx 再深入泛化一步,做成可以更方便地用于 multi_index 。

gold_hash_map abstract++

阅读更多关于《gold_hash_map abstract++》

目前的gold_hash_map 实现中,index和data是耦合在一起的。
今天在思考 onfly MinADFA 的进一步优化时,想到了一点:在MinADFA_onfly 中,equivalence_register是一个gold_hash_tab, 继续阅读

Trie, Hash, MinADFA

阅读更多关于《Trie, Hash, MinADFA》

Trie的搜索复杂度是 O(length(strkey)),Hash表,计算Hash的复杂度也是O(length(strkey)),但是,仔细分析一下: 继续阅读

NFA转化DFA

阅读更多关于《NFA转化DFA》

NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,实际上,在计算理论中,它属于ExpSpace问题,是一类比NP问题更难的问题。

继续阅读