MyException - 我的异常网
当前位置:我的异常网» 开源软件 » lucene的spanNearQuery(2)——不带有顺序的

lucene的spanNearQuery(2)——不带有顺序的

www.MyException.Cn  网友分享于:2018-03-30  浏览:0次
lucene的spanNearQuery(二)——不带有顺序的

 这个博客中有个未解之谜, 如果读者有更好的理解的话,可以联系我,我的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)。

 

文章评论

那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
总结2014中国互联网十大段子
总结2014中国互联网十大段子
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
如何成为一名黑客
如何成为一名黑客
中美印日四国程序员比较
中美印日四国程序员比较
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
10个调试和排错的小建议
10个调试和排错的小建议
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
那些争议最大的编程观点
那些争议最大的编程观点
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
 程序员的样子
程序员的样子
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
老程序员的下场
老程序员的下场
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员应该关注的一些事儿
程序员应该关注的一些事儿
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
漫画:程序员的工作
漫画:程序员的工作
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我的丈夫是个程序员
我的丈夫是个程序员
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员必看的十大电影
程序员必看的十大电影
程序员都该阅读的书
程序员都该阅读的书
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
编程语言是女人
编程语言是女人
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员的鄙视链
程序员的鄙视链
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
一个程序员的时间管理
一个程序员的时间管理
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
鲜为人知的编程真相
鲜为人知的编程真相
我是如何打败拖延症的
我是如何打败拖延症的
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员和编码员之间的区别
程序员和编码员之间的区别
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
每天工作4小时的程序员
每天工作4小时的程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有