Lucene3.0源码分析(三) Lucene对多个Term查询的结果取交集算法

       本博客属原创文章,欢迎转载！转载请务必注明出处:http://guoyunsky.iteye.com/blog/724989

      欢迎加入Heritrix群(QQ)：109148319

 

      当查询 "Java AND Lucene" 的时候,需要对Java跟Lucene这个两个Term的查询结果取交集,也就是对查询到他们的DocumentID取交集,然后对获取到交集的DocumentID，根据评分,获得评分前N的DocumentID(至于Lucene获得评分前N的DocumentID算法,我请查看我这篇博客:Lucene3.0源码分析(二) Lucene中获得评分前N的DocumentID算法

),最终获得这些DocumentID的数据返回给用户。

       我这里模仿Lucene中的算法,具体请看一下Java代码以及注释,同时这些Java代码不依赖Lucene任何组件,可以单独运行。

      

import java.util.Arrays;
/**
 * 对有序数组取交集,数组必须按照从小到大排序
 * 模仿Lucene的合并子查询条件结果集
 * 
 * @author Administrator
 *
 */
public class MyConjunctionScorer {
	private MyScorer[] scorers=new MyScorer[2];
	private int length;		// 子评分器个数
	private int first=0;	// 迭代子评分器的起始指针位置
	private int last=-1;	// 迭代子评分器的终止指针位置
	
	private boolean more;	// 是否还有子查询条件以及里面是否还有DocumentID
	private boolean hasInit;// 是否已经初始化	
	
	public MyConjunctionScorer() {
		
	}
	
	/**
	 * 添加子查询条件评分器
	 * 
	 * @param scorer
	 */
	public void add(MyScorer scorer){
		needExpansion();
		length++;
		last++;
		scorers[last]=scorer;	
	}
	
	public boolean next(){
		if(!hasInit){	//首先初始化
			init();
			hasInit=true;
		}else if(more){
			more=scorers[last].next();	//获得下一个要匹配的数据,也就是上一次获取的结果数据的下一个数据
		}
		return doNext();
		
	}
	
	public int doc(){
		return scorers[first].doc;	//返回交集documentID
	}
	
	public boolean doNext(){
		while(more&&scorers[first].doc<scorers[last].doc){	//如果要比较的子查询条件评分器的DocumentID一直比last的DocumentID小则一直迭代
			more=scorers[first].SkipTo(scorers[last].doc);	// 从first中找到比last大的DocumentID
			last=first;										// 则以first为基准跟其他子评分器查询条件进行比较
			first=(first==length-1)?0:first+1;				// 指针后移，获得其他子查询条件评分器跟last指针位置的子查询条件评分器进行对比
		}
		return more;
	}
	
	/**
	 * 初始化
	 */
	public void init(){
		more=length>0;
		for(int i=0,pos=first;i<length;i++){
			if(!more){
				break;
			}
			more=scorers[pos].next();//获取子查询条件评分器下一个DocumentID,有的话返回true,没有的话则false
			pos=(pos==length-1)?0:pos+1;	//位置叠加,让每个子查询条件评分器可以进行迭代
		}
		if(more){	//如果每个子查询条件评分器里有DocumentID
			sortScorers();	//先对每个子查询条件评分器根据当前的DocumentID进行排序
		}
	}
	
	/**
	 * 排序
	 */
	public void sortScorers(){
		needExpansion();		//是否要扩容
		Arrays.sort(scorers);	//排序
	}
	
	/**
	 * 扩容
	 */
	public void needExpansion(){
		if(length>=scorers.length){
			MyScorer[] tmpScorers=new MyScorer[scorers.length*2];
			System.arraycopy(scorers, 0, tmpScorers,0,length);
			scorers=tmpScorers;
			
		}
	}
	
	public static void main(String[] args){
		int[] s1={3,4,5,6,7,8,9};
		int[] s2={2,3,9};
		int[] s3={3,4,5,9};
		
		MyScorer sc1=new MyScorer(s1);
		MyScorer sc2=new MyScorer(s2);
		MyScorer sc3=new MyScorer(s3);
		
		MyConjunctionScorer conScorer=new MyConjunctionScorer();
		conScorer.add(sc1);
		conScorer.add(sc2);
		conScorer.add(sc3);
		
		while(conScorer.next()){
			System.out.println(conScorer.doc());
		}
		
		
	}
}

 

/**
 * 模仿Lucene的TermScorer(子查询条件评分器)
 * 
 * @author Administrator
 *
 */
public class MyScorer implements Comparable{
	
	private int[] docs;		//所有DocumentID
	public int doc;			//当前DocumentID
	private int pointer;	//当前指针
	private int pointerMax;	//所允许的最大范围
	
	/**
	 * 获得当前指针位置
	 * @return
	 */
	public int getPointer() {
		return pointer;
	}
	
	/**
	 * 比较两个MyScorer大小,通过当前DocumentID进行比较
	 */
	@Override
	public int compareTo(Object arg0) {
		if(arg0 instanceof MyScorer){
			MyScorer s=(MyScorer)arg0;
			return this.doc-s.doc;
		}
		return 0;
	}
	
	public MyScorer(int[] docs) {
		super();
		this.docs = docs;
		doc=-1;
		pointer=-1;
		pointerMax=docs.length;
	}
	
	/**
	 * 获取下一个DocumentID
	 * @return
	 */
	public boolean next(){
		pointer++;
		if(pointer>=pointerMax){
			pointer=0;
			return false;
		}
		doc=docs[pointer];
		return true;
	}
	
	/**
	 * 指针跳转到大于或等于目标documentID值,然后接下来可以通过指针位置获取该值
	 * @param target
	 * @return
	 */
	public boolean SkipTo(int target){
		for(pointer++;pointer<pointerMax;pointer++){
			if(docs[pointer]>=target){
				doc=docs[pointer];
				return true;
			}
		}
		return false;
	}
	
	
}

 

更多技术文章、感悟、分享、勾搭，请用微信扫描:

评论

1 楼 linliangyi2007 2010-11-11  

这个算法很不错，可以略作修改后，进行分布式的翻页查询，更深入的说，是一种mapreduce的实现基础