当搜索词中有错别字时，搜索引擎会尝试纠错通过相似拼音纠错搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。 这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！ 例如某互联网大厂的实现(枚举多音字全排列)。 基于自动机的算法可以完美解决这个指数爆炸问题
这个算法也可以用来解决用户输入预测(智能提示)功能用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。 基于编辑距离的纠错在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面） |
|
先强调一点，在我的引擎中，所有正则表达式的语法结构，包括 并、交、差、补 都是在编译时完成的，对匹配性能无任何影响，切记！…… 现在可以开始了：
正则表达式，描述的是正则语言， 学过形式语言与自动机理论的人应该都知道，正则语言在并、交、差、补运算下都是封闭的；但是，根据 Wikipedia 的描述，到目前为止，还没有任何一个已知的正则流派(Flavor)将交和差纳入正则语法。理论与实践之间竟然隔着这么巨大的鸿沟！
| 并： | A || B | 能匹配 A 或者能匹配 B | 这三种操作都可以编译为 DFA， 从而非常高效地执行匹配 |
|---|---|---|---|
| 交： | A && B | 能匹配 A 并且能匹配 B | |
| 差： | A &! B | 能匹配 A 但不能匹配 B，即从 A 中排除 B |
一直以来，自动机的创建程序（adfa_build/dawg_build/kvbin_build 等）性能虽然尚可，以最常用的 adfa_build 来说，根据不同的输入文本，平均吞度量能达到每秒钟 5~20M 。这个速度看上去还不错，至少比竞品要快了许多，但是，如果有非常大的数据 继续阅读
前一段时间，在将 多正则表达式匹配工具 用于数十万任意的正则表达式时，以前一直担心的问题终于出现了：NFA 转化 DFA 时的指数爆炸，那样的 DFA 根本创建不出来，因为那些正则表达式之间有不可预料的各种交集！ 继续阅读
最近做了一项工作：允许一个 DFA 有多个起始状态（可以称作根: root）。引入这个概念有很多好处，主要体现在 DFA Union 中，这个操作通过 NFA 到 DFA 的转化来完成，算法思想很简单： 继续阅读
这篇文档只关心 有穷状态自动机 ，不讲具体的算法，对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库，怎样使用自动机 API 访问 KV 数据库…… 继续阅读
代码表示的是数据格式，DATA_IO_LOAD_SAVE 在 <febird/io/DataIO.h> 中定义
对于 boost.serialization， DATA_IO_LOAD_SAVE 的定义相当于： 继续阅读
简而言之，编程语言中的反射（Reflection）指的是从运行时中获取语言本身的类型等信息。C++ 缺乏这样的机制，对于最简单的 enum 类型，我们或许可以实现带有反射功能的 enum。
我们实现了几个宏，通过宏定义的 enum，就自动地拥有反射功能。
|
1 2 3 4 5 6 7 |
// 可在任意 namespace 中调用，不可在 struct/class 内调用 #define TERARK_ENUM_PLAIN(EnumType, IntRep, ...) details... #define TERARK_ENUM_CLASS(EnumType, IntRep, ...) details... // 可在 struct/class 内调用，不可在任意 namespace 中调用 #define TERARK_ENUM_PLAIN_INCLASS(EnumType, IntRep, ...) details... #define TERARK_ENUM_CLASS_INCLASS(EnumType, IntRep, ...) details... |
作为数据库，在系统资源(cpu, 内存, ssd, 磁盘 …) 一定的前提下，我们希望：
windows 和 linux 都不约而同地加入了 自动最大化 的功能：在拖动整个窗口 或 拖动resize 窗口 到屏幕边缘时，会自动最大化。
我一向非常反感这种自作聪明越俎代庖把用户当傻逼的 傻逼 产品经理/程序员 的 傻逼 行为。
所以，我要禁止这种傻逼功能：
设置 >> 系统 >> 多任务 >> 靠贴: 把选择框打叉
gconftool-2 –set /apps/compiz-1/plugins/grid/screen0/options/top_edge_action –type int 0
Mongodb 虽然是 schemaless (不需要 schema) 的文档数据库，但是，同一个表中的数据一般都有相同的结构，我们需要将这样的结构抽象出来，用以提高数据库的性能
terichdb 的数据有以下类型： 继续阅读
找了很多地方，最终的解决方案： 继续阅读
之前，自动机词典仅用来存储自然语言处理的语料、url、query 等单条数据很小的数据集，为了简单，解压算法用的是递归实现。前段时间对自动机进行了一个改进，可以压缩存储单条数据很大的数据集。于是，该发生的事情终于发生了：堆栈溢出，也叫爆栈！ 继续阅读
nark 数据库最重要的特性：高压缩并且拥有丰富、高效的查询能力。特别是高压缩，其他数据库都没有这个能力，你可能对此表示怀疑，本文提供的内容会打消你的疑虑。
实现上，不同于普通 Hash 或 Tree 结构的数据库，nark 数据库是基于自动机的，这决定了 nark 的强大与简洁，但是，最重要的是，nark 为大家提供了一整套解决方案。
因为自动机只有离线(offline)创建成只读数据库，才能为在线(online)计算 提供 最节省内存 并且 高速查找 的 功能。从而，绝大部分 nark 组件都分为离线(offline)建库 和 在线(online)搜索 两部分。
目前，离线建库以可执行程序的形式向所有用户开放，在线搜索以 C++ API 的形式仅向付费用户开放。
为了让所有用户在付费前体验 nark 的高性能，下载包中也包含了一些示例程序，大部分示例程序同时也是 benchmark 程序，所有用户都可以在自己的机器上运行这些示例程序。 继续阅读
描述 Double Array Trie 的文章有很多，我在这里从另一个视角来讲 Double Array Trie。首先，是 base 和 check 的更深层含义，然后再详细说一下由此引申出来的问题。 继续阅读
