首页 > 代码库 > nark 数据库简介

nark 数据库简介

2024-11-25 06:27:02   203人阅读

本文是本人原创，来自本人的公司网站：http://nark.cc/p/?p=1560

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

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

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

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


nark 是如何的强大


作为
NoSQL
数据库

  1. 提供普通数据库的精确查找、范围查找、前缀查找
  2. 高效支持正则表达式查找，仅用几十微秒，就能在包含数亿条记录的数据库中找到结果
  3. 内存用量非常低，索引结构(即全部数据)是高度压缩的！
    • 因为高度压缩，整个数据库完全装在内存中，查找过程无任何硬盘访问
    • 使用 mmap ，瞬间即可加载整个数据库，真正实现“一次建库，到处使用”
    • 支持 MapReduce 并行建库，适应高速创建超大数据库的需求
  4. 举个极端的例子：一个841M 的 url 列表，被压缩到只有6.4M，压缩率高达131:1
    • 哪怕是只比较压缩率，都远超主流压缩软件（bzip2只压缩到37M，压缩率23:1）
    • 而与此同时，从中查找一条 url 只需要600纳秒！

智能纠错

Demo 见首页，这本质上可以认为是用正则表达式查找数据库，不过这个“正则表达式”不是人手写的，而是从搜索词创建了一个DFA， 这个DFA自然有某正则表达式与它对应。

规则引擎

每条规则是一个高级正则表达式，假如配置了10万条规则，现在有一个字符串(比如一条网络消息)，要看这个字符串能匹配那个(或哪些)规则，nark 规则引擎只需要几微秒的时间就能得到结果。应用案例：某互联网公司的查询词分类、某自然语言处理应用中的，某手机短信分析应用、某网络设备商的入侵检测……
一个简化的场景是规则只包含需要精确匹配的二进制串，可以使用 nark AC自动机，Benchmark 中 2000 个 pattern ， 匹配性能高达 720MB/s
用于NLP
(自然语言处理)
  • 把大量语料（例如: N-Gram）压缩到一个DFA中，既有强大的匹配能力，又大大减小内存用量（或者换句话说，使用相同的内存装入更多语料）。
  • 把很多复杂的计算问题简化为（匹配 + 简单的计算），等等
用于海量
小文件压缩
  • 在小文件存储中，使用主流的压缩算法，要实时读取单个小文件，就只能压缩文件内的冗余，文件之间的冗余无法压缩
  • 使用 rltzip ，可以高效压缩海量小文件，并且高速读取单个小文件(相当于仅解压一个文件)
  • 搜索引擎的正排表是一个典型的现实案例


nark 核心 API


抽象接口功能
DFA_Interface前缀搜索、Key-Value 搜索、Key 存在性检验
DAWG_Interface前缀搜索、字符串 Key 和 整数 Index 互相转化，Index 是 Key 在整个数据库中的排序序号：从 0 到 n-1。
要实现 Map<Key,Value> 的功能，可以将 Value 保存在外部一个数组中，用 Index 访问；这就有了另外一种能力：修改 Value
SuffixCountableDAWGDAWG_Interface 的派生接口，新增功能：高速获取指定前缀的所有不同后缀的数量
AC_Scan_InterfaceAC 自动机多模匹配：在整个输入数据中搜索多个 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 有以上优点，以下两种使用方式都很适合：

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

rltzip

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

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

rltunzip

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

regex_build

这个是规则引擎建库工具

 

 更多文档，正在撰写中……

nark 数据库简介


联系
我们