lucene3.0.3中的SpanNearQuery（一）

SpanNearQuery和PhraseQuery是差不多的意思，都是表示多个term必须全部存在且距离满足一定的条件的query，但是SpanTermQuery的用法更多，比如他有一个inorder的参数，可以控制多个term出现的位置是不是要符合指定的顺序（phraseQuery就是可以不按照出现的顺序的）

构建一个SpanNearQuery需要三个参数，一个是多个SpanQuery，一个是多个spanQuery之间最大的距离slop，第三个是是否要求多个term出现的位置和传入参数的顺序相同，他的构造方法为：

public SpanNearQuery(SpanQuery[] clauses, int slop, boolean inOrder) {
    this(clauses, slop, inOrder, true);
}

 我在这个博客中将多个SpanQuery的getSpans方法生成的Span叫做subSpan。看一下这个类的getSpans方法：

public Spans getSpans(final IndexReader reader) throws IOException {
	if (clauses.size() == 0) // optimize 0-clause case
		return new SpanOrQuery(getClauses()).getSpans(reader);
	if (clauses.size() == 1) // optimize 1-clause case
        	return clauses.get(0).getSpans(reader);
	return inOrder ? (Spans) new NearSpansOrdered(this, reader, collectPayloads) : (Spans) new NearSpansUnordered(this, reader);
}

 我们忽略clauses==0和1的情况（因为这两个没有意义），直接看最后一种，他会根据各个term在某个doc中出现的顺序要不要符合传入的各个subQuery（也就是clause中的query）的顺序返回不同的Span，如果是inorder，则只有存在所有的term且各个term出现的位置是按照sunQuery的顺序且他们之间的距离的和小于指定的slop的doc才能被召回，如果不是inorder，则只要全部出现且各个term之间的距离的和小于指定的slop的doc就能被召回。

 

我们看看NearSpansOrdered的实现，一切还是从next方法入手

/**和termSpan一样*/
@Override
public boolean next() throws IOException {
	if (firstTime) {//初次调用，将每一个sunSpan都调用next方法，即读取第一个位置
		firstTime = false;
		for (int i = 0; i < subSpans.length; i++) {
			if (!subSpans[i].next()) {
				more = false;
				return false;
			}
		}
		more = true;
	}
	if (collectPayloads) {//这个是为了收集payload设置的，如果是收集payload的话每一个位置都要收集所以把之前的payload清空，collectPayloads是一个list<byte[]>，用于收集所有的subSpan的payload，
		matchPayload.clear();
	}
	return advanceAfterOrdered();//关键是这个方法，他会将所有的subSpan都读取到同一个doc上，然后判断的当前的doc是否满足需求。
}

  

private boolean advanceAfterOrdered() throws IOException {
	//因为所有的span都必须满足，所以必须调到相等的doc上，即调用toSameDoc方法。toSameDoc方法和booleanQuery在and的情况下生成的ConjunctionSumScorer中将所有的子query调整到同一个doc上的算法是一样的，这里不再重复了，都是使用的循环数组
	while (more && (inSameDoc || toSameDoc())) {
		if (stretchToOrder() && shrinkToAfterShortestMatch()) {
			return true;
		}
	}
	return false; // no more matches
}

 指执行完toSameDoc之后所有的subSpan都停留在同一个doc上，接下来要判断下当前doc上各个term出现的顺序是不是符合置顶的subQuery的顺序，这个是通过stretchToOrder方法实现的 

private boolean stretchToOrder() throws IOException {
	matchDoc = subSpans[0].doc();
	for (int i = 1; inSameDoc && (i < subSpans.length); i++) {//每两个进行对比，i从1开始。
		while (!docSpansOrdered(subSpans[i - 1], subSpans[i])) {//docSpansOrdered用于判断当前两个位置符合不符合要求（即不能重叠且按照顺序出现）。如果不符合顺序要求，则读取当前的span（也就是第i个span)在当前doc上的下一个位置。
			//进入while表示当前term的当前位置是不符合顺序的，则要读取下一个位置（当前term在当前的doc上可能出现了多次）
			if (!subSpans[i].next()) {//如果当前的span（里面封装了termPosition）已经读取玩了，也就是所有的位置都读取完了，则返回false。
				inSameDoc = false;
				more = false;
				break;
			} else if (matchDoc != subSpans[i].doc()) {//读取下一个位置时已经到下一个doc了，表示当前的doc上的所有的位置已经读取玩了，则返回false。
				inSameDoc = false;
				break;
			}
		}
	}
	return inSameDoc;
}

 

 经过上面的stretchToOrder方法，如果返回是true的话表示当前的doc是符合顺序的，接下来判断各个term的距离的和是不是小于指定的值，用 shrinkToAfterShortestMatch()方法来完成

 

private boolean shrinkToAfterShortestMatch() throws IOException {		
	matchStart = subSpans[subSpans.length - 1].start();
	matchEnd = subSpans[subSpans.length - 1].end();
	Set<byte[]> possibleMatchPayloads = new HashSet<byte[]>();//paylaod最后的结果
	if (subSpans[subSpans.length - 1].isPayloadAvailable()) {//这里添加了最有一个span的payload，因为现在选择的最后一个span一定是正确的，距离之和最小的所有的位置一定是现在的最后一个位置，不会再移动，所以下面的for循环使用的是subSpans.length - 2，也就是说从后面向前计算。
		possibleMatchPayloads.addAll(subSpans[subSpans.length - 1].getPayload());
	}
	//这个叫做possible，是因为他可能是一个合格的payload，也可能不是
	Collection<byte[]> possiblePayload = null;
	int matchSlop = 0;
	int lastStart = matchStart;
	int lastEnd = matchEnd;
        //for循环的思路是确定了最后一个，然后再向前计算。
	for (int i = subSpans.length - 2; i >= 0; i--) {
		Spans prevSpans = subSpans[i];
		if (collectPayloads && prevSpans.isPayloadAvailable()) {//这里并没有更新payload，因为当前的位置可能并不是最合适的，可能后面还有一个位置更合适呢。
			Collection<byte[]> payload = prevSpans.getPayload();
			possiblePayload = new ArrayList<byte[]>(payload.size());
			possiblePayload.addAll(payload);
		}
		int prevStart = prevSpans.start();
		int prevEnd = prevSpans.end();
		//他的目的是计算最小的slop
		while (true) { // Advance prevSpans until after (lastStart, lastEnd)
			if (!prevSpans.next()) {//当前的span已经穷尽
				inSameDoc = false;
				more = false;
				break; // Check remaining subSpans for final match.
			} else if (matchDoc != prevSpans.doc()) {//当前的span没有穷尽doc，但是下一个doc已经不是当前的doc
				inSameDoc = false; // The last subSpans is not advanced here.
				break; // Check remaining subSpans for last match in this
						// document.
			} else {//出现了多次，并且当前不是最后一次。
				int ppStart = prevSpans.start();//新的位置的开始
				//新的位置的结束
				int ppEnd = prevSpans.end(); // Cannot avoid invoking .end()
				//判断新位置和下一个span的位置是不是符合顺序，新位置只会比刚才的位置更靠后，所以不用和前面的对比只需要和后面的对比即可。
				if (!docSpansOrdered(ppStart, ppEnd, lastStart, lastEnd)) {//不符合顺序，不用继续向后找
					break; // Check remaining subSpans.
				} else { // prevSpans still before (lastStart, lastEnd)  仍然符合顺序，则更新当前的span的匹配位置，使其更加靠后，从这里可以发现，他是优先使用最小的距离来计算slop。继续循环，因为可能后面还有出现的位置
					prevStart = ppStart;
					prevEnd = ppEnd;
					if (collectPayloads && prevSpans.isPayloadAvailable()) {//当前的位置比上一个位置更靠后，则重新读取此位置的payload。
						Collection<byte[]> payload = prevSpans.getPayload();
						possiblePayload = new ArrayList<byte[]>(payload.size());
						possiblePayload.addAll(payload);
					}
				}
			}
		}
		//添加最后确定的payload到最后的结果中
		if (collectPayloads && possiblePayload != null) {
			possibleMatchPayloads.addAll(possiblePayload);
		}
		assert prevStart <= matchStart;
		if (matchStart > prevEnd) {// Only non overlapping spans add to slop.  对于紧邻的term，是不算入slop的，因为matchStart-prevEnd=0，紧邻的意思是matchStart==prevEnd
			matchSlop += (matchStart - prevEnd);
		}
		/* Do not break on (matchSlop > allowedSlop) here to make sure that subSpans[0] is advanced after the match, if any. */
		matchStart = prevStart;
		lastStart = prevStart;
		lastEnd = prevEnd;
	}
		boolean match = matchSlop <= allowedSlop;
		if (collectPayloads && match && possibleMatchPayloads.size() > 0) {
		matchPayload.addAll(possibleMatchPayloads);
	}
	return match; // ordered and allowed slop
}

 

 

这样按照顺序的SpanNearQuery就完成了，他的思路是第一步把所有的span都指向到同一个doc上，然后找到最前面的符合顺序的一组，这样就定死了最后的一个span（即顺序是spans.size - 1的那个），然后按照逆序挨个移动其前面的span（即先移动第span.size-2个），移动到超过下一个span的位置，然后记录在移动的过程中出现的在下一个span的位置之前的最靠近的位置，这样挨个移动，就可以计算出距离最小的一组了。然后再移动到下一组，直到某个span在这个doc上已经没有匹配的位置了位置。

 

这个方法在我看来特别耗cpu资源，因为他的操作太多了，如果某个doc上的符合要求的term特别多，就更慢了，因为会每个位置都会读取一次匹配一次，尤其是当使用的sunQuery比较多或者是当某个域比较大的时候对cpu的更大，所以谨慎使用这个query。下一篇博客中我将写一下不按照顺序的SpanNearQuery。