Skip to content

Latest commit

 

History

History
91 lines (76 loc) · 4.96 KB

File metadata and controls

91 lines (76 loc) · 4.96 KB

任意位整数

下载 SDK 90 天试用版,满意可 购买正式版

引言

integer-fields.md 中,我们讲述了把 Unicode 码点 当做整数的编码方式,解决了一些问题,但是 Unicode 码点 的问题在于,它能表示的 整数范围太小,只有 0 到 0x10FFFF。本文讲述 大整数范围 的表示方法。

语法

{i{min,max}}

这个语法足够简单,整数用十进制表达,min,max 可以为负数,也可以为空,为空时表示 (无穷):

{i{min,max}} 闭区间 [min,max]
{i{,max}} 区间 (-, max] ,表示所有 小于等于 max 的整数,max 可以为负数
{i{min,}} 区间 [min, +) ,表示所有 大于等于 min 的整数,min 可以为负数
{i{,}} 区间 (-, +) ,表示所有所有整数,包含所有正负数和 0
整数的位数 没有限制,例如可以是 100万位(十进制数)

注意

  • 以 '-' 开头的为负数
  • 数字可以为 0, 但 +0, -0 均为非法
  • 数字不能包含前导 0 (0 本身的 0 不算前导 0)
  • 正数不能包含 '+',这主要为了避免不必要的复杂性
    • 例如如果允许 '+',那么 '+0','-0' 呢,输入中的形式又是否要与表达式一致,等等

最简单的例子:IP 地址

({i{0,255}}."."){3}.{i{0,255}}

引号内的"."表示字符.,引号外的 . 表示串接{3} 表示重复 3 次,相比整数范围 [0,255]的正则表达式:

(0|[1-9]\d{0,2}|[1-9]\d?|1\d{2}|2[0-4]\d|25[0-5])

{i{0,255}} 是简单直接的。

复杂点的例子

RuleDB 支持联合索引,此处仅作为原理性展示

我们仍以 integer-fields.md 中的 gender_age_income 为例:

gender_age_income["0 ".{i{26,30}}." ".{i{12000,18000}}]
gender_age_income["0 ".{i{20,25}}." ".{i{-9000,-8000}}]
gender_age_income["0 ".{i{,30}}." ".{i{,12000}}]
gender_age_income["0 ".{i{,-30}}." ".{i{,-12000}}]
gender_age_income["0 ".{i{-30,}}." ".{i{-12000,}}]
gender_age_income["0 ".({i{-30,26}} | {i{28,32}})." ".({i{-12000,18000}} - {i{-6000,3000}})]
gender_age_income["0 ".{i{26,}}." ".({i{12000,}} & {i{9000,15000}})]
gender_age_income["0 ".{i{26,}}." ".({i{0,}} or {i{,-800}})]
gender_age_income["0 ".{i{26,}}." ".{i{,}}] \
  and tags(美食 and 运动 or 电脑 and 手机) \
  and books(红楼梦 and 水浒 or 了不起的盖茨比)

gender_age_income[ ... ] 表示对该字段执行全匹配,而不是子串匹配。 . 表示 concat 串接 操作,可以看到 "0 " 中 0 后面有个空格,年龄后面用 ." ". 串接了一个空格作为与收入字段的分隔符;相应地,输入中也要有空格作为分隔符(也可以使用其它字符例如 ,: 等做字段分隔符,只要规则与输入中的分隔符一致即可)。

不同的区间可以进行**并(|, or)、交(&, and)、差(-)**运算;多维数据 concat 串接 操作在这里的意义等价于笛卡尔积,等价于多维空间中的立方体(cube)。

gender_age_income 这样的条件可以和其它条件混合,例如上述带续行符 '' 的最后一条规则。

输入中 doc["gender_age_income"] 就类似这样(有匹配的也有不匹配的但没有非法的):

0 27 13000
0 23 -9001
0 23 -8999
0 230 -8999
0 230 17999
0 -230 -12001
0 -23 18999

非法的输入例如(非法输入会在 DFA 匹配过程中直接被判为不匹配):

+0 27 +13000
-0 23 -9001
0,23,-8999
0,+230 -8999
0:230:-17999 abc

原理

整数范围可以使用正则语言表达,从而可以转化为 DFA, n 位数 的范围对应的最小化 DFA 状态数为 O(n) ,这是一种很高效的表达方式。

字段之间使用分隔符分隔,从而各个字段不会混淆,并且对这些 DFA 进行并集运算来生成一遍扫描识别 regex_id 的全集 DFA 时也不会产生状态爆炸。

得出 regex_id 后再通过倒排表召回 rule_id ,然后执行 rule 表达式的虚拟机代码进行验证(整个规则表达式)

在进行 DFA 并集运算时,如果多个复合 regex 存在交集,算法会自动进行状态的合并与分裂。相比 rtree 等算法对多维 cube 的分裂与合并,DFA 最小化得到的结果是 理论最优 的,而不是启发式的“较优”。

在搜索时,就是用输入来匹配 DFA,时间复杂度是输入长度 n 的 O(n) ,也是理论最优的。 数学上,搜索一个字符串等价于搜索这个字符串代表的点位于数据库中的很多个多维立方体(cube)中的哪个立方体中。