tofacebook.com -专业IT技术社区 【百家号】脸书百科,Lucene的数值索引以及范围查询 Web程序 - tofacebook.com-专业IT技术社区
72°

【百家号】脸书百科,Lucene的数值索引以及范围查询 Web程序

标签:因此   The   分系统   简单   基本   ring   情况   get   引擎   

对文本搜索引擎的倒排索引(数据结构和算法)、评分系统、分词系统都清楚掌握之后,本人对数值索引和搜索一直有很大的兴趣,最近对Lucene对数值索引和范围搜索做了些学习,并将主要内容整理如下:

1. Lucene不直接支持数值(以及范围)的搜索,数值必须转换为字符(串);

2. Lucene搜索数值的初步方案;

3. Lucene如何索引数值,并支持范围查询。

 

1. Lucene不直接支持数值搜索

Lucene不直接支持数值(以及范围)的搜索,数值必须转换为字符(串)——这是由倒排索引这个核心所决定,lucene要求term按照字典序(lexicographic sortable)排列。如果只是简单的将数值转为字符串,会带来很多的问题:

 

2. Lucene搜索数值的初步方案

2.1 如直接保存11,24,3,50,按照字典序查询范围[24,50],会将3一起带出来。这个问题有个简单的解决方案,就是将字符串补全成定长的串,如000011,000024,000003,000050。这样就能解决[000024,000050]这样的字符范围查询。

2.2 建立索引的时候,term按照数字顺序排序,上面的例子以3,11,24,50,搜索也能正确。

显而易见,上述方案有“硬伤”:

 2.1方案的问题是,固定多少位难以控制,补的位数多则浪费空间,少则存储的数值范围有限;

 2.2方案的问题是,对范围[24,50]查询,必须要展开成25,26...50,这样Boolean query查询效率会低到无法接受。

 

3. Lucene如何索引数值,并支持范围查询

  首先可以把数值转换成字符串,且保持顺序。也就是说如果 number1 < number2 ,那么transform(number) < transform(number)。transform就是把数值转成字符串的函数,如果拿数学术语来说,transform就是单调的。

  *注意, 数字做索引时, 只能是同一类型, 例如不可能是同一个field, 里面有int, 又有float的.

 

 3.1 Lucene 对NumericField建索引的时候,首先把Numeric Value转成 Lexicographic Sortable Binary然后根据某个步长(Precision Step 后面详说)不断右移然后转换成 Lexicographic Sortable String建索引,本质上相当于建了一个Trie。

  怎么把numeric value转成  Lexicographic Sortable Binary 所有的Byte的词典顺序就是Numeric顺序。

  对于Long 二进制表示方式 http://en.wikipedia.org/wiki/Two‘s_complement

  最高位是符号位0表示正数 1表示负数。对于正数来说低63位越大这个数越大,对于负数来说也是低63位越大(0xFFFFFFFFFFFFFFFF是-1,最大的负整数)这个数越大。所以只要把符号位取反Long就可以按字节映射成一个 Lexicographic Sortable Binary了。

 对于Double 二进制表示方式 http://en.wikipedia.org/wiki/Binary64

How <wbr>Lucene <wbr>NumericRangeQuery <wbr>works

The real value assumed by a given 64-bit double-precision datum with a given biased exponent  and a 52-bit fraction is

How <wbr>Lucene <wbr>NumericRangeQuery <wbr>works

对于正Double来说低63位越大这个数越大,对于负Double来说低63位越大这个数越小。负数情况和Long是相反的,因此对于小于0的Double把低63位取反,然后和Long相同再把符号位取反,Double就可以按字节映射成一个 Lexicographic Sortable Binary了。

对于Int和Float 32位的类型一样道理,就不赘述了。

 

 3.2 利用Trie的性质把RangeQuery分解成尽量少TermQuery,然后用这些TermQuery做搜索就可以了

原理就是Shift从0开始以precisionStep为步长递增,对每一个Shift试图找到最多两个子Range:Lower和Upper,然后中间的Range继续递归直到break发生,这时的Range成为Center Range。当Shift=n时,对于split出来的Range满足把minBound的低Shift位全部置0和把maxBound的低Shift位全部置1后之间的所有数值都在要查询的Range中。基本思想和树状数组类似。

 

看例子更容易明白比如[1, 10000]这个Range,通过splitRange出来的Range:

Shift: 0  

Lower: [0x1,0xF],  表示从1到15

Upper: [0x2710,0x2710] 表示10000到10000

Shift: 4

Lower:[0x10, 0xF0]   表示从16(0x10)到255(0xFF) 

Upper:[0x2700, 0x2700]  表示从9984(0x2700)到 9999(0x270F)

Shift: 8

Lower: [0x100,0xF00]  表示从256(0x100)到 4095(0xFFF)

Upper: [0x2000,0x2600] 表示从8192(0x2000)到9983(0x26FF)

Shift: 12

Center: [0x1000, 0x1000] 表示从4096(0x1000)到8191(0x1FFF)

一共7个Range最后一个Range是Center Range, 这7个Range也正好覆盖了[1,10000]

 

addRange中会对每个split出来的Long Range的minBound和maxBoud右移Shift位然后转成Lexicographic Sortable String,最后和建索引时一样在前面加一个Byte表示Shift。因为Shift是以precisionStep为步长递增的,所以splitRange出来的多个Lexicographic Sortable String Range是递增的(Pair顺序比较)。这样查找所有属于这些Range中的Term,只需要对这个field一直seek forward,不需要seek backward。

 

对于上面的例子,这7个Range转换成Lexicographic Sortable String, 然后用这些Range去查找所有属于这些Range范围内的Term。

比如shift: 8

Lower: [0x100,0xF00]  表示从256(0x100)到 4095(0xFFF)

0x100,最高位变成1  成为 0x80,00,00,00,00,00,01,00  然后右移8位变成 0x80,00,00,00,00,00,01 然后每7个bit变成一个Byte成为

0x40, 00, 00, 00, 00, 00, 00,01

0xF00 同理变成0x40, 00, 00, 00, 00, 00, 00,0F。

在最前面加一个Byte表示Shift那么最终的Lexicographic Sortable String

0x100  -> 0x28,40, 00, 00, 00, 00, 00, 00,01

0xF00  -> 0x28,40, 00, 00, 00, 00, 00, 00,0F

第一个Byte 0x28表示Shift为8,0x20是偏移量,区分不同数值类型。

这样如果要查找[256, 4095]的数值共有3840个,那么只需要查找15个Term  

 0x28,40, 00, 00, 00, 00, 00, 00,01 ~  0x28,40, 00, 00, 00, 00, 00, 00,0F

整体来看[0, 10000]之间共1000个数值,最多需要查找的Term数量是55个。

[0x1,0xF]               15 

[0x2710,0x2710]         1 

[0x10, 0xF0]             15

[0x2700, 0x2700]         1

[0x100,0xF00]           15 

[0x2000,0x2600]         7

[0x1000, 0x1000]         1

如果不做Trie树,那么需要最多遍历查找10000个Term。

 

理论上对于precisionStep=4时一个Range最多需要查找多少个Term?

根据splitRange可以看出除了最后一次Shift,前面的每次Shift最多产生两个Range(Lower 和 Upper),最后一个Shift产生的是Center Range。

64位的数字Value最多Shift  64/4=16次。 所以最多有Lower和Upper最多各15个Range, Center 1个Range,每个Range最多覆盖15个Term。

为什么不是16个Term?16个Term的话,这个Range的存在是没有意义可以进位到下一个Shift。

只有一种情况是特殊的就是无法进位的时候,比如Range是[Long.MIN_VALUE, Long.MAX_VALUE]  只得到一个Center Range在Shift=60时,覆盖了16个Term的。

所以理论上对precisionStep=4,最多需要查找的Term   31个Range * 15个Term/Range = 465

更一般的结论

  n = [ (bitsPerValue/precisionStep - 1) * (2^precisionStep - 1 ) * 2 ] + (2^precisionStep - 1 )

precisionStep=8, n=3825

precisionStep=2, n=189

显然precisionStep越小n越小,但是precisionStep越小意味着对每个Field需要index的Term越多,对64位的数值需要index的Term是64/precisionStep。

 

以上主要讨论了LongField的搜索,对于DoubleField只是需要做一步处理就是对于小于0的Double,低63位取反,接下来和LongField完全相同流程。对于Int和Float只是数值类型从64位变成32位了,其余的都一样。

Lucene的数值索引以及范围查询

标签:因此   The   分系统   简单   基本   ring   情况   get   引擎   

原文地址:https://www.cnblogs.com/fan-yuan/p/9360411.html


本文由百家号/熊掌号作者上传并发布,百家号仅提供信息发布平台。文章仅代表作者个人观点,不代表百度立场。

已有 0 条评论

    我有话说: