nark 数据库简介

作者: rockeet 发表日期: 2015年02月01日分类: 自动机评论: 0 条阅读次数: 14,257 次

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

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

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

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

为了让所有用户在付费前体验 nark 的高性能，下载包中也包含了一些示例程序，大部分示例程序同时也是 benchmark 程序，所有用户都可以在自己的机器上运行这些示例程序。同时，这些示例程序的代码也向所有用户开放，但只有付费用户才能自己编译这些示例程序，因为需要 C++ API 。

nark 是如何的强大

作为 NoSQL 数据库	提供普通数据库的精确查找、范围查找、前缀查找高效支持正则表达式查找，仅用几十微秒，就能在包含数亿条记录的数据库中找到结果内存用量非常低，索引结构(即全部数据)是高度压缩的！因为高度压缩，整个数据库完全装在内存中，查找过程无任何硬盘访问使用 mmap ，瞬间即可加载整个数据库，真正实现“一次建库，到处使用” 支持 MapReduce 并行建库，适应高速创建超大数据库的需求举个极端的例子：一个841M 的 url 列表，被压缩到只有6.4M，压缩率高达131:1 哪怕是只比较压缩率，都远超主流压缩软件（bzip2只压缩到37M，压缩率23:1）而与此同时，从中查找一条 url 只需要600纳秒！
智能纠错	Demo 见首页，这本质上可以认为是用正则表达式查找数据库，不过这个“正则表达式”不是人手写的，而是从搜索词创建了一个DFA，这个DFA自然有某正则表达式与它对应。
规则引擎	每条规则是一个高级正则表达式，假如配置了10万条规则，现在有一个字符串(比如一条网络消息)，要看这个字符串能匹配那个(或哪些)规则，nark 规则引擎只需要几微秒的时间就能得到结果。应用案例：某互联网公司的查询词分类(Query意图识别)、某手机短信分析应用、某网络设备商的入侵检测…… 一个简化的场景是规则只包含需要精确匹配的二进制串，可以使用 nark AC自动机，Benchmark 中 2000 个 pattern ，匹配性能高达 720MB/s
用于NLP (自然语言处理)	把大量语料（例如: N-Gram）压缩到一个DFA中，既有强大的匹配能力，又大大减小内存用量（或者换句话说，使用相同的内存装入更多语料）。把很多复杂的计算问题简化为（匹配 + 简单的计算），等等
用于海量小文件压缩	在小文件存储中，如果使用主流的压缩算法，要实时读取单个小文件，就只能每个文件分别压缩，读取时分别解压，从而只能压缩同一文件内部的冗余，不同文件之间的冗余无法压缩，导致压缩率很低使用 nlt_zip ，同一文件内部和不同文件之间的冗余都被压缩了，从而可以高效压缩海量小文件，并且高速读取单个小文件(相当于仅解压一个文件) 搜索引擎的正排表是一个典型的现实案例，再比如论坛帖子内容，博客内容，微博内容，等等……

nark 核心 API

抽象接口	功能
MatchingDFA	前缀搜索、Key-Value 搜索、Key 存在性检验
BaseDAWG	前缀搜索、字符串 Key 和整数 Index 互相转化，Index 是 Key 在整个数据库中的排序序号：从 0 到 n-1。要实现 Map<Key,Value> 的功能，可以将 Value 保存在外部一个数组中，用 Index 访问；这就有了另外一种能力：修改 Value
SuffixCountableDAWG	BaseDAWG的派生接口，新增功能：高速获取指定前缀的所有不同后缀的数量，这种DAWG的 key <-> id 映射是字典序的。
BaseAC	AC 自动机多模匹配：在整个输入数据中搜索多个 Pattern 的出现位置

nark 离线建库程序

adfa_build

用来从文本文件创建 (Key, Value) 数据库，(Key, Value) 都是字符串。文本文件中每行是一条 (Key, Value) 记录，一般情况下 (Key, Value) 之间使用 \t 分隔，第一个 \t 之前的是 Key，之后的是 Value，Value 中也可以包含 \t。

这个程序生成的 dfa 数据库仅支持 MatchingDFA 接口。

这个程序适合用来创建 (Key, Value) 集合有组合特征的输入，当你不能确定这一点时，可以尝试 nlt_build，看生成的 dfa 数据库文件是否更小。

dawg_build

用来从文本文件创建 (Key, Index) 数据库，文本文件中每行的全部内容被当作一个Key。生成的 dfa 数据库同时支持 AcyclicPathDFA 和 SuffixCountableDAWG。

DAWG 的全称是 Directed Acylic Word Graph。

在 SuffixCountableDAWG 中，一个 Key 对应的 Index 是这个 Key 在整个 Key 集合中的字典序的序号(0 ~ n-1)
只有当 Key 集合有高度组合特征时，这种数据库的压缩率才更高
一般而言，SuffixCountable 的功能并不是很重要，但由此功能引申出来的字典序非常重要，特别是创建由多个DFA组成超大DFA时，和单趟创建KeyValue数据库时。

nlt_build

这个程序也用来从文本文件创建 (Key, Value) 数据库，很多情况下生成的数据库文件比 adfa_build 要小，并且功能更丰富，支持 MatchingDFA 和 BaseDAWG。nlt 的含义是 NestLoudsTrie。

这种数据库并不是 Directed Acylic Word Graph，但是它也可以实现 Key 和整数 Index 之间的互相映射，这个 Index 不是字典序，而是对压缩算法来说，最“自然”的一个映射，可以认为是没有规律的。如果你需要将该 Index 与 Value 数组对应起来，需要再次处理一遍数据以建立这种联系。

从名字可以看出，这种数据库本质上是一种 trie 树。但是相比双数组(DoubleArray) Trie，这种 trie 的尺寸大约要小30倍，甚至300倍也有可能。当然，速度比 DoubleArray Trie 要慢不少，根据数据和应用场景的的不同，大约在 3~8倍之间。

即使不考虑查找功能，仅把 nlt_build 当作一个压缩软件，大多数情况下，针对 (Key, Value) 文本文件，它的压缩率也比传统压缩软件(如gzip,bzip2,7z,…)更高。

虽然这种数据库比 adfa 拥有额外的能力(Key 和 Index 互相转化)，但是很多时候尺寸竟然还更小，并且速度更快，似乎有点违反直觉，但事实确实如此。

只有在数据有大量组合特征时，nlt 才比 adfa 尺寸更大。在理论上 nlt 的压缩率是线性的，adfa 是指数的，但实际数据的冗余更多情况下的是线性的，不是指数的。

因为 nlt 有以上优点，以下两种使用方式都很适合：

文本文件每行是一条 (Key, Value) 记录，通常使用 MatchingDFA 接口
文本文件每行仅包含一个 Key，而无 Value，通常使用 BaseDAWG，如果 Value 需要修改，就只能使用这种方式
这种数据库不是 SuffixCountableDAWG，幸运的是，这个功能大多数应用都不需要

nlt_zip

使用与 nlt_build 相同的算法，压缩大量小文件（目前单个文件最大长度限制为16M），文件数量越多，压缩率越高，特别是对文本文件。

生成的 dfa 数据库文件格式与 nlt_build 完全相同。我曾使用 nlt_zip 把总共 58G 的 300万个json小文件压缩到 7G 的单个 nlt 。

nlt_unzip

按文件名从 nlt_zip 生成的数据库中解压/读取

regex_build

这个是规则引擎建库工具