我看了3个下午,加上一个上午终于看懂了lucene对于数字的索引和对于数字范围的检索,主要的时间都是花在了NumericRangeQuery上,尽管一次一次的失败但是我并没有放弃的打算,研究与探索本来就是我的一大兴趣,最后的喜悦要比之前所有的痛苦都要来的爽!谢谢笔记,方便可能正在迷茫的你。备注:如果你对lucene的索引格式不熟悉尤其刚接触lucene的话,请绕行,这片笔记只适合对源码有深入研究的程序员。
对于数字的索引并不是直接将数字变为字符串,因为这样的话没法进行范围搜索,比如我们索引1、5、20、56、89、200、201、202、203...299、500,如果按照lucene的字符排序,这些term在词典表中的排序为1、20、200、201、202、203...299、5、56、500、89,显然他的顺序是没有用于范围查询的,如果我们要进行范围搜索1-300的话,我们就要穷尽所有该域下的term,因为可能有以9开头的term,但是他出现在所有的term的最后面,所以明显按照字符顺序排序不是最好的排序方式。我们看卡luene是怎么样存储的,对于数字的域,是使用lucene的NumeircField,他里面有个最重要的属性是TokenStream——NumericTokenStream,它用来将这个域的数字进行分词(也就是形成一个特里树),看下他的incrementToken方法,该方法用于对数字进行分词,这里我们以long(也就是64位作为例子)型的数字作为例子,进行分词的方法是调用的NumericUtils.longToPrefixCoded方法:
/** 将一个数字值分多次进行shift,一次处理precisionStep的位数 */ @Override public boolean incrementToken() { if (valSize == 0) throw new IllegalStateException("call set???Value() before usage"); if (shift >= valSize) return false; clearAttributes(); final char[] buffer; switch (valSize) { case 64: buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_LONG); // 将数字变为字符,返回的字符内容放入buffer中 // 每调用一次会形成一个字符串,放入到buffer中,所以关键的就是这个方法,他会使用到当前已经处理的位数已经精度的位数 termAtt.setTermLength(NumericUtils.longToPrefixCoded(value, shift, buffer)); break; case 32: buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_INT); termAtt.setTermLength(NumericUtils.intToPrefixCoded((int) value, shift, buffer)); break; default: // should not happen throw new IllegalArgumentException("valSize must be 32 or 64"); } typeAtt.setType((shift == 0) ? TOKEN_TYPE_FULL_PREC : TOKEN_TYPE_LOWER_PREC); posIncrAtt.setPositionIncrement((shift == 0) ? 1 : 0);//第一次的时候表示是一个数字,非第一次为0表示是同一个数字,所以位置增量是0 shift += precisionStep;//增加偏移量 return true; }
在上面的方法中有两个重要的属性,一个是shift,一个是precisionStep,在计算机中,数字用二进制表示,在进行分词的时候他的思路是每次都向左偏移precisionStep的位数,被偏移过的数字都被忽略,而剩余的数字则形成一个字符串,precisionStep就是每次都偏移的二进制的位数,而shift表示现在已经偏移过的总的位数,我们看下NumericUtils.longToPrefixCoded的源码:
public static int longToPrefixCoded(final long val, final int shift, final char[] buffer) { if (shift > 63 || shift < 0) throw new IllegalArgumentException("Illegal shift value, must be 0..63"); // 计算本次处理的所有的位数要生成的char的个数,计算的规则为 64-已经处理的位数(也就是shift)然后除以7,因为后面用每7个bit位形成一个字符,(63-shift)/7 + 1等价于这个意思。 int nChars = (63 - shift) / 7 + 1; // 这个是本次处理的所有的位数加上记录偏移量的字符产生的char的总个数,比上面的多一的原因是第一个字符用于存储偏移量,偏移量用32+shift表示,形成一个字符。 int len = nChars + 1; // 填写第一个字符——偏移的位数,为32+shift 用第一位表示偏移量也是有原因的,因为偏移量越大他的位数也就越高,那么表示的数也就越大(所有的数字在存储时都是有偏移量的,刚上来的是偏移量为0), 这一点和字符串的字符顺序也是对应的,如果高位(靠左边)更大则这个字符串会排在后面(即 bx 一定在ax后面) buffer[0] = (char) (SHIFT_START_LONG + shift); //0x8000000000000000L这个数字是第64位为1,其他位为0。抑或他的目的是将最高位取反,也就是如果原来是正数符号位变为1,负数的符合位变为0。通过这个操作后,所有的负数排在正数的前面,且正数的相对位置不变,负数的也不变化。(此步骤自己想,我在这里不做解释) long sortableBits = val ^ 0x8000000000000000L; sortableBits >>>= shift; //不计算已经shift的位数,只计算还剩余的位数。 while (nChars >= 1) { //循环,每7位处理一次,这里之所以用7位形成一个字符也是有原因的,因为最终在磁盘上是使用utf-8格式,7位的话最大是127,在127以下时utf8编码采用的是一个字节表示一个字符,这时最节省空间。 // Store 7 bits per character for good efficiency when UTF-8 encoding. // The whole number is right-justified so that lucene can // prefix-encode the terms more efficiently. 。 // 只取最后的7个bit,形成一个char。也就是每7个bit形成一个char,放入到buffer中 buffer[nChars--] = (char) (sortableBits & 0x7f); sortableBits >>>= 7;//继续处理下一个7位 } return len; }
上面的方法用二进制描述不太形象,我们用十进制来举个例子,假设我们要索引的是8153这个数字,我们的precisionStep是1,也就是每一次偏移一个十进制的位,第一次shift是0,所以整个8152会形成一个字符串,外加上用于存储偏移量的位数(在这里我们省去用来表示偏移量的位数,并直接用数字的字符串形式作为最终形成的字符串),所以第一次形成的字符串是8153,第二次是815(但是偏移量是1),第三次是81(偏移量是2),第四次是8(偏移量是3),所以很容易发现他是一个特里结构,他形成的这四个term的意思也可以这样理解,8xxx的或者是81xx的或者是815x的,还有最精确的8153都是可以搜索到当前的文档。现在我们把precision变大一点,为两个十进制的位,则会形成8153和81,他表示在8153和81xx这两个term都可以搜到这个document。可以发现,当precision更小的时候,会生成更多的term,那么索引也一定会更大(如果precision过大,其实在进行范围搜索的时候会降低速度,这个到搜索的时候再说)。当我们在索引别的数字的时候就会继续形成不同的term,所有的这些term会最终组成一个特里树,并且precisionStep越小这个树的节点就会越多,最终的索引的体积也会越大。
搜索:NumericRangeQuery 这个类用于使用特里树进行范围的搜索,他的关键是对要进行搜索的范围进行分词,找到在特里树上的节点(也就是之前建立索引时声称的term)然后再按照重写规则对所有找到的term进行重写,比如声称一个booleanQuery,或者是生成一个filter,就这么简单,但是他花费了我很长的时间才看懂。NumericRangeQuery最关键的部分就是找到之前的term,通过调用它的getEnum方法,该方法返回了一个NumericRangeTermEnum,我们看看它的代码:
// 将查询区间分解成若干个小的查询区间 NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() { @Override public final void addRange(String minPrefixCoded, String maxPrefixCoded) { rangeBounds.add(minPrefixCoded); rangeBounds.add(maxPrefixCoded); } }, precisionStep, minBound, maxBound);
上述方法就是根据要查找的区间范围(也就是最大值和最小值)以及prerecisionStep,找到形成的特里树上的节点,将这些节点放入到一个链表里面,提一句,在NumericRangeTermEnum的构造方法里面,已经将所有的对比转化为>=或者是<=,我们看一下NumericUtils.splitLongRange方法
/** 将查询区间分解成若干个小的查询区间*/ private static void splitRange(final Object builder, final int valSize, final int precisionStep, long minBound,//下线 long maxBound/*上线*/) { if (precisionStep < 1) throw new IllegalArgumentException("precisionStep must be >=1"); if (minBound > maxBound) return; for (int shift = 0;; shift += precisionStep) { // calculate new bounds for inner precision final long diff = 1L << (shift + precisionStep); final long mask = ((1L << precisionStep) - 1L) << shift;//当前精度范围的最大值 // minBound在本次处理的精度内有没有要限制的部分,如果等于0说明是本精度范围内没有任何限制,也就是本精度范围的任何值都是可以的。继续匹配上一个精度即可。 // 如果是true,则说明本精度范围要添加限制,所以在后面有addRange (看下面的解释1)。 final boolean hasLower = (minBound & mask) != 0L; // 因为mask是次精度范围的最大值,如果等于mask说明本层次的所有值都符合要求,不等于说明是有限制的,有的term是不包含的。 // 如果是true,则本精度要添加限制,所以后面有addRange (看解释2) final boolean hasUpper = (maxBound & mask) != mask; // 如果在当前区间有值的话就会要加diff,即下一次的区间一定要大于下一个精度的最小值(也就是加一个下一个精度的最小值),然后把当前的精度的限制去掉之后 // 比如十进制中的 632,precisionStp是1,在把632中的2删掉之后,不能仅仅是63x,因为这样话,631 630也会匹配,所以要加一个十进位的1,表示64x的任意值都是可以的,而不是63x。 final long nextMinBound = (hasLower ? (minBound + diff) : minBound) & ~mask;//&~mask 将shift到shift+precisionStep位变为0. // 道理和上面的一样,比如十进制中的对比,如果最后一位是9的话则任何本精度的值都会满足,则直接对比下一个精度即可,如果maxBound是765,则不能仅仅是删掉最后的精度5,因为单纯的76x并不能完全限制, // 因为769 768 这样的值在第二个精度的时候也会满足条件。所以必须减小一位下一个精度,也就是使用75x是可以的。 final long nextMaxBound = (hasUpper ? (maxBound - diff) : maxBound) & ~mask; // 这两个是极端的情况,看下面的解释三 final boolean lowerWrapped = nextMinBound < minBound; final boolean upperWrapped = nextMaxBound > maxBound; // 1、第一个判断是有没有下一个精度 // 2、第二个判断是下一个精度是不是交叉,即最小值比最大值要大,如果是这样,就不再对比了,因为在继续下去仍然是最小值大于最大值。 // 3、4的原理在解释3、4中 if (shift + precisionStep >= valSize || nextMinBound > nextMaxBound || lowerWrapped || upperWrapped) { // We are in the lowest precision or the next precision is not available. addRange(builder, valSize, minBound, maxBound, shift); // exit the split recursion loop break; } if (hasLower) //添加最小的区间限制 addRange(builder, valSize, minBound, minBound | mask, shift);//minBound是当前精度的最小值,minBound|mask表示当前精度的最大值, if (hasUpper) //添加最大的区间限制 addRange(builder, valSize, maxBound & ~mask, maxBound, shift); minBound = nextMinBound; maxBound = nextMaxBound; } }
解释1:final boolean hasLower = (minBound & mask) != 0L; 如果minBound和当前精度的最大值做对比等于0,说明minBound在当前精度范围的所有位都是0,那么次精度范围任何一个值都满足>=0的要求,所以他就不用添加一个节点了,此精度范围内不会形成一个限制的节点,继续减小精度即可。相反,如果当前精度范围内是有限制的,也就是不是最小值,那么就要添加一个限制的节点用来限制查找的结果,所以当前为true的时候,会在后面添加addRange方法(等会再看)。
解释2:final boolean hasUpper = (maxBound & mask) != mask,如果maxBound 和当前精度的最大值相等,则在当前精度范围内,所有的值都会满足<=maxBound的要求,这是就不用添加当前精度的限制了,继续减小精度即可。
解释3:nextMinBound < minBound; 貌似是所有的nextMinBound都要大于minBound,因为nextMinBound都加上了下一个精度的最小值,怎么可能比minBound小呢?其实不是,因为他是有64位或者是32位限制的,我们还是用10进制来描述,因为计算机中有32位 64位的限制,我们在10进制中用3位的限制,所以我们在处理997的时候,已经在处理过最后的7之后,我们要加上10,再删除最后的一位,则就会变为100x,由于3位的限制,所以就会变为00x,这里的判断就是这种情况。当出现这种情况时,说明minBound已经是下一个精度范围的最大值了,现在已经不能继续往特里树的根前进了,所以要退出查找更多term的循环。
解释4:nextMaxBound > maxBound;道理和上面的3一样,我们还是举10进制的例子:比如我们处理的是003,precisionStep是1,十进制的位数限制为3,,现在处理的3,然后前往下一个precisionStep,减10,则变为负数了,所以就会出现这种情况,他的意思是已经无法再特里树里面找到更深的节点了。
addRange方法:最终还是调用的longToPrefix方法,将数字变为字符串,然后放入到一个链表里面,对于每一次调动都会添加两个term。
我们再看一下最后他是如何使用产生的这些term的,在org.apache.lucene.search.NumericRangeQuery.NumericRangeTermEnum.next()方法中
/** Increments the enumeration to the next element. True if one exists. */ @Override public boolean next() throws IOException { //这里的操作貌似没有必要关闭当前的termEnum,为什么不通过调用一个termEnum不停的读呢?为什么还要关掉然后重新打开? //因为在搜集词典表中的term的时候,他们不是挨着的,还有一个原因是特里树里面的限制性的节点限制的term通过从前向后读取是读取不到的,要重新从头读取,不一点不像一般的term的查找, //而通过使用词典表的索引(通过使用3.0中的tii文件),也就是在下面while中的创建termEnum的方式,可以更加快速的找到要查找的term。 // if a current term exists, the actual enum is initialized: // try change to next term, if no such term exists, fall-through if (currentTerm != null) { assert actualEnum != null; if (actualEnum.next()) { currentTerm = actualEnum.term(); if (termCompare(currentTerm)) return true; } } // if all above fails, we go forward to the next enum, if one is available currentTerm = null; while (rangeBounds.size() >= 2) {//只要还剩最后的两个,也就值最后退出循环的addRange assert rangeBounds.size() % 2 == 0; // close the current enum and read next bounds if (actualEnum != null) { actualEnum.close(); actualEnum = null; } final String lowerBound = rangeBounds.removeFirst();// this.currentUpperBound = rangeBounds.removeFirst(); // create a new enum actualEnum = reader.terms(termTemplate.createTerm(lowerBound)); currentTerm = actualEnum.term(); if (currentTerm != null && termCompare(currentTerm)) return true; // clear the current term for next iteration currentTerm = null; } // no more sub-range enums available assert rangeBounds.size() == 0 && currentTerm == null; return false; }
他的思路是根据产生的用来作为限制条件的term,来查找处于他们区间的所有term,所以到这里思路就明朗起来了,概括一下:他是根据maxBoung和minBound和precisionStep产生多个限制的term,然后根据这些限制性的term在词典表中来查找所有的处于他们去见的term,使用这个办法的好处是:他能减少对叶子节点的使用,因为在生成所有的限制性term的时候,都是使用的特里树的父节点,以及父节点的父节点,直到已经没有父节点了或者是maxBound和minBound相互交叉,这样在查找的时候词典表就会绕过大量的term,只寻找在限制性节点之间的term,使得搜索到的term的数量大大减少,从而加速搜索的速度。
在搜索时使用的precisionStep的大小的影响:此值越大,则生成的特里树深度越浅,限制性节点的范围越大,查找到的term的数量就会更多,在合并倒排表的时候就会越慢;此值越小,则生成的特里树的深度越大,限制性节点的个数越大,搜索到的term的数量越小,合并时的速度越大。
相关推荐
盘古分词 lucene3.0.3 使用 示例 可以方便地整合到项目中使用,.net 4.0的。有分页功能。新加根据分类索引功能。
lucene3.0.3搜索的使用示例lucene3.0.3搜索的使用示例lucene3.0.3搜索的使用示例
Lucene 3.0.3 API Lucene 3.0.3 Lucene
盘古分词 lucene3.0.3 使用 示例 可以方便地整合到项目中使用,.net 4.0的。
盘古分词 lucene3.0.3 使用 示例 可以方便地整合到项目中使用,.net 4.0的。新加分页功能。
lucene3.0.3.core.jar文件,不用到apache官方网站下载17M的包,直接下载这个core就可以了。
Lucene是一个基于Java的全文索引工具包。
Lucene3.0.3+盘古分词的实现用到的dll文件,带词库文件。已证实可用,可指定使用自己维护后的词库文件。
基于lucene技术的增量索引,实现索引的首次创建,动态增删改
整理开发Lucene+盘古分词 开发搜索引擎用到的所有必备资源 亲测可用
lucene 对 xml建立索引 建立索引就是怎么简单 呵呵
Lucene3.0分词系统.doc
Lucene创建索引,查询索引的简单使用。
这是Lucene.NET v3.0.3 DEMO范例程序(含PanGu分词),用C#语言编写的,同时对PanGu分词进行了整合,可以直接下载运行。 项目中还整理了一个后台任务线程监听范例,可以用作增量索引创建,但这个需要你自行加入相关...
lucene-smartcn-3.0.3.jar
Apache Lucene.Net 3.0.3 just passed a vote for release - our first official release since graduating from the incubator in August. A lot of work was put into porting and testing the code. We've ...
lucene-3.0.3.zip 官方版
在Eclipse环境中运用java,Lucene建索引及查询关键字
Lucene索引器实例Lucene索引器实例Lucene索引器实例Lucene索引器实例