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

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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

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

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

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

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

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

继续阅读

用自动机表达嵌套的数据

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

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

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

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

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

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

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

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

规则引擎建库工具

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

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

继续阅读

有多个初始状态的 DFA

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

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

把自动机用作 Key-Value 存储

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

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

febird.dataio vs boost.serialization 运行性能对比

阅读更多关于《febird.dataio vs boost.serialization 运行性能对比》

代码表示的是数据格式,DATA_IO_LOAD_SAVE 在 <febird/io/DataIO.h> 中定义

对于 boost.serializationDATA_IO_LOAD_SAVE 的定义相当于: 继续阅读

全局压缩-革命性的数据库技术

阅读更多关于《全局压缩-革命性的数据库技术》

全局压缩-革命性的数据库技术

背景

作为数据库,在系统资源(cpu, 内存, ssd, 磁盘 …) 一定的前提下,我们希望:

  1. 存储的数据更多:采用压缩,这个世界上有各种各样的压缩算法……
  2. 访问的速度更快:更快的 压缩(写)/解压(读) 算法,更大的缓存……

继续阅读

禁止窗口自动最大化

阅读更多关于《禁止窗口自动最大化》

windows 和 linux 都不约而同地加入了 自动最大化 的功能:在拖动整个窗口 或 拖动resize 窗口 到屏幕边缘时,会自动最大化。

我一向非常反感这种自作聪明越俎代庖把用户当傻逼的 傻逼 产品经理/程序员 的 傻逼 行为。

所以,我要禁止这种傻逼功能:

windows10

设置 >> 系统 >> 多任务 >> 靠贴: 把选择框打叉

linux

gconftool-2 –set /apps/compiz-1/plugins/grid/screen0/options/top_edge_action –type int 0

MongoDB 的 terichdb schema

阅读更多关于《MongoDB 的 terichdb schema》

Mongodb 虽然是 schemaless (不需要 schema) 的文档数据库,但是,同一个表中的数据一般都有相同的结构,我们需要将这样的结构抽象出来,用以提高数据库的性能

terichdb 的数据有以下类型: 继续阅读

在 Ubuntu 中禁止自动隐藏程序菜单

阅读更多关于《在 Ubuntu 中禁止自动隐藏程序菜单》

找了很多地方,最终的解决方案: 继续阅读

自动机解压中的非递归算法

阅读更多关于《自动机解压中的非递归算法》

之前,自动机词典仅用来存储自然语言处理的语料、url、query 等单条数据很小数据集,为了简单,解压算法用的是递归实现。前段时间对自动机进行了一个改进,可以压缩存储单条数据很大数据集。于是,该发生的事情终于发生了:堆栈溢出,也叫爆栈! 继续阅读

nark 数据库简介

阅读更多关于《nark 数据库简介》

nark 数据库最重要的特性:高压缩并且拥有丰富、高效的查询能力。特别是高压缩其他数据库都没有这个能力,你可能对此表示怀疑,本文提供的内容会打消你的疑虑。

实现上,不同于普通 Hash 或 Tree 结构的数据库,nark 数据库是基于自动机的,这决定了 nark 的强大与简洁,但是,最重要的是,nark 为大家提供了一整套解决方案

因为自动机只有离线(offline)创建成只读数据库,才能为在线(online)计算 提供 最节省内存 并且 高速查找 的 功能。从而,绝大部分 nark 组件都分为离线(offline)建库 在线(online)搜索 两部分。

目前,离线建库以可执行程序的形式向所有用户开放,在线搜索以 C++ API 的形式仅向付费用户开放。

为了让所有用户在付费前体验 nark 的高性能,下载包中也包含了一些示例程序,大部分示例程序同时也是 benchmark 程序,所有用户都可以在自己的机器上运行这些示例程序。 继续阅读

发掘双数组Trie (Double Array Trie)的能力

阅读更多关于《发掘双数组Trie (Double Array Trie)的能力》

描述 Double Array Trie 的文章有很多,我在这里从另一个视角来讲 Double Array Trie。首先,是 base 和 check 的更深层含义,然后再详细说一下由此引申出来的问题。 继续阅读

AC 自动机的实现

阅读更多关于《AC 自动机的实现》

关于 AC 自动机,有太多的文章在讲述它的原理,讲述者借此来展示自己的算法能力。但其实AC自动机的原理很简单,真正困难的地方在于一个高效的实现!对于任何一个基础算法,一个好的实现都要尽量满足:

* 速度快 这几点排名不分先后
* 内存小
* 接口灵活、通用
* 使用简单、易上手

继续阅读

奇简软件名字的故事

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

奇简软件,“奇”字本身有“奇妙”、“奇特”,还有“非常”的意思,“简”字有“简单”、“简洁”,另外,还有“竹简”,也就是“书”、“知识”的意思,放在一起,有多重含义。

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

多正则表达式匹配的应用

阅读更多关于《多正则表达式匹配的应用》

搜索引擎 Query 分析

Query 意图分析

定义一批规则(正则表达式),每条规则表达一种搜索的意图,例如问路、吃饭、看病、查找ip、查找电话、小说、软件下载…… 继续阅读