Uindex - 通用索引

Uindex 是一个数据存储库，用于可以解析为某些上下文无关语言中句子的数据。通过它，可以创建数据库（db），向其中添加数据，并查询这些数据。每个 db（或，我们可能称之为，其模式）的形状由一个 解析表达式语法（PEG）给出，因此每个数据库都以 unicode 字符串的形式存储数据，这些字符串按照提供的 PEG 的顶层生成式进行结构化。

对 uindex 的查询也采用 PEG 中指定的形式：它们只是由 PEG 描述的语言中的句子。此外，在查询中，我们可以使用变量，代替 PEG 中的任何生成式，从数据库中检索未知值。我们还可以在查询中使用多个句子。

Uindex 以这种方式存储数据，向 db 添加新句子的大小为 O(1)，并且允许查询无未知项，相对于 db 的大小也是 O(1)。

示例

例如，我们将构建一个非常简单的三倍数据库，主语-谓语-宾语。单词（无论是主语、谓语还是宾语）将具有字母数字字符的字符串形式，句子将是由 3 个这样的单词通过空格分隔组成。Uindex 目前提供了一个句子终止符号（要么是 <> 要么是 ◊），尽管计划允许用户提供它。因此，在这个数据库中的一个示例句子可以是 susan likes oranges ◊。这个 PEG 将是

fact        = { word ~ word ~ word }

word        = @{ ASCII_ALPHANUMERIC+ }

WHITESPACE  = { " " | "\t" | "\r" | "\n" }

Uindex 使用 Pest 处理 PEG，所以请查阅 pest 文档中 uindex 使用的 PEG 的 特定语法。特别是，对于 Pest，WHITESPACE 规则特别重要，如果提供，它将在任何两个其他链式或重复生成式之间插入（除了标记为 @ 的原子生成式之外。）

上述语法中唯一特定于 uindex 的内容是将顶层生成式命名为 fact；uindex 需要。

现在我们想指定我们的生成式中的哪些可以在查询中作为未知项。我们按照以下方式转换我们的语法

var         = @{ "X" ~ ('0'..'9')+ }

fact        = { word ~ word ~ word }

v_word      = @{ ASCII_ALPHANUMERIC+ }

word        = _{ var | v_word }

WHITESPACE  = { " " | "\t" | "\r" | "\n" }

简而言之，我们为变量提供了一种生成方式，我们使用前缀v_来标识我们希望变量可以匹配的生成式，然后我们提供一个新的生成式，使用旧名称（不包含v_前缀），它是旧生成式和var的和。我们可以标记尽可能多的生成式，它们可以是终结符也可以不是。

要使用此语法，我们需要设置一些样板代码。目前，uindex只能从Rust使用。

因此，我们将上述代码存储在一个名为grammar.pest的文件中，将其放置在我们的rust包的根目录下。

我们必须在我们的Cargo.toml中添加一些依赖项。

[dependencies]
uindex = "0.1.1"
uindex_derive = "0.1.1"
pest = "2.1.3"
pest_derive = "2.1.0"
log = "0.4"
env_logger = "0.7.1"

然后，我们基于语法构建我们的知识库，在rust模块中添加此代码

use crate::uindex::kbase::DBGen;
use crate::uindex::kbase::DataBase;

extern crate uindex
#[macro_use]
extern crate uindex_derive;

extern crate pest;
#[macro_use]
extern crate pest_derive;

#[derive(DBGen)]
#[grammar = "grammar.pest"]
pub struct DBGenerator;

这为我们提供了一个struct DBGenerator，它唯一的职责是根据grammar.pest创建可以存储句子的数据库。因此，我们现在可以构建一个数据库

let db = DBGenerator::gen_db();

我们可以向其中添加数据

db.tell("susan likes oranges ◊");
db.tell("susan likes apples ◊");
db.tell("john likes oranges ◊");
db.tell("john hates apples ◊");

最后，我们可以像这样查询系统

db.ask("john likes oranges ◊");  // -> true
db.ask("john likes apples ◊");  // -> false
db.ask("susan likes X1 ◊");  // -> [{X1: oranges}, {X1: apples}]
db.ask("X1 likes oranges ◊ X1 likes apples ◊");  // -> [{X1: susan}]
db.ask("susan likes X1 ◊ john likes X1 ◊");  // -> [{X1: oranges}]
db.ask("susan X1 apples ◊ john X1 apples ◊");  // -> []

就这样了。

索引

Uindex以树结构（带有一些循环）保存数据，因此查询意味着在树中搜索路径。从输入到uindex的数据中解析出的标记按顺序放置在树中，从根到叶。因此，在查询的开始处放置变量并不方便。当它们不是查询的第一句话时，在句子的开始处放置变量是可以的，并且相关的变量已经被缩小。我将举一个例子。

让我们想象一个电话号码目录，为每个给定的名字和姓氏的唯一配对分配一个号码。如果我们把数据库设置成按“号码 给定名字 姓氏”的顺序存储数据，并查询“X1 john smith”，uindex将检查几乎整个树来找到答案。然而，如果我们把数据库设置成按“姓氏 给定名字 号码”的顺序存储数据，查询“john smith X1”将只检查树的一小部分。

如果有必要以两种方式快速获取数据，即从名称获取号码，以及从号码获取名称，那么可能有必要同时使用这两种类型的句子，但这会以一些数据冗余为代价。

API

语法

数据库生成器

告诉

询问

复杂性

数据结构和算法

基准测试

在这里，我们比较了uindex与内存中的SQLite（由Python驱动）的性能。这并不意味着uindex可以被视为SQLite的替代品，而只是表明uindex的表现是可以接受的，也就是说，其成本，无论是时间还是空间，都是合理的，并且是合理增长的。

请注意，在空间方面，还有一些工作要做。通常，一个uindex数据库将占用与相同数据的SQLite数据库2到3倍的内存。

简单的数据库，简单的查询

对于这个基准测试，我们使用了非常简单的结构的数据，就像上面的例子一样，以及完全限定的查询，这些查询只会检索一行/句子，以获得是/否的回答。对于SQLite，我们使用一个包含3个varchar列的单个表，使用所有3个列的单个索引。我们添加了最多10,000,000条记录，并测量了添加新条目和解决单个答案查询所需的时间。在这个基准测试中，两种情况下的性能都没有随着数据库大小的增加而降低。

uindex基准测试的代码

SQLite基准测试的代码

简单数据库，交集查询

对于这个基准测试，我们使用了与上一个基准测试相同的数据，以及提取两个行/句子共同值的查询。在这个基准测试中，两种情况下性能都没有随着数据库大小的增加而下降。

uindex基准测试的代码

SQLite基准测试的代码

简单数据库，返回多行查询

对于这个基准测试，我们使用了与之前基准测试相同的数据，以及提取100到1000行数据的查询。添加数据与之前的基准测试成本相同。随着SQLite查询命中次数的增加，查询数据的成本略有增加。

uindex基准测试的代码

SQLite基准测试的代码

包含3个表的数据库，查询连接所有3个表

在这里，我们设置了包含3个表的数据库，其中一个表包含指向其他2个表的外键，并查询一个边界表中的数据，提供来自另一个表的数据。对于每个表，无论是uindex还是SQLite，添加到1,000,000条条目时，性能都没有下降。

注意，对于SQLite，在这种情况下，我们希望在插入之前检查重复项，这会影响性能。对于uindex，这是既定的。

uindex基准测试的代码

SQLite基准测试的代码

递归数据库。

在这个基准测试中，我们设置了不同宽度（每个分支的子节点数）和深度（从根到叶子的分支数）的树存储。这个方案中一个示例数据点

(6 (60 617 64) (31 493 538))

每个括号是一个分支，其中第一个条目是分支的名称，其余的是子节点；所以前面是一个深度2宽度2的树。

使用SQLite，我尝试了3个表，Branch, Leaf和Child，其中Child将持有指向Branch的“parent”外键以及指向Child或Branch的“child”外键。我没有找到任何索引组合能够提供可接受的性能，因此这里不包括SQLite的结果。在一个包含20,000个深度为2宽度为2的树的数据库中查找树可能需要10到12秒；显然SQLite不适合这种负载。

然而，我想表明uindex没有这个问题，所以这里展示了uindex在深度为2宽度为2、深度为2宽度为3、深度为3宽度为3的树上的性能，仅查询特定树的存在（查询中没有未知数）。随着数据库大小的增加，性能没有下降，我已经用数据库中有1,000,000棵树进行了测试。

uindex基准测试的代码

SQLite基准测试的代码

待办事项

注意，这是一个正在进行中的工作。目前uindex甚至没有持久性；它只存在于内存中。数据库的大小也有改进的空间，查询可以通过使用一些并行化来受益。目前正在添加（数值和字符串）约束到查询变量。

© EnriquePérez Arnaud <enrique at cazalla dot net> 2021