lucene的spanNearQuery（二）——不带有顺序的

 如果你觉得我的代码里有bug，可以联系我，我的qq是1308567317 。

 

一年前写了一篇文章介绍有顺序的spanNearQuery，地址为：http://suichangkele.iteye.com/blog/2348256，现在才会想起来，还有一篇没写呢，即没有顺序的spanNearQuery，今天在看之前的博客的时候，突然发现，所以写一下吧。

没有顺序的spanQuery的意思是，只要多个span挨着足够近的距离即可，不需要按照一定的顺序出现，而且也没有不能重叠的限制（在有顺序的SpanNearQuery中是有不能重叠的这个限制的）。在SpanNearQuery.getSpans(AtomicReaderContext, Bits, Map<Term, TermContext>)方法，即获得span的方法中

public Spans getSpans(final AtomicReaderContext context, Bits acceptDocs, Map<Term, TermContext> termContexts)	throws IOException {
	if (clauses.size() == 0) // optimize 0-clause case
		return new SpanOrQuery(getClauses()).getSpans(context, acceptDocs, termContexts);
	if (clauses.size() == 1) // optimize 1-clause case
		return clauses.get(0).getSpans(context, acceptDocs, termContexts);
	return inOrder ? (Spans) new NearSpansOrdered(this, context, acceptDocs, termContexts, collectPayloads)	: (Spans) new NearSpansUnordered(this, context, acceptDocs, termContexts);
}

 可以发现，如果没有指定顺序，则返回一个NearSpansUnordered，看看这个类的代码。

private SpanNearQuery query;
/** 存储的额是封装了span的东西，按照用户查询的顺序存储的 */
private List<SpansCell> ordered = new ArrayList<>(); // spans in query order
/** 所有的span */
private Spans[] subSpans;
private int slop; // from query

//这个链表是按照从小到大的顺序存放的，按照span的大小存放的。用于移动span到同一个doc
/**链表的头*/
private SpansCell first; // linked list of spans
/**链表的尾*/
private SpansCell last; // sorted by doc only
/** 多个subSpan（即子span）内部的长度，在计算整个slope的时候，要减去 */
private int totalLength; // sum of current lengths
/** 优先队列，用于找到当前最小的span和按照从小到大的顺序生成队列 */
private CellQueue queue; // sorted queue of spans
/** 所有的span中当前读取的doc最大的span或者是相同的doc中位置最后的span， 可以直接理解为位置最后的span */
private SpansCell max; // max element in queue

private boolean more = true; // true iff not done
private boolean firstTime = true; // true before first next()

public NearSpansUnordered(SpanNearQuery query, AtomicReaderContext context, Bits acceptDocs, Map<Term, TermContext> termContexts) throws IOException {
	this.query = query;
	this.slop = query.getSlop();
	SpanQuery[] clauses = query.getClauses();
	queue = new CellQueue(clauses.length);//优先队列，
	subSpans = new Spans[clauses.length];
	for (int i = 0; i < clauses.length; i++) {
		SpansCell cell = new SpansCell(clauses[i].getSpans(context, acceptDocs, termContexts), i);//这个就是封装了一个span，用来在更新span的next的时候记录所有的span中最大（即doc最大或者同样的doc但是位置最后）的span。
		ordered.add(cell);//这个是一个链表，在将多个span移动到同一个doc的时候使用，就像booleanQuery在合并多个AND的倒排表的时候的逻辑一样。
		subSpans[i] = cell.spans;
	}
}

 

他是将span用SpanCell封装了，封装的目的是在调用spanCell的next的时候，会顺别找到所有的span中的最大值（判断的标准在下面有）

private class SpansCell extends Spans {
	/** 封装的span */
	private Spans spans;
	private SpansCell next;
	/**封装的span当前匹配的长度*/
	private int length = -1;
	private int index;

	public SpansCell(Spans spans, int index) {
		this.spans = spans;
		this.index = index;
	}
	//他的next方法会更新max，因为优先队列是个最小堆，只能找到最小的对象，所以最大的对象要单独维护。
	@Override
	public boolean next() throws IOException {
		return adjust(spans.next());
	}
	@Override
	public boolean skipTo(int target) throws IOException {
		return adjust(spans.skipTo(target));
	}
	/**更新max值  */
	private boolean adjust(boolean condition) {
		if (length != -1) {
			totalLength -= length; //减去当前的长度，重新计算长度
		}
		if (condition) {
			length = end() - start();
			totalLength += length; // add new length
			if (max == null || doc() > max.doc() || (doc() == max.doc()) && (end() > max.end())) {//这个就是最大的值得判断条件，如果docid更大，则更大，如果docid相等，则找位置最大的。
				max = this;
			}
		}
		more = condition;
		return condition;
	}
	还有很多方法省略，都是直接调用的封装的span的方法。
}

 看看最重要的next方法：

@Override
public boolean next() throws IOException {
	if (firstTime) {//
		initList(true);
		listToQueue();//构建优先队列
		firstTime = false;
	} else if (more) {
		if (min().next()) { // 更新堆鼎的对象，读取下一个位置，现在可能就不在同一个doc上了
			queue.updateTop(); // maintain queue
		} else {
			more = false;
		}
	}
	
	while (more) {
		boolean queueStale = false;//是否优先队列失效，即要不要重新构建优先队列
		if (min().doc() != max.doc()) {//如果不是在同一个doc上，则重置链表，按照span大小排序，因为下面要移动到一个doc上，此时最好用链表，因为使用优先队列的成本太大了。这里体现了使用优先队列的用处，即用于构建一个有顺序的链表。
			queueToList();
			queueStale = true;
		}
		// 将所有的span都移动到一个doc上！这里不重新构建优先队列，因为代价太大。
		while (more && first.doc() < last.doc()) {
			more = first.skipTo(last.doc());
			firstToLast(); // and move it to the end
			queueStale = true;
		}
		if (!more)
			return false;
		
		if (queueStale) {//重建优先队列，因为这样建立的话，成本会比较小
			listToQueue();
			queueStale = false;
		}
		
		if (atMatch()) {//如果满足条件，则找到了
			return true;
		}s

		more = min().next();//如果不满足条件，即最大的位置和最小的位置的差太大，则读取最小的位置，这个方法中就会更新max的值。min方法就是获得优先队列中堆顶的元素
		if (more) {
			queue.updateTop(); //更新队列中最小的对象
		}
	}
	
	return false; // no more matches
}

 queueToList这个方法用于构建一个链表，他的目的是用于将所有的span移动到同一个doc上，做这个操作要使用链表，使用链表的原因是使用优先队列的话会比较耗时。处处体现了solr的作者的精明与仔细。这么优秀的代码，太值得学习了

还剩最后一个关键的代码atMatch，即判断当前所有的span的位置是否满足条件，别忘了现在所有的span都在同一个doc上，

private boolean atMatch() {
	return (min().doc() == max.doc()) && ((max.end() - min().start() - totalLength) <= slop);
}

max就是位置最后的span，min就是位置最前的span，他们现在在同一个doc上，要求是最后一个位置的结束位置减去最前面的位置的开始位置小于slop，还要减去这其中每个span的位置的长度，（这个地方有点让我很疑惑，为啥要减去呢？但是没大问题，我们可以修改一下这个的代码，去掉这一部分）。

对于让我很疑惑的totalLength，我自己做了一个实验，我用 java php cpp net c go erlang这几个词做的索引，然后使用java go erlang查询，slope是3的时候就查不到，但是大于3就可以查到，可以erlang这个span的end是7，java的start是0，如果没有totalLength的话，明显是不匹配得，所以这个totalLength应该是考虑了span的个数。如果读者有更好的理解的话，可以联系我，我的qq是1308567317

 

这样就看完了没有顺序的。他的要求是在一个doc上最后面的一个位置减去最前面的额位置的差小于一个值，但是也考虑了span的个数（即totalLength）。