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

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