欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

FST源代码解读6——FST的读取

程序员文章站 2022-03-30 15:24:50
...

lucene fst 源代码 解读

 

在lucene的官方文档里,有读取的代码的介绍,直接用了一个Util类,代码如下,方法名字是:org.apache.lucene.util.fst.Util.get(FST<T>, IntsRef)

/** Looks up the output for this input, or null if the input is not accepted. */
public static <T> T get(FST<T> fst, IntsRef input) throws IOException {
	// TODO: would be nice not to alloc this on every lookup
	final FST.Arc<T> arc = fst.getFirstArc(new FST.Arc<T>());// 获得一个指向root的虚拟arc
	final BytesReader fstReader = fst.getBytesReader();//获得一个reader,如果是没有压缩的,则是从后面读,否则从前面开始读
	// Accumulate output as we go
	T output = fst.outputs.getNoOutput();
	for (int i = 0; i < input.length; i++) {
		if (fst.findTargetArc(input.ints[input.offset + i], arc, arc, fstReader) == null) {// 获得一个lebal是指定值的arc,如果这个找不到,则认为要查找的input是不存在的,直接返回null,
			return null;
		}
		output = fst.outputs.add(output, arc.output);//找到了,累加输出
	}
	if (arc.isFinal()) {//都找到了,需要判断原来的输入是不是final的,如果不是也不存在。
		return fst.outputs.add(output, arc.nextFinalOutput);//是final的,再累加final输出
	} else {
		return null;
	}
}

 

/**
 * 读的时候调用,找到一个lebal是指定lebal的arc <br/>
 * Finds an arc leaving the incoming arc, replacing the arc in place. This returns null if the arc was not found, else the incoming arc.
 * @param follow 查找的条件的arc
 * @param arc 最终将查询的结果写入到这个里面来
 */
private Arc<T> findTargetArc(int labelToMatch, Arc<T> follow, Arc<T> arc, BytesReader in, boolean useRootArcCache) throws IOException {

	if (labelToMatch == END_LABEL) {//TODO 这个没有用到过,忽略
		if (follow.isFinal()) {
			if (follow.target <= 0) {
				arc.flags = BIT_LAST_ARC;
			} else {
				arc.flags = 0;
				// NOTE: nextArc is a node (not an address!) in this case:
				arc.nextArc = follow.target;
				arc.node = follow.target;
			}
			arc.output = follow.nextFinalOutput;
			arc.label = END_LABEL;
			return arc;
		} else {
			return null;
		}
	}

	// Short-circuit if this arc is in the root arc cache:
	if (useRootArcCache && cachedRootArcs != null && follow.target == startNode	&& labelToMatch < cachedRootArcs.length) {//从缓存中查找
		final Arc<T> result = cachedRootArcs[labelToMatch];
		// LUCENE-5152: detect tricky cases where caller modified previously returned cached root-arcs:
		assert assertRootCachedArc(labelToMatch, result);
		if (result == null) {
			return null;
		} else {
			arc.copyFrom(result);
			return arc;
		}
	}
	
	if (!targetHasArcs(follow)) {//判断指向的节点是否存在符合条件的arc
		return null;
	}
	in.setPosition(getNodeAddress(follow.target));//准备从bytes中读取,提前找好位置,定位到taget节点的开始的位置
	arc.node = follow.target;

	if (in.readByte() == ARCS_AS_FIXED_ARRAY) {//fixedArray格式的,采用二分查找
		// Arcs are full array; do binary search:
		arc.numArcs = in.readVInt();//arc的数量
		if (packed || version >= VERSION_VINT_TARGET) {//一个arc占用的内存的大小
			arc.bytesPerArc = in.readVInt();
		} else {
			arc.bytesPerArc = in.readInt();
		}
		arc.posArcsStart = in.getPosition();//这个节点中的arc开始的位置
		int low = 0;//开始用二分法查找
		int high = arc.numArcs - 1;
		while (low <= high) {
			int mid = (low + high) >>> 1;
			in.setPosition(arc.posArcsStart);
			in.skipBytes(arc.bytesPerArc * mid + 1);//先指向开始,然后再根据每个arc的大小和是第几个arc移动指针,这样就移动到了中间的一个arc上
			int midLabel = readLabel(in);//读取这个arc的lebal
			final int cmp = midLabel - labelToMatch;//根据label的大小判断该怎么移动指针。
			if (cmp < 0) {
				low = mid + 1;
			} else if (cmp > 0) {
				high = mid - 1;
			} else {
				arc.arcIdx = mid - 1;//正好匹配,则读取这个arc。这里减一是因为后面再readNextRealArc中会自动加一
				return readNextRealArc(arc, in);
			}
		}
		return null;
	}

	// Linear scan  如果不是fixedArray的,则先读取第一个,读取到arc中
	readFirstRealTargetArc(follow.target, arc, in);

	while (true) {//遍历
		// TODO: we should fix this code to not have to create object for the output of every arc we scan... only for the matching arc, if found
		if (arc.label == labelToMatch) {//相同的
			return arc;
		} else if (arc.label > labelToMatch) {//因为是从小到大的排列每个节点上的arc,所以如果一个arc的值大于目标值则标识找不到
			return null;
		} else if (arc.isLast()) {//找不到
			return null;
		} else {//继续读取下一个arc的属性到arc中
			readNextRealArc(arc, in);
		}
	}
}

 

还有一个功能是根据输出查找输入,即:Util.getByOutput(FST<Long>, long),不过他是有条件的,只有当加入到fst的key-value中所有的value是按照从小到大的顺序添加时才可以使用这个方法,且只有当输出值是long时。这种的使用情况为:用在文件指针上。代码如下:

/**
 * Reverse lookup (lookup by output instead of by input), in the special case when your FSTs outputs are strictly ascending. This locates the input/output pair where the output is equal to the target, and will return null if that output does not exist.
 * <p>
 * NOTE: this only works with {@code FST<Long>}, only works when the outputs are ascending in order with the inputs. For example, simple ordinals (0,1, 2, ...), or file offets (when appending to a file) fit this.  只有long的输出才可以用。
 */
public static IntsRef getByOutput(FST<Long> fst, long targetOutput) throws IOException {
	
	final BytesReader in = fst.getBytesReader();

	// TODO: would be nice not to alloc this on every lookup  指向root的虚拟arc
	FST.Arc<Long> arc = fst.getFirstArc(new FST.Arc<Long>());

	FST.Arc<Long> scratchArc = new FST.Arc<>();

	final IntsRefBuilder result = new IntsRefBuilder();
	return getByOutput(fst, targetOutput, in, arc, scratchArc, result);//
}

/**
 * 别忘了前提是按照output严格递增的顺序来添加的,这个特性导致arc上的输出也是不会减小的,而且不会出现负数的输出。在读取的时候如果一个节点上任何arc的输出值和之前读取的所有的arc上的输出的累加和
 * 不等于targetOutput,则此节点上选择的arc是  输出值和之前所有的arc的输出值的和比targetOutput要小的集合中的最大的一个,解释:首先不能是超过targetOutput的,因为这种fst的所有的arc的输出都不会有负数,
 * 所以一旦超过targetOutput,则不会变小;第二:因为所有的输出是按照严格递增来的,那么同一个节点上发出的arc中,顺序靠后的arc上的输出一定比   在这个arc之前的任意arc开始到结束节点的所有arc上的输出的和要大
 * ,比如在最大的一个都不够大的时候,必须选最大的一个才有可能是相等的,不选最大的那个则一定是比targetOutput小的。
 * @param fst
 * @param targetOutput	查找的目标值,也即是输出
 * @param in			读取fst的reader
 * @param arc			指向root的虚拟的arc
 * @param scratchArc	        scratchArc是一个复用的对象,用来记录上一个读取的arc
 * @param result		将查找到的结果写入到里面
 * @return
 * @throws IOException
 */
public static IntsRef getByOutput(FST<Long> fst, long targetOutput, BytesReader in, Arc<Long> arc, Arc<Long> scratchArc, IntsRefBuilder result) throws IOException {
	
	long output = arc.output;//读取的lebal
	int upto = 0;

	while (true) {
		
		// 判断之前读取的输出是否匹配targetOutput
		if (arc.isFinal()) {
			final long finalOutput = output + arc.nextFinalOutput;//留心final output
			if (finalOutput == targetOutput) {//如果相等,则找到了
				result.setLength(upto);
				return result.get();
			} else if (finalOutput > targetOutput) {
				return null;
			}
		}//如果不是final的,则继续读取当前的arc的指向的节点的所有的arc

		if (FST.targetHasArcs(arc)) {
			result.grow(1 + upto);//还没有查找到,而且有新的查找可能,所以要增大

			fst.readFirstRealTargetArc(arc.target, arc, in);//读取arc.target节点上的第一个arc,将结果读取再arc上

			if (arc.bytesPerArc != 0) {//这个节点是采用fixedArray格式存储的

				int low = 0;
				int high = arc.numArcs - 1;
				int mid = 0;
				boolean exact = false;
				while (low <= high) {//在所有的arc中查找;如果找不到的话
					mid = (low + high) >>> 1;
					in.setPosition(arc.posArcsStart);// 指向这个节点的开始
					in.skipBytes(arc.bytesPerArc * mid);//移动到这个arc的开始
					final byte flags = in.readByte();//读取这个arc的flag
					fst.readLabel(in);//读取label
					final long minArcOutput;
					if ((flags & FST.BIT_ARC_HAS_OUTPUT) != 0) {//有输出
						final long arcOutput = fst.outputs.read(in);//读取输出
						minArcOutput = output + arcOutput;//当前查找到的输出
					} else {
						minArcOutput = output;
					}
					if (minArcOutput == targetOutput) {
						exact = true;
						break;
					} else if (minArcOutput < targetOutput) {
						low = mid + 1;
					} else {
						high = mid - 1;
					}
				}

				if (high == -1) {// 这个是连第一个都比targetOutput大的时候,此时说明找不到,因为后面的只能更大
					return null;
				} else if (exact) {//他的目的是读取下标是mid的arc,但是因为下面的readNextRealArc会加一,所以这里要减一
					arc.arcIdx = mid - 1;
				} else {// 这个需要好好分析一下二分查找,如果找不到的话,low永远是在准确值的左边的一个,所以减一就可以了,因为下面的readNextRealArc中会加一,所以这里要减二。
					arc.arcIdx = low - 2;
				}

				fst.readNextRealArc(arc, in);// 读取下一个arc(读了之后可能是准确的,可能是不准确的,如果不准确,则是输出最紧接于targetOutput的arc)
				result.setIntAt(upto++, arc.label);//将读取的lebal写在result中
				output += arc.output;//将读取的输出添加到output

			} else {//当不是fixedArray格式存储的时候,挨个比对,要查找output+arc.ouput < targetOutput中最大的一个(或者说最后的一个),也就是下面的pervArc,然后再去继续读取他指向的node上的arc
				FST.Arc<Long> prevArc = null;
				while (true) {//遍历当前节点上的所有的arc
					// This is the min output we'd hit if we follow this arc:
					final long minArcOutput = output + arc.output;//从小的开始匹配
					if (minArcOutput == targetOutput) {//相等了,不能再对比下去了,因为后面的一定更大。所以要退出让前面的程序判断是否满足条件,即是否是final的
						// Recurse on this arc:
						output = minArcOutput;
						result.setIntAt(upto++, arc.label);
						break;
					} else if (minArcOutput > targetOutput) {//我们的目的就是找到一个比targetOutput大的,然后确定他的前一个,也就是prevArc。
						if (prevArc == null) {//prevArc不存在,说明是第一次遍历这个node,当前的minArcOutput是这个节点任意的arc所能提供的最小的值,最小的值都比targetOutput,则一定不满足
							return null;
						} else {//优先看最后一个else,就很好明白了
							// Recurse on previous arc:
							arc.copyFrom(prevArc);
							result.setIntAt(upto++, arc.label);
							output += arc.output;
							break;
						}
					} else if (arc.isLast()) {// 小于targetOutput且是最后一个,则需要继续读取这个arc指向的节点。所以要break,退出对当前节点的遍历。如果不是最后一个,则进入下面的else,继续遍历当前节点的arc
						// Recurse on this arc:
						output = minArcOutput;
						result.setIntAt(upto++, arc.label);
						break;
					} else {// 结果比targetOutput要小,则记录这个arc为prev,因为下一个arc有可能比targetOutput要大,如果是的话,那么prev就是我们要找的arc。
						// Read next arc in this node:
						prevArc = scratchArc;//scratchArc就是当前的arc,传入的时候是一个对象
						prevArc.copyFrom(arc);
						fst.readNextRealArc(arc, in);//继续读取这个节点的下一个arc,然后继续判断这个是否比targetOutput大
					}
				}
			}
		} else {//如果这个节点没有输出,说明是最后一个节点了,还不匹配,则找不到
			return null;
		}
	}
}

 这个的代码不难,他的关键就是在查找一个节点的arc的时候,使用所有 arc输出和之前的输出的和 小于目标值的所有的arc中,和最大的一个arc,然后再顺着这个思路查找这个arc的下一个节点。不过用处我觉得不如根据input查找out多。 

 

如果懂了写的代码,读的代码是很容易理解的,FST就这样看完了,花了我足足一周的时间,不过好开心哈哈哈哈哈哈。如果有地方错误,请联系我的qq:1308567317

 

相关标签: fst lucene 使用