当前位置：首页 -> AI编程基础 -> 数据库编程

nark数据库简介(一)

2015-11-21 01:44:05 · 作者: · 浏览: 7
标签: nark 数据库 简介

  1. 作为

  2. NoSQL

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

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

  3. 规则引擎
  1. 每条规则是一个高级正则表达式，假如配置了10万条规则，现在有一个字符串(比如一条网络消息)，要看这个字符串能匹配那个(或哪些)规则，nark 规则引擎只需要几微秒的时间就能得到结果。应用案例：某互联网公司的查询词分类、某自然语言处理应用中的，某手机短信分析应用、某网络设备商的入侵检测……
  2. 一个简化的场景是规则只包含需要精确匹配的二进制串，可以使用 nark AC自动机，Benchmark 中 2000 个 pattern ， 匹配性能高达 720MB/s
  1. 用于NLP
  2. (自然语言处理)
  1. 把大量语料（例如: N-Gram）压缩到一个DFA中，既有强大的匹配能力，又大大减小内存用量（或者换句话说，使用相同的内存装入更多语料）。把很多复杂的计算问题简化为（匹配 + 简单的计算），等等
  1. 用于海量
  2. 小文件压缩
  1. 在小文件存储中，使用主流的压缩算法，要实时读取单个小文件，就只能压缩文件内的冗余，文件之间的冗余无法压缩使用 rltzip ，可以高效压缩海量小文件，并且高速读取单个小文件(相当于仅解压一个文件)搜索引擎的正排表是一个典型的现实案例
  1. 抽象接口
  1. 功能
  1. DFA_Interface
  1. 前缀搜索、Key-Value 搜索、Key 存在性检验
  1. DAWG_Interface
  1. 前缀搜索、字符串 Key 和 整数 Index 互相转化，Index 是 Key 在整个数据库中的排序序号：从 0 到 n-1。
  2. 要实现 Map 的功能，可以将 Value 保存在外部一个数组中，用 Index 访问；这就有了另外一种能力：修改 Value
  1. SuffixCountableDAWG
  1. DAWG_Interface 的派生接口，新增功能：高速获取指定前缀的所有不同后缀的数量
  1. AC_Scan_Interface
  1. AC 自动机多模匹配：在整个输入数据中搜索多个 Pattern 的出现位置
不同于普通 Hash 或 Tree 结构的数据库，nark 数据库是 基于自动机的，这决定了 nark 的强大与简洁，但是，最重要的是，nark 为大家提供了 一整套解决方案。
因为自动机只有离线(offline)创建成 只读数据库，才能为在线(online)计算 提供 最 节省内存 并且 高速查找 的 功能。从而，绝大部分 nark 组件都分为 离线(offline)建库 和 在线(online)搜索 两部分。
目前， 离线建库以可执行程序的形式向 所有用户开放， 在线搜索以 C++ API 的形式仅向 付费用户开放。
为了让 所有用户在付费前体验 nark 的高性能， 下载包中也包含了一些 示例程序，大部分示例程序同时也是 benchmark 程序， 所有用户都可以在自己的机器上运行这些示例程序。同时，这些示例程序的代码也向 所有用户开放，但只有 付费用户才能自己编译这些示例程序，因为需要 C++ API 。


nark 是如何的强大



?

nark 核心 API



?

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小文件压缩到 7