nark 数据库简介
本文是本人原创，来自本人的公司网站：http://nark.cc/p/?p=1560
不同于普通 Hash 或 Tree 结构的数据库，nark 数据库是基于自动机的，这决定了 nark 的强大与简洁，但是，最重要的是，nark 为大家提供了一整套解决方案。
因为自动机只有离线(offline)创建成只读数据库，才能为在线(online)计算 提供 最节省内存 并且 高速查找 的 功能。从而，绝大部分 nark 组件都分为离线(offline)建库 和 在线(online)搜索 两部分。
目前，离线建库以可执行程序的形式向所有用户开放，在线搜索以 C++ API 的形式仅向付费用户开放。
为了让所有用户在付费前体验 nark 的高性能，下载包中也包含了一些示例程序，大部分示例程序同时也是 benchmark 程序，所有用户都可以在自己的机器上运行这些示例程序。同时，这些示例程序的代码也向所有用户开放，但只有付费用户才能自己编译这些示例程序，因为需要 C++ API 。
nark 是如何的强大
作为
|
|
智能纠错 |
Demo 见首页，这本质上可以认为是用正则表达式查找数据库，不过这个“正则表达式”不是人手写的，而是从搜索词创建了一个DFA， 这个DFA自然有某正则表达式与它对应。 |
规则引擎 |
每条规则是一个高级正则表达式，假如配置了10万条规则，现在有一个字符串(比如一条网络消息)，要看这个字符串能匹配那个(或哪些)规则，nark 规则引擎只需要几微秒的时间就能得到结果。应用案例：某互联网公司的查询词分类、某自然语言处理应用中的，某手机短信分析应用、某网络设备商的入侵检测…… 一个简化的场景是规则只包含需要精确匹配的二进制串，可以使用 nark AC自动机，Benchmark 中 2000 个 pattern ， 匹配性能高达 720MB/s |
| 用于NLP (自然语言处理) |
|
| 用于海量 小文件压缩 |
|
nark 核心 API
| 抽象接口 | 功能 |
| DFA_Interface | 前缀搜索、Key-Value 搜索、Key 存在性检验 |
| DAWG_Interface | 前缀搜索、字符串 Key 和 整数 Index 互相转化，Index 是 Key 在整个数据库中的排序序号：从 0 到 n-1。 要实现 Map<Key,Value> 的功能，可以将 Value 保存在外部一个数组中，用 Index 访问；这就有了另外一种能力：修改 Value |
| SuffixCountableDAWG | DAWG_Interface 的派生接口，新增功能：高速获取指定前缀的所有不同后缀的数量 |
| AC_Scan_Interface | AC 自动机多模匹配：在整个输入数据中搜索多个 Pattern 的出现位置 |
nark 离线建库程序
adfa_build
用来从文本文件创建 (Key, Value) 数据库，(Key, Value) 都是字符串。文本文件中每行是一条 (Key, Value) 记录，一般情况下 (Key, Value) 之间使用 \t 分隔，第一个 \t 之前的是 Key，之后的是 Value，Value 中也可以包含 \t。
这个程序生成的 dfa 数据库仅支持 DFA_Interface 接口。
这个程序适合用来创建 (Key, Value) 集合有组合特征的输入，当你不能确定这一点时，可以尝试 rptrie_build，看生成的 dfa 数据库文件是否更小。
dawg_build
用来从文本文件创建 (Key, Index) 数据库，文本文件中每行的全部内容被当作一个Key。生成的 dfa 数据库同时支持 DFA_Interface 和 SuffixCountableDAWG。
DAWG 的全称是 Directed Acylic Word Graph。
- 在 DAWG 中，一个 Key 对应的 Index 是这个 Key 在整个 Key 集合中的字典序的序号(0 ~ n-1)
- 只有当 Key 集合有高度组合特征时，这种数据库的压缩率才更高
- 根据以往经验，DAWG 的适用范围要小于 adfa 和 rptrie
rptrie_build
这个程序也用来从文本文件创建 (Key, Value) 数据库，很多情况下生成的数据库文件比 adfa_build 要小，并且功能更丰富，支持 DFA_Interface 和 DAWG_Interface。
这种数据库并不是 Directed Acylic Word Graph，但是它也可以实现 Key 和 整数 Index 之间的互相映射，这个 Index 不是字典序，而是 KeyLen+字典序，可以用以下代码生成这样的序列：
从名字可以看出，这种数据库本质上是一种 trie 树。但是相比双数组(DoubleArray) Trie，这种 trie 的尺寸大约要小30倍，甚至300倍也有可能。当然，速度比 DoubleArray Trie 要慢不少，根据数据和应用场景的的不同，大约在 3~10 倍之间。
虽然这种数据库比 adfa 拥有额外的能力(Key 和 Index 互相转化)，但是很多时候尺寸竟然还更小，并且速度更快，似乎有点违反直觉，但事实确实如此。
只有在数据有大量组合特征时，rptrie 才比 adfa 尺寸更大。在理论上 rptrie 的压缩率是线性的，adfa 是指数的，但实际数据的冗余更多情况下的是线性的，不是指数的。
因为 rptrie 有以上优点，以下两种使用方式都很适合：
- 文本文件每行是一条 (Key, Value) 记录，通常使用 DFA_Interface 接口
- 文本文件每行仅包含一个 Key，而无 Value，通常使用 DAWG_Interface，如果 Value 需要修改，就只能使用这种方式
- 这种数据库不是 SuffixCountableDAWG，幸运的是，这个功能大多数应用都不需要
rltzip
使用与 rptrie_build 相同的算法，压缩大量小文件（目前单个文件最大长度限制为16M），文件数量越多，压缩率越高，特别是对文本文件。
生成的 dfa 数据库文件格式与 rptrie_build 完全相同。我曾使用 rltzip 把总共 58G 的 300万个json小文件压缩到 7G 的单个 rptrie 。
rltunzip
按文件名从 rltzip 生成的数据库中解压/读取
regex_build
这个是规则引擎建库工具
更多文档，正在撰写中……
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
